Thi*_*ter 135 python hash dictionary
出于缓存目的,我需要从dict中存在的GET参数生成缓存键.
目前我正在使用sha1(repr(sorted(my_dict.items())))(sha1()是一种在内部使用hashlib的便捷方法),但我很好奇是否有更好的方法.
Jac*_*nor 118
使用sorted(d.items())不足以让我们获得稳定的代表.其中一些值d也可能是字典,它们的键仍然会以任意顺序出现.只要所有键都是字符串,我更喜欢使用:
json.dumps(d, sort_keys=True)
也就是说,如果哈希需要在不同的机器或Python版本之间保持稳定,我不确定这是否是防弹的.您可能希望添加separators和ensure_ascii参数以保护自己免受对默认值的任何更改.我很感激评论.
Imr*_*ran 99
如果您的字典没有嵌套,您可以使用dict的项目进行冻结并使用hash():
hash(frozenset(my_dict.items()))
这比计算JSON字符串或字典表示的计算密集程度要低得多.
jom*_*ido 59
编辑:如果你的所有键都是字符串,那么在继续阅读这个答案之前,请参阅Jack O'Connor的更简单(更快)的解决方案(这也适用于散列嵌套字典).
虽然答案已被接受,但问题的标题是"哈希蟒蛇字典",关于该标题的答案是不完整的.(关于问题的正文,答案是完整的.)
嵌套字典
如果一个人搜索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
小智 19
对我来说产生最稳定结果的方法是使用 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()
sma*_*007 12
这是一个更清晰的解决方案.
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))
Ben*_*Ben 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()))
一点：异或之所以有效，部分原因是dict保证键是唯一的。sum 之所以有效，是因为 Python 会按位截断结果。
如果你想对多重集进行散列，那么 sum 是更好的选择。使用异或，将散列到与因为{a}相同的值。{a, a, a}x ^ x ^ x = x
如果您确实需要 SHA 做出的保证，那么这对您不起作用。但是要在集合中使用字典，这会很好地工作；Python 容器对某些冲突具有抵抗力，并且底层的哈希函数非常好。
小智 8
下面的代码避免使用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=
小智 6
使用DeepDiff模块中的 DeepHash
from deepdiff import DeepHash
obj = {'a':'1', 'b':'2'}
hashes = DeepHash(obj)[obj]
自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