hash() 如何计算元组的哈希值？

Question

函数hash()如何计算元组的哈希值？例如：

t = (1,2,3)
print(hash(t))

给出输出

-378539185

Answer 1

如果您熟悉 C 编程和一些高等数学，您可以查看 implementation of this function in C。似乎算法对元组中的每个元素进行异或哈希并增加了一些魔力。

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;
}

请注意，这是 CPython 的当前实现。其他 Python 解释器甚至其他版本的 CPython 可能具有不同的散列函数。这种称为 SipHash 的特定实现自 2013 年以来一直在使用。有关详细说明，请参阅 PEP 456 -- Secure and interchangeable hash algorithm。

SipHash is a cryptographic pseudo random function with a 128-bit seed and 64-bit output.... SipHash is a family of pseudorandom functions (a.k.a. keyed hash functions) optimized for speed on short messages. Target applications include network traffic authentication and defense against hash-flooding DoS attacks.

Answer 2

standard library documentation 有一点细节。哈希函数一般具有以下性质：

如果两个值相等，则它们总是具有相同的散列值；和
如果两个值不同，则它们可能具有不同的哈希值。

写这些有更简单和更难的方法，也有更快和更慢的方法，但重要的是不同的值很少产生相同的哈希值。一个好的是棘手的，但你通常不关心实现。

（在 Python 中，您几乎不需要直接调用 hash()；如果它是用作键的自定义类型的字典实现的一部分，我不会感到惊讶。Object.__hash__() documentation 说的比较多。）

hash() 如何计算元组的哈希值？

How does hash() compute the hash of a tuple?

python

hashcode