将字典进行哈希处理？

Question

将字典进行哈希处理？

pythonhashdictionary

233

为了缓存目的，我需要从一个包含在字典中的GET参数生成一个缓存键。

目前，我正在使用sha1(repr(sorted(my_dict.items())))（sha1()是一个使用hashlib内部的便捷方法），但我很好��是否有更好的方法。

- ThiefMaster

7

这可能不能处理嵌套字典。最简短的解决方案是使用json.dumps(my_dict, sort_keys=True)替代，它会递归到字典值中。 - Andrey Fedorov

3

关于转储，请参考 http://stackoverflow.com/a/12739361/1082367，该网站指出：“pickle 的输出不能保证规范化，原因与 dict 和 set 的顺序不确定性相似。不要使用 pickle、pprint 或 repr 进行哈希处理。” - Matthew Cornell

2

有关哈希可变数据结构（如字典）的有趣背景故事：https://www.python.org/dev/peps/pep-0351/曾提出允许任意冻结对象，但被拒绝。有关理由，请参见python-dev中的此线程：https://mail.python.org/pipermail/python-dev/2006-February/060793.html - FluxLemur

1

如果你的数据是json格式，并且你想要语义不变的哈希，请查看https://github.com/schollii/sandals/blob/master/json_sem_hash.py。它适用于嵌套结构（当然，因为json），并且不依赖于像保留顺序这样的字典内部（在python的生命周期中已经发生了演变），如果两个数据结构在语义上相同，则会给出相同的哈希值（例如`{'a': 1, 'b':2}在语义上与{'b':2, 'a':1}`相同）。我还没有在任何太复杂的东西上使用过它，所以效果可能有所不同，但欢迎反馈。 - Oliver

1

@shelper 你忘记了 repr() 函数（在 Python 3 中可能还需要加上 .encode()）。 - ThiefMaster

显示剩余2条评论

17个回答

154

如果您的字典没有嵌套，您可以使用字典的项目创建一个不可变集合，并使用hash()函数：

hash(frozenset(my_dict.items()))

这比生成JSON字符串或字典的表示方式要少得多的计算量。

更新：请参见下面的评论，说明此方法可能不会产生稳定的结果。

- Imran

10

对于嵌套字典，这对我不起作用。我没有尝试下面的解决方案（太复杂了）。楼主的解决方案完全有效。我将sha1替换为hash以节省一个导入。 - spatel

11

这样做行不通，因为“tuple”意味着有序，但字典项目是无序的。使用“frozenset”更好。 - Antimony

42

如果需要在不同的机器之间保持一致性，请注意内置哈希的问题。在云平台上（比如Heroku和GAE）实现的Python将在不同的实例上返回不同的hash()值，这使得它对于任何必须在两个或更多“机器”（在Heroku中为动态资源）之间共享的内容都是无用的。 - B Robster

11

hash()函数不会产生稳定的输出，这可能很有趣。这意味着，给定相同的输入，在同一Python解释器的不同实例中它会返回不同的结果。对我来说，这看起来像是每次启动解释器时生成了某种种子值。 - Hermann Schachner

9

预期的。据我记得，种子是为了安全原因引入的，以添加某种内存随机化。因此，您不能期望在两个Python进程之间哈希值相同。 - Nikokrock

显示剩余5条评论

76

编辑: 如果 所有的键都是字符串，那么在继续阅读本答案之前，请查看Jack O'Connor的更简单（更快）的解决方案（也适用于哈希嵌套字典）。

尽管有一个答案被接受了，但问题的标题是“哈希Python字典”，而就该标题而言，答案并不完整。（针对问题正文，答案是完整的。）

嵌套字典

如果你在 Stack Overflow 上搜索如何哈希一个字典，你可能会偶然发现这个题目，并且如果你试图哈希多层嵌套的字典，则上面的答案将无法工作，你必须实现某种递归机制来检索哈希值。

下面是这样一种机制：

import copy

