对字典进行哈希？

Question

为了缓存的需要，我需要从一个字典里的GET参数生成一个缓存键。

现在我使用的是 sha1(repr(sorted(my_dict.items())))（sha1() 是一个方便的方法，内部使用了 hashlib），但我想知道有没有更好的方法。

Answer 1

编辑: 如果你的所有键都是字符串，在继续阅读这个回答之前，请先看看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

Answer 2

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

json.dumps(d, sort_keys=True)

不过，如果你需要在不同的机器或不同版本的Python之间保持哈希值的稳定性，我不太确定这样做是否万无一失。你可能需要添加 separators 和 ensure_ascii 这两个参数，以防默认设置发生变化。欢迎大家留言讨论。

Answer 3

如果你的字典不是嵌套的，你可以用字典的项（也就是键值对）来创建一个不可变集合（frozenset），然后使用 hash() 函数：

hash(frozenset(my_dict.items()))

这样做比生成字典的 JSON 字符串或表示要轻松得多，计算量也小。

更新：请查看下面的评论，了解为什么这种方法可能不会产生稳定的结果。