Python一致散列替换

Question

正如许多人所指出的，Python的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是否只应用于字符串和字节数组的散列

我为什么要问这个问题？

我有一个系统，它依赖于散列来记住我们是否见过给定的dict（以任何顺序）：{key: tuple(ints)}。在该系统中，键是文件名的集合，元组是os.stat_result的子集，例如与它们关联的(size, mtime)。该系统用于根据检测差异做出更新/同步决策

在我的应用程序中，我有大约100K个这样的dict，每个dict可以表示数千个文件及其状态，因此缓存的紧凑性非常重要

我可以容忍可能的哈希冲突（另请参见birthday paradox）产生的小误报率（对于64位哈希，<；10^-19）

对于每个这样的dict“fsd”，一个紧凑的表示如下所示：

def fsd_hash(fsd: dict):
    return hash(frozenset(fsd.items()))

它非常快，并产生一个int来表示整个dict（具有顺序不变性）。如果fsddict中的任何内容发生更改，则哈希很可能会不同

不幸的是，hash仅在单个Python实例中是一致的，这使得主机无法比较各自的哈希值。将完整缓存（{location_name: fsd_hash}）持久化到要在重新启动时重新加载的磁盘也是无用的

我不能期望使用该模块的更大系统已经被PYTHONHASHSEED=0调用，据我所知，一旦Python实例启动，就没有办法改变这一点

我尝试过的事情

1. 我可以使用hashlib.sha1或类似的方法来计算一致性散列。这比较慢，而且我不能直接使用frozenset技巧：我必须在更新哈希程序时以一致的顺序（例如，通过对键排序，慢）迭代dict。在我对真实数据的测试中，我发现速度慢了50倍以上

2. 我可以尝试对每个项目获得的一致哈希应用顺序不变的哈希算法（也很慢，因为为每个项目启动一个新的哈希程序很耗时）

3. 我可以尝试将所有内容转换为int或int的元组，然后再转换为此类元组的冻结集。目前，似乎所有的int、tuple(int)和frozenset(tuple(int))都会产生一致的散列，但是：这是有保证的吗？如果是，我希望这种情况持续多久

附加问题：更一般地说，当dict包含各种类型和类时，为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)

Answer 1

对广泛问题的简短回答：除了x == y要求hash(x) == hash(y)的总体保证之外，没有明确的关于散列稳定性的保证。这意味着x和y都是在程序的同一次运行中定义的（如果x == y其中一个显然不存在于该程序中，则无法执行，因此不需要保证跨运行的哈希）

具体问题的详细答案：

Is [your belief that int, float, tuple(x), frozenset(x) (for x with consistent hash) have consistent hashes across separate runs] always true and guaranteed?

数字类型也是如此，使用the mechanism being officially documented，但是该机制只保证特定编译的特定解释器。^{} provides the various constants，它们在该解释器上是一致的，但是在不同的解释器上（CPython vs.pypypy，64位编译vs.32位编译，甚至3.n vs.3.n+1），它们可能不同（在64位与32位CPython的情况下，记录的结果有所不同），因此哈希值不能在具有不同解释器的机器之间移植

对于tuple和frozenset的算法没有任何保证；我想不出任何理由他们会在运行之间更改它（如果底层类型是种子，那么tuple和frozenset会从中受益，而不需要任何更改），但是他们可以并且确实会在不同版本的CPython之间更改实现（例如in late 2018 they made a change to reduce the number of hash collisions in short ^{}s of ^{}s and ^{}s），因此，如果存储3.7中的tuple散列，然后在3.8+中计算相同tuple的散列，它们将不匹配（即使它们在3.7上的运行之间或在3.8上的运行之间匹配）

If so, is that expected to stay that way?

我可以很容易地看到int的种子散列（扩展来说，所有数值类型都保留数值散列/相等保证），原因与它们为str/bytes等种子散列相同。主要障碍是：

1. 它几乎肯定会比当前非常简单的算法慢
2. 通过显式地记录数值散列算法，他们需要很长一段时间的反对，然后才能更改它
3. 这并不是绝对必要的（如果web应用程序需要种子哈希来保护DoS，它们总是可以在将int作为密钥使用之前将其转换为str）

Is the PYTHONHASHSEED only applied to salt the hash of strings and byte arrays?

除了str和bytes之外，它还适用于一些随机的东西，这些东西根据str或bytes的散列实现自己的散列，通常是因为它们已经可以自然地转换为原始字节，并且通常用作dict中的键它由面向web的前端填充。我所知道的这些前端包括各种类型的datetime模块（datetime、date、time，尽管模块本身中没有实际记录），以及具有字节大小格式的只读memoryview（即hash equivalently to hashing the result of the view's ^{} method）

What would be a good way to write a consistent hash replacement for hash(frozenset(some_dict.items())) when the dict contains various types and classes?

最简单/最可组合的解决方案可能是将const_hash定义为a single dispatch function，使用方法与hash本身相同。这避免了在一个地方定义一个必须处理所有类型的函数；您可以使用const_hash默认实现（它只依赖于hash对于那些具有已知一致散列的内容），并为您知道的不一致（或可能包含不一致内容）的内置类型提供其他定义在那里，虽然仍然允许人们通过导入const_hash并用@const_hash.register装饰其类型的实现来注册他们自己的单一分派函数，从而无缝地扩展它所涵盖的内容集。实际上，它与您建议的const_hash没有显著区别，但它更易于管理