在Python中对不同的元组进行哈希处理会得到相同的结果

Question

我正在使用整数矩阵的集合，并且认为将它们表示为元组是有意义的，因为它们是可哈希的。然而，对于元组，hash()函数给出了奇怪的结果：

hash(((1, -1, 0), (1, 0, 0), (1, 0, -1)))

Out[147]: -697649482279922733

hash(((1, 0, -1), (1, 0, 0), (1, -1, 0)))

Out[148]: -697649482279922733

可以看出，这两个不同的元组具有相同的哈希值。请注意它们实际上非常相似（第一个和最后一个子元组的交换），但我找不到更简单的例子：((0,1),(0,0)) 和 ((0,0),(0,1))，例如具有不同的哈希值。

你有什么线索吗？我不敢相信这只是极度不幸...现在我已经找到了问题所在，我可以轻松地绕过它，但我认为还是值得在这里提一下。

- pierre

---

这真是太倒霉了...哇。但我觉得奇怪的是找到哈希冗余这么容易。因为有一个糟糕的代码片段，它造成了问题-我使用哈希值来测试相等性，我绝对不会再这样做了。谢谢！ - pierre

近5年来，我不得不大幅更新我的答案，因为有人成功地说服了Python核心开发人员，证明Python元组哈希方法确实存在问题。 :-) 希望你不介意！然而，你仍然不应该使用哈希来代替相等性测试。最多只能用它来证明相反的情况（产生不同哈希值的两个值必须是不相等的，但反过来并不总是成立）。 - Martijn Pieters

直到现在才看到 - 谢谢Martijn！自那以后，我已经转向更好的编码实践，非常感谢你。 - pierre

Answer 1

在 Python 3.8 之前，元组的哈希值基于内容的哈希值计算，使用以下公式（来自 tuplehash() 函数）：

Py_uhash_t mult = _PyHASH_MULTIPLIER; /* defined as 1000003UL == 0xf4243 */
x = 0x345678UL;
p = v->ob_item;
while (--len >= 0) {
    y = PyObject_Hash(*p++);
    if (y == -1)
        return -1;
    x = (x ^ y) * mult;
    /* the cast might truncate len; that doesn't change hash stability */
    mult += (Py_hash_t)(82520UL + len + len);
}
x += 97531UL;
if (x == (Py_uhash_t)-1)
    x = -2;
return x;

这是一种被称为FNV-1（Fowler / Noll / Vo）哈希方法的方法。

恰好，该公式对于（1，0，-1）和（1，-1，0）产生完全相同的输出：

>>> hash((1, -1, 0))
-2528505496374624146
>>> hash((1, 0, -1))
-2528505496374624146

因为这3个整数的哈希值分别是1、0和-2：

>>> hash(1)
1
>>> hash(0)
0
>>> hash(-1)
-2

并且交换0和-2对结果没有实际影响。

因此，这3个包含的元组的哈希值在两个示例之间不会改变，因此最终的哈希值也不会改变。

这只是一个巧合，在实践中，我认为这种情况并不经常发生，字典和集合已经可以很好地处理冲突。

然而，在撰写原始答案几年后，事实证明我的期望是错误的！上述的tuplehash()实现已经使用了14年，直到有人坚持认为该方案存在问题。结果发现，某些值的组合（例如4和-4或0.25和0.5）大大降低了该方法可能输出的哈希值：

>>> import sys; from itertools import product
>>> sys.version_info
sys.version_info(major=3, minor=7, micro=7, releaselevel='final', serial=0)
>>> values = (0.25, 0.5)
>>> sum(1 for _ in product(values, repeat=20))  # 20 elements in each tuple
1048576
>>> len(set(map(hash, product(values, repeat=20))))
32

上面的代码创建了所有可能的20个值的元组，这些值组合了0.25和0.5。理想情况下，它们都应该具有不同的哈希值，或者至少具有非常多的不同哈希值。但是上述tuplehash()函数仅生成了32个唯一值。每个这32个唯一哈希值都适用于32768（2 ** 15）个这样的组合。

>>> from collections import Counter
>>> Counter(Counter(map(hash, product(values, repeat=20))).values())
Counter({32768: 32})

这实际上是一个相当大的问题！上述问题也适用于1，-1，0，只是没有那么明显。这里使用3 ** 12 == 531441组合进行测试：

>>> values = (1, -1, 0)
>>> sum(1 for _ in product(values, repeat=12))
531441
>>> len(set(map(hash, product(values, repeat=12))))
238605
>>> Counter(Counter(map(hash, product(values, repeat=12))).values())
Counter({1: 153005, 2: 51006, 4: 21730, 8: 8424, 16: 3012, 32: 994, 64: 314, 128: 92, 256: 20, 512: 6, 1024: 2})

因此，这些12元组生成的153005个哈希值中，全部使用了单个哈希。

因此，在Python 3.8中，实现已从FNV-1a切换到了xxHash快速摘要方案的一种改编。有关详细信息，请参见新的tuplehash()函数实现。

这种新方法在您问题中的示例中表现出色：

>>> sys.version_info
sys.version_info(major=3, minor=8, micro=1, releaselevel='final', serial=0)
>>> hash((1, -1, 0))
426056430309831993
>>> hash((1, 0, -1))
-7823806182320511195
>>> hash(((1, -1, 0), (1, 0, 0), (1, 0, -1)))
-6252168277346219339
>>> hash(((1, 0, -1), (1, 0, 0), (1, -1, 0)))
-5221381175350594014

除了我上面讨论的病理情况之外：

>>> values = (0.25, 0.5)
>>> len(set(map(hash, product(values, repeat=20))))
1048576
>>> values = (1, -1, 0)
>>> len(set(map(hash, product(values, repeat=12))))
531441

- Martijn Pieters

---

请注意，Py3.8引入了一种不同的算法来哈希元组：https://bugs.python.org/issue34751（有关哈希值不必唯一的论点仍然成立！） - Tomasz Gandor

@TomaszGandor：再次感谢您提供的链接。我已经看到了实现方式已经改变，但是忘记了这个答案。我现在已经扩展它以显示之前元组哈希函数确实存在问题。 - Martijn Pieters

Answer 2

似乎很奇怪，但无论如何都不要使用hash：https://docs.python.org/2/library/functions.html#hash “[hash用于]在字典查找期间快速比较字典键。”

它实际上并不是为了通用哈希而设计的 - 字典在简单哈希相等之外还有额外的检查。对于通用哈希，请使用hashlib。

- dave mankoff