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

Question

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

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

提供输出

-378539185

- Aditya Mandal

Answer 1

如果你熟悉C编程和一些高级数学，可以查看在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是一个具有128位种子和64位输出的加密伪随机函数。SipHash是一族伪随机函数（也称为键控哈希函数），针对短消息进行了速度优化。目标应用包括网络流量认证和防御哈希洪水DoS攻击。

- Lev Zakharov

---

重要的是，Python逐步获取元组中每个元素的哈希值，并将其组合成一个滚动哈希值，这个值成为最终结果。 - Alnitak

此外，上述的代码并不是核心的SipHash算法。 - Alnitak

那个最终溢出检查有什么用？你以(Py_uhash_t) -1的准确概率有多大，为什么在那一点上将其设为-2？ - user129393192

Answer 2

标准库文档提供了一些细节。哈希函数通常具有以下特性：

1. 如果两个值相等，则它们始终具有相同的哈希值；
2. 如果两个值不同，则它们可能具有不同的哈希值。

有更简单和更困难的编写方式，也有更快和更慢的方式，但重要的是不同的值很少产生相同的哈希值。一个好的哈希函数很棘手，但通常您并不深入关注实现。

（在Python中，您几乎从不需要直接调用hash()；如果它是用作键的自定义类型的字典实现的一部分，我不会感到惊讶。Object.__hash__()文档提供了更多信息。）

- David Maze

---

楼主要求关于如何计算元组哈希值的具体细节，而不是一般哈希函数的相关信息。 - Alnitak