在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))具有不同的哈希值。

关于发生了什么的任何线索？我简直不敢相信这真是太不可思议了……现在，我已经找到了问题所在，因此可以轻松地绕开它，但是我仍然认为在这里值得一提。

Answer 1

直到Python 3.8，元组的哈希是基于内容的哈希，使用以下公式（来自tuplehash() function：]]]

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) hash method和(1, 0, -1)产生了完全相同的输出：

(1, -1, 0)
因为包含的3个整数的散列为>>> hash((1, -1, 0))
-2528505496374624146
>>> hash((1, 0, -1))
-2528505496374624146
，1和0：

-2
并且交换>>> hash(1)
1
>>> hash(0)
0
>>> hash(-1)
-2
和0对结果没有实际影响。

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

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

但是，在写完我的原始答案几年后，事实证明我的期望被放错了！上述-2实施已实施14年，直到tuplehash()为止。事实证明，某些值

组合

（例如someone insisted that there was a problem with the scheme和4或-4和0.25）极大地降低了该方法可能输出的可能的哈希值：0.5

上面创建了所有1048576（2 ** 20 == 1024 ** 2）可能的20值元组，它们组合了>>> 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
和0.25。理想情况下，它们都应具有不同的哈希值，或者至少具有大量不同的哈希值。但是上面的0.5函数仅产生32个唯一值。这32个唯一的散列中的每一个都适用于32768（2 ** 15）个这样的组合：
tuplehash()

这实际上是一个很大的问题。上面的问题也出现在>>> from collections import Counter
>>> Counter(Counter(map(hash, product(values, repeat=20))).values())
Counter({32768: 32})
中，只是不那么明显。在这里用3 ** 12 == 531441组合进行测试：
1, -1, 0

所以为这12个元素的元组生成的哈希中的153005全部都使用单个哈希。

因此在Python 3.8中，从FNV-1a的>>> 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})
到implementation was switched的改编。有关详细信息，请参见xxHash fast digest scheme。
此新方法在您的问题示例中表现出色：

new tuplehash() function implementation

以及我上面讨论的病理病例：

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
[[哈希]用于在字典查找期间快速比较字典关键字。
它实际上不是用于通用哈希的-字典除了具有简单的哈希相等性以外，还具有其他检查功能。对于通用哈希，请使用hash

Answer 2

[[哈希]用于在字典查找期间快速比较字典关键字。