python - 元组的哈希函数如何工作

Question

根据我对 Python 的理解，由于元组是不可变的，因此它们应该是可散列的，并且 hash() 函数应该对它们起作用。然而，情况似乎并非如此，因为当它们包含诸如列表或字典之类的项目时，散列函数会如下所示发出警告。

这个有效:

>>> t = (1, 2, 'name', 'Subhayan', 'age', 32, 'sex', 'male')
>>> hash(t)
3584505648807432737

这不起作用:

>>> t = ({'First': 1, 'second': 2}, 'age', 32, 'sex', 'male', 'name', 'Subhayan')
>>> hash(t)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'dict'

所以我的问题是哈希函数在内部是如何运行的？它是否循环遍历元组并尝试散列各个组件？

有人可以给我一些关于它如何工作的引用吗。

Answer 1

是的，不可变容器的哈希采用所包含对象的哈希。

对于元组，请参阅 Objects/tupleobject.c 源代码，特别是 tuplehash function:

static Py_hash_t
tuplehash(PyTupleObject *v)
{
    Py_uhash_t x;  /* Unsigned for defined overflow behavior. */
    Py_hash_t y;
    Py_ssize_t len = Py_SIZE(v);
    PyObject **p;
    Py_uhash_t mult = _PyHASH_MULTIPLIER;
    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;
}

在 Python 中，忽略 C int 类型溢出，等价于:

_PyHASH_MULTIPLIER = 1000003  # from pyhash.h

def tuplehash(v):
    x = 0x345678
    mult = _PyHASH_MULTIPLIER
    l = len(v)
    for i, ob in enumerate(v, 1):
        y = hash(ob)
        x = ((x ^ y) * mult)
        mult += (82520 + 2 * (l - i))
    x += 97531
    return x

“魔数(Magic Number)”用于确保元组哈希为内容哈希中的微小变化生成范围广泛的值。

毕竟这是最合乎逻辑的实现；散列应该反射(reflect)包含的值，并且当您测试与另一个元组的相等性时，包含的值也会针对另一个元组中的对象进行测试；散列和相等功能密切相关。

元组可以引用任何类型的对象；元组本身不能改变，但这并不意味着你不能改变它所引用的对象。因此，元组的可哈希性取决于元组引用的对象的可哈希性。