def make_hash(o):

  """
  Makes a hash from a dictionary, list, tuple or set to any level, that contains
  only other hashable types (including any lists, tuples, sets, and
  dictionaries).
  """

  if isinstance(o, (set, tuple, list)):

    return tuple([make_hash(e) for e in o])    

  elif not isinstance(o, dict):

    return hash(o)

  new_o = copy.deepcopy(o)
  for k, v in new_o.items():
    new_o[k] = make_hash(v)

  return hash(tuple(frozenset(sorted(new_o.items()))))

额外福利：对象和类的哈希

hash() 函数对于类或实例的哈希处理效果很好。但是，关于对象，我发现了一个问题：

class Foo(object): pass
foo = Foo()
print (hash(foo)) # 1209812346789
foo.a = 1
print (hash(foo)) # 1209812346789

即使我已经修改了foo，哈希值仍然相同。这是因为foo的身份没有改变，所以哈希值相同。如果你想让foo根据其当前定义以不同的方式进行哈希，解决方案是根据实际更改内容进行哈希。在这种情况下，使用__dict__属性进行哈希：

class Foo(object): pass
foo = Foo()
print (make_hash(foo.__dict__)) # 1209812346789
foo.a = 1
print (make_hash(foo.__dict__)) # -78956430974785

遗憾的是，当您尝试使用类本身执行相同的操作时：

print (make_hash(Foo.__dict__)) # TypeError: unhashable type: 'dict_proxy'

__dict__ 属性所表示的类并不是一个普通的字典：

print (type(Foo.__dict__)) # type <'dict_proxy'>

这里有一个类似于之前机制的方法，可以适当处理类：

import copy

DictProxyType = type(object.__dict__)

def make_hash(o):

  """
  Makes a hash from a dictionary, list, tuple or set to any level, that 
  contains only other hashable types (including any lists, tuples, sets, and
  dictionaries). In the case where other kinds of objects (like classes) need 
  to be hashed, pass in a collection of object attributes that are pertinent. 
  For example, a class can be hashed in this fashion:

    make_hash([cls.__dict__, cls.__name__])

  A function can be hashed like so:

    make_hash([fn.__dict__, fn.__code__])
  """

  if type(o) == DictProxyType:
    o2 = {}
    for k, v in o.items():
      if not k.startswith("__"):
        o2[k] = v
    o = o2  

  if isinstance(o, (set, tuple, list)):

    return tuple([make_hash(e) for e in o])    

  elif not isinstance(o, dict):

    return hash(o)

  new_o = copy.deepcopy(o)
  for k, v in new_o.items():
    new_o[k] = make_hash(v)

  return hash(tuple(frozenset(sorted(new_o.items()))))

您可以使用此方法返回一个哈希元组，其中包含任意数量的元素：

# -7666086133114527897
print (make_hash(func.__code__))

# (-7666086133114527897, 3527539)
print (make_hash([func.__code__, func.__dict__]))

# (-7666086133114527897, 3527539, -509551383349783210)
print (make_hash([func.__code__, func.__dict__, func.__name__]))

注意：以上所有代码都假定使用Python 3.x。尽管我认为make_hash()在早期版本（如2.7.2）中也能运行，但我没有在早期版本中测试过。至于使示例工作，我确实知道

func.__code__

应该被替换为

func.func_code

- jomido

isinstance函数的第二个参数需要一个序列，因此isinstance(o, (set, tuple, list))可以正常工作。 - Xealot

谢谢你让我意识到frozenset可以一致地哈希查询字符串参数 :) - Xealot

1

需要对项目进行排序，以便在字典项顺序不同但键值不变的情况下创建相同的哈希值 ->返回哈希元组（frozenset(sorted(new_o.items()))） - Bas Koopmans

3

在Python 3.7中，这个解决方案的性能比 hash(json.dumps(d, sort_keys=True)) 差了18倍。证明链接：https://pastebin.com/XDZGhNHs - kolypto

2

@kolypto的Json解决方案取决于字符串的大小（显然），而哈希解决方案的时间是稳定的。证明使用您的代码与更大的字符串。 - Gulzar

显示剩余6条评论

19

