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仅适用于对字符串和字节数组的散列加盐？
我为什么要问？
我有一个依赖散列的系统来记住我们是否看到了给定的字典(以任何顺序): {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()))

它非常快，并产生一个 int 来表示整个 dict(具有顺序不变性)。如果在 fsd 中有任何内容dict 更改，很可能哈希会不同。
不幸的是， hash仅在单个 Python 实例中保持一致，这使得主机无法比较它们各自的哈希值。将完整缓存( {location_name: fsd_hash} )保留到磁盘以在重新启动时重新加载也是无用的。
我不能指望使用该模块的较大系统已被 PYTHONHASHSEED=0 调用。 ，而且，据我所知，一旦 Python 实例启动，就无法更改此设置。
我尝试过的东西

我可以用 hashlib.sha1或类似计算一致性哈希。这比较慢，我不能直接使用 frozenset技巧:在更新哈希器时，我必须以一致的顺序遍历 dict(例如，通过键排序，慢)。在我对真实数据的测试中，我看到速度下降了 50 倍以上。

我可以尝试在为每个项目获得的一致散列上应用顺序不变散列算法(也很慢，因为为每个项目启动一个新的散列器很耗时)。

我可以尝试将所有内容转换为整数或整数元组，然后是这些元组的卡住集。目前，似乎所有int , tuple(int)和 frozenset(tuple(int))产生一致的哈希值，但是:这是否有保证，如果是这样，我可以期望这种情况持续多久？

附加问题 :更一般地说，为 hash(frozenset(some_dict.items())) 编写一致的哈希替换是什么好方法？当 dict 包含各种类型和类时？我可以实现自定义 __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 ，但是 该机制仅适用于特定构建的特定解释器。 sys.hash_info provides the various constants ，并且它们将在该解释器上保持一致，但是在不同的解释器上(CPython 与 PyPy，64 位构建与 32 位构建，甚至 3.n 与 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 tuple s of int s and float s)，所以如果你存储了 tuple 的哈希值s 来自 3.7，然后计算相同 tuple 的哈希值s 在 3.8+ 中，它们不会匹配(即使它们会在 3.7 的运行之间或 3.8 的运行之间匹配)。

If so, is that expected to stay that way?

预计，是的。保证，没有。我可以很容易地看到 int 的种子哈希值s(并且通过扩展，对于所有数字类型，以保留数字散列/相等保证)，原因与他们为 str 播种散列的原因相同。/ bytes等。主要障碍是:

它几乎肯定会比当前非常简单的算法慢。

通过明确记录数字散列算法，他们需要长时间的弃用才能更改它。

这不是绝对必要的(如果 Web 应用程序需要种子哈希来进行 DoS 保护，它们总是可以将 int s 转换为 str，然后再将它们用作 key )。

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

超越 str和 bytes ，它适用于许多随机事物，它们根据 str 的哈希值实现了自己的哈希值。或 bytes ，通常是因为它们已经可以自然地转换为原始字节并且通常用作 dict 中的键s 由面向 Web 的前端填充。我所知道的副手包括 datetime 的各种类别。模块( datetime 、 date 、 time ，尽管这实际上并未在模块本身中记录)，以及只读 memoryview s of 具有字节大小的格式(其中 hash equivalently to hashing the result of the view's .tobytes() 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 来注册他们自己的单分派(dispatch)功能，从而无缝地扩展它涵盖的内容集。并使用 @const_hash.register 为他们的类型装饰实现.它与您提出的 const_hash 的效果没有显着差异，但它更易于管理。