许多人指出,Python的
然而,我注意到某些对象的哈希仍然是一致的(至少在Python 3.7中),包括
这总是真实和可靠的吗?如果是这样,那么预计会保持这种方式吗?
为什么我要问这个问题?
我有一个依赖哈希记住是否已经看到给定的字典(任何顺序)的系统:
在我的应用程序中,我有大约10万个这样的字典,每个字典可以表示数千个文件及其状态,因此缓存的紧凑性非常重要。
我可以容忍小的误报率(64位哈希值可能会出现<10^-19的碰撞率,另请参见birthday paradox)。
每个这样字典的一种紧凑表示如下所示:“
hash
从3.3版本开始不再一致,因为默认情况下使用随机的PYTHONHASHSEED
(这是为了解决安全问题,如this excellent answer所述)。然而,我注意到某些对象的哈希仍然是一致的(至少在Python 3.7中),包括
int
、float
、tuple(x)
、frozenset(x)
(只要x
产生一致的哈希值)。例如:assert hash(10) == 10
assert hash((10, 11)) == 3713074054246420356
assert hash(frozenset([(0, 1, 2), 3, (4, 5, 6)])) == -8046488914261726427
这总是真实和可靠的吗?如果是这样,那么预计会保持这种方式吗?
PYTHONHASHSEED
只适用于给字符串和字节数组散列加盐吗?为什么我要问这个问题?
我有一个依赖哈希记住是否已经看到给定的字典(任何顺序)的系统:
{key: tuple(ints)}
。在该系统中,键是文件名的集合,元组是与它们相关联的os.stat_result
的子集,例如(size, mtime)
。该系统用于基于检测差异进行更新/同步决策。在我的应用程序中,我有大约10万个这样的字典,每个字典可以表示数千个文件及其状态,因此缓存的紧凑性非常重要。
我可以容忍小的误报率(64位哈希值可能会出现<10^-19的碰撞率,另请参见birthday paradox)。
每个这样字典的一种紧凑表示如下所示:“
fsd
”:def fsd_hash(fsd: dict):
return hash(frozenset(fsd.items()))
这个方法非常快速,使用单个整数来表示整个字典(并且不受顺序影响)。如果 fsd
字典中的任何内容发生变化,则哈希值很可能会不同。
不幸的是,hash
只在单个 Python 实例内部一致,对于主机比较其各自的哈希值而言毫无用处。将完整的缓存 ({location_name: fsd_hash}
) 持久化到磁盘上以便重新加载也没有用。
我不能指望使用该模块的更大系统已经使用了 PYTHONHASHSEED=0
,而且据我所知,一旦 Python 实例启动,就没有办法更改它。
我尝试过的事情
我可以使用
hashlib.sha1
或类似的方法来计算一致的哈希值。这会更慢,而且我不能直接使用frozenset
技巧:我必须通过一个一致的顺序(例如按键排序,速度较慢)遍历字典并更新哈希器。在我的实际数据测试中,我看到了超过50倍的减速。我可以尝试对每个项目获得的一致哈希应用无序哈希算法(也很慢,因为为每个项目启动一个新的哈希器是耗时的)。
我可以尝试将所有内容转换为整数或整数元组,然后将其冻结为元组的集合。目前,似乎所有
int
、tuple(int)
和frozenset(tuple(int))
都产生一致的哈希值,但是:这是否有保证,如果有,我可以期望它能持续多长时间?
hash(frozenset(some_dict.items()))
的好方法是什么?我可以为我拥有的类实现自定义的__hash__
(一致的),但例如我不能覆盖str
的哈希值。我想到的一件事是:def const_hash(x):
if isinstance(x, (int, float, bool)):
pass
elif isinstance(x, frozenset):
x = frozenset([const_hash(v) for v in x])
elif isinstance(x, str):
x = tuple([ord(e) for e in x])
elif isinstance(x, bytes):
x = tuple(x)
elif isinstance(x, dict):
x = tuple([(const_hash(k), const_hash(v)) for k, v in x.items()])
elif isinstance(x, (list, tuple)):
x = tuple([const_hash(e) for e in x])
else:
try:
return x.const_hash()
except AttributeError:
raise TypeError(f'no known const_hash implementation for {type(x)}')
return hash(x)
frozenset
和dict
进行无序哈希,但是将它们pickle的结果将是有序的(必须按照特定顺序写出项目,即使集合彼此相等,由于构造顺序不同,顺序也可能不同)。 - ShadowRangerhash
是非持久性的:https://dev59.com/QF4c5IYBdhLWcg3wzs6Q - Albert