以下代码避免使用Python的hash()函数，因为它不会提供在Python重新启动时保持一致的哈希值（请参见Python 3.3中的哈希函数在会话之间返回不同的结果）。make_hashable()将对象转换为嵌套元组，make_hash_sha256()还将repr()转换为基于base64编码的SHA256哈希值。

import hashlib
import base64

def make_hash_sha256(o):
    hasher = hashlib.sha256()
    hasher.update(repr(make_hashable(o)).encode())
    return base64.b64encode(hasher.digest()).decode()

def make_hashable(o):
    if isinstance(o, (tuple, list)):
        return tuple((make_hashable(e) for e in o))

    if isinstance(o, dict):
        return tuple(sorted((k,make_hashable(v)) for k,v in o.items()))

    if isinstance(o, (set, frozenset)):
        return tuple(sorted(make_hashable(e) for e in o))

    return o

o = dict(x=1,b=2,c=[3,4,5],d={6,7})
print(make_hashable(o))
# (('b', 2), ('c', (3, 4, 5)), ('d', (6, 7)), ('x', 1))

print(make_hash_sha256(o))
# fyt/gK6D24H9Ugexw+g3lbqnKZ0JAcgtNW+rXIDeU2Y=

- Claudio Fahey

1

make_hash_sha256(((0,1),(2,3)))==make_hash_sha256({0:1,2:3})==make_hash_sha256({2:3,0:1})!=make_hash_sha256(((2,3),(0,1)))。这不是我正在寻找的完美解决方案，但它是一个不错的中间步骤。我考虑在每个元组的开头添加"type(o).name"以强制区分。 - Poik

如果你也想对列表进行排序：tuple(sorted((make_hashable(e) for e in o))) - Suraj

make_hash_sha256() - 很棒！ - jtlz2

3

@Suraj 在进行哈希之前不应该想要对列表进行排序，因为其内容以不同的顺序出现的列表绝对不是同一件事情。如果项目的顺序并不重要，那么问题在于你使用了错误的数据结构。你应该使用一个集合(set)而不是一个列表(list)。 - scottclowe

@scottclowe 非常正确。感谢您补充这一点。有两种情况下，您仍需要一个列表（没有特定的排序需求）- 1. 重复项列表。2. 当您必须直接使用JSON时。因为JSON不支持“set”表示。 - Suraj

18

MD5哈希

对于我来说最稳定的方法是使用MD5哈希和JSON.stringify。

from typing import Dict, Any
import hashlib
import json

def dict_hash(dictionary: Dict[str, Any]) -> str:
    """MD5 hash of a dictionary."""
    dhash = hashlib.md5()
    # We need to sort arguments so {'a': 1, 'b': 2} is
    # the same as {'b': 2, 'a': 1}
    encoded = json.dumps(dictionary, sort_keys=True).encode()
    dhash.update(encoded)
    return dhash.hexdigest()

- Shay Dahan

1

我发现用yaml替换json有所帮助，因为它可以序列化类及其属性。import yaml ... yaml.dump(dictionary, sort_keys=True).encode() - DomDev

注意：这对于Python中的嵌套字典无效。DeepDiff模块中的DeepHash可以解决这个问题！ - Farhan Hai Khan

1

@FarhanHaiKhan 请解释一下。json.dumps 看起来可以稳定地转储嵌套字典。 - dfrankow

看起来是这样，但我最初在嵌套的东西上尝试了一次，并没有找到匹配，尽管这两个字典是相同的。结构似乎很好地嵌套，所以得出了这个结论。 - Farhan Hai Khan

16

这里是一个更清晰的解决方案。

def freeze(o):
  if isinstance(o,dict):
    return frozenset({ k:freeze(v) for k,v in o.items()}.items())

  if isinstance(o,list):
    return tuple([freeze(v) for v in o])

  return o


def make_hash(o):
    """
    makes a hash out of anything that contains only list,dict and hashable types including string and numeric types
    """
    return hash(freeze(o))

- smartnut007

3

如果你将 if isinstance(o,list): 改为 if isinstance(obj, (set, tuple, list)):，那么这个函数就可以在任何对象上运行。 - Peter Schorn

11

