在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

元组的哈希基于内容的哈希值,使用以下公式(来自tuplehash()函数):

long mult = 1000003L;
x = 0x345678L;
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 += (long)(82520L + len + len);
}
x += 97531L;
if (x == -1)
    x = -2;
return x;

碰巧,该公式为(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个元组的散列在两个示例之间不会发生变化,因此最终散列也不会改变.

这仅仅是一个巧合,在实践中这种情况不会发生所有这往往和字典套已经可以处理冲突就好了.