hash(frozenset(x.items()) 和 hash(tuple(sorted(x.items())) 能够工作，但是这样做会分配大量内存并复制所有的键值对。一个好的哈希函数应该避免大量的内存分配。

一些数学知识可以帮助解决这个问题。大多数哈希函数的问题在于它们认为顺序很重要。要哈希一个无序结构，你需要进行可交换操作。乘法不起作用，因为任何哈希为 0 的元素都意味着整个积为 0。按位 & 和 | 倾向于全部为 0 或 1。有两个好的选择：加法和异或。

from functools import reduce
from operator import xor

class hashable(dict):
    def __hash__(self):
        return reduce(xor, map(hash, self.items()), 0)

    # Alternative
    def __hash__(self):
        return sum(map(hash, self.items()))

一点要注意的是：xor的部分原理在于`dict`保证键唯一。使用sum的原因是Python会对结果进行位截断。

如果您想要哈希一个多重集合，建议使用sum。使用xor时，{a}将与{a, a, a}哈希为同样的值，因为x ^ x ^ x = x。

如果您确实需要SHA提供的保证，这种方式可能不适用于您。但要在集合中使用字典，这种方法就可以良好运作；Python容器对某些冲突有着较强的韧性，并且底层哈希函数效果相当不错。

- Ben

6

使用DeepDiff模块中的DeepHash功能

from deepdiff import DeepHash
obj = {'a':'1', 'b':'2'}
hashes = DeepHash(obj)[obj]

- JithinM

注意：这适用于Python中的嵌套字典，而MD5哈希不适用！ - Farhan Hai Khan

1

请编辑为：obj = {'a': '1', 'b': '2'} - Ioannis Koumarelas

5

从2013年回答更新...

以上所有答案对我来说似乎都不可靠。原因是使用了items()。据我所知，这会以机器相关的顺序输出。

那么这个怎么样呢？

import hashlib

def dict_hash(the_dict, *ignore):
    if ignore:  # Sometimes you don't care about some items
        interesting = the_dict.copy()
        for item in ignore:
            if item in interesting:
                interesting.pop(item)
        the_dict = interesting
    result = hashlib.sha1(
        '%s' % sorted(the_dict.items())
    ).hexdigest()
    return result

- Steve Yeago

你认为dict.items不返回可预测排序列表有什么影响吗？frozenset可以解决这个问题。 - glarrain

2

一个集合的定义是无序的。因此，添加对象的顺序是不相关的。你必须意识到内置函数hash并不关心frozenset内容的打印方式或类似的东西。在几台机器和Python版本中进行测试，你就会看到。 - glarrain

为什么在value = hash（'％s :: ％s'％（value，type（value）））中使用额外的hash（）调用？ - RuiDo

4

为了保持键的顺序，我更喜欢使用一个简单粗暴的解决方案，而不是使用hash(str(dictionary))或hash(json.dumps(dictionary))。

from pprint import pformat
h = hash(pformat(dictionary))

即使对于无法JSON序列化的类型（如DateTime等），它也能正常工作。

- shirk3y

3

谁能保证pformat或json总是以相同的顺序使用？ - ThiefMaster

1

@ThiefMaster，“从2.5版本开始更改：在计算显示之前，字典按键排序；在2.5之前，仅当字典的显示需要超过一行时才对其进行排序，尽管这并未记录在文档中。”（https://docs.python.org/2/library/pprint.html） - Arel

3

这对我来说似乎不太有效。pprint模块和pformat函数被作者理解为用于显示目的而非序列化。因此，你不应该觉得pformat总是会返回一个可行的结果。请注意不要改变原意。 - David Sanders

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jack O'Connor · Accepted Answer

使用 sorted(d.items()) 并不能保证我们得到一个稳定的表示。因为在字典 d 中有些值可能也是字典，它们的键仍将以任意顺序出现。只要所有键都是字符串，我更喜欢使用：

json.dumps(d, sort_keys=True)

话虽如此，如果哈希需要在不同的计算机或Python版本之间稳定，我不能确定这是100%可靠的。您可能需要添加separators和ensure_ascii参数以保护自己免受默认设置的任何更改。我会很感激您的评论。