Python Frozenset哈希算法/实现

Question

我目前正在尝试了解为Python的内置frozenset数据类型定义的哈希函数背后的机制。该实现显示在底部，以供参考。我特别感兴趣的是选择此分散操作的原理：

lambda h: (h ^ (h << 16) ^ 89869747) * 3644798167

h每个元素的哈希值在哪里。有人知道这些来自哪里吗？（也就是说，是否有任何特定的原因来选择这些数字？）还是只是简单地任意选择了它们？

这是来自官方CPython实现的代码片段，

static Py_hash_t
frozenset_hash(PyObject *self)
{
    PySetObject *so = (PySetObject *)self;
    Py_uhash_t h, hash = 1927868237UL;
    setentry *entry;
    Py_ssize_t pos = 0;

    if (so->hash != -1)
        return so->hash;

    hash *= (Py_uhash_t)PySet_GET_SIZE(self) + 1;
    while (set_next(so, &pos, &entry)) {
        /* Work to increase the bit dispersion for closely spaced hash
           values.  The is important because some use cases have many
           combinations of a small number of elements with nearby
           hashes so that many distinct combinations collapse to only
           a handful of distinct hash values. */
        h = entry->hash;
        hash ^= (h ^ (h << 16) ^ 89869747UL)  * 3644798167UL;
    }
    hash = hash * 69069U + 907133923UL;
    if (hash == -1)
        hash = 590923713UL;
    so->hash = hash;
    return hash;
}

以及Python中的等效实现：

def _hash(self):
    MAX = sys.maxint
    MASK = 2 * MAX + 1
    n = len(self)
    h = 1927868237 * (n + 1)
    h &= MASK
    for x in self:
        hx = hash(x)
        h ^= (hx ^ (hx << 16) ^ 89869747)  * 3644798167
        h &= MASK
    h = h * 69069 + 907133923
    h &= MASK
    if h > MAX:
        h -= MASK + 1
    if h == -1:
        h = 590923713
    return h

Answer 1

除非Raymond
Hettinger（代码的作者）陷入困境，否则我们将永远无法确定;-)但是，这些东西中的“科学”通常比您期望的要少：您采用一些通用原则，一个测试套件，然后对它们进行弄乱。常量几乎是任意的，直到结果看起来“足够好”为止。

一些通用原则“显然”在这里起作用：

1. 要获得所需的快速“位分散”，您需要乘以一个大整数。由于在许多平台上CPython的哈希结果必须适合32位，因此最好使用需要32位的整数。而且，的确(3644798167).bit_length() == 32。

2. 为避免系统地丢失低阶位，您需要乘以一个奇数整数。3644798167很奇怪。

3. 更一般而言，为避免在输入哈希中增加模式，您需要乘以质数。3644798167是质数。

4. 而且，您还需要一个乘法器，该乘法器的二进制表示形式没有明显的重复模式。 bin(3644798167) == '0b11011001001111110011010011010111'。那真是一团糟，这是一件好事;-)

在我看来，其他常量完全是任意的。的

if h == -1:
    h = 590923713

部分是由于另一个原因而需要的：在内部，CPython-1从整数值C函数获取一个返回值，表示“需要引发异常”；即，这是错误返回。因此，您将永远不会-1在CPython中看到任何对象的哈希码。返回的值而不是-1完全任意的-
每次只需要是 相同的 值（而不是-1）即可。

编辑：玩

我不知道雷蒙德用什么来测试。这是我将要使用的：查看一组连续整数的所有子集的哈希统计信息。这些是有问题的，因为hash(i) == i有很多整数i。

>>> all(hash(i) == i for i in range(1000000))
True

简单地将异或散列在一起将对此类输入产生大量抵消。

因此，这里有一个小函数可以生成所有子集，另一个函数是对所有哈希码进行简单的异或运算：

def hashxor(xs):
    h = 0
    for x in xs:
        h ^= hash(x)
    return h

def genpowerset(xs):
    from itertools import combinations
    for length in range(len(xs) + 1):
        for t in combinations(xs, length):
            yield t

然后是一个驱动程序，以及一个显示碰撞统计信息的小功能：

def show_stats(d):
    total = sum(d.values())
    print "total", total, "unique hashes", len(d), \
          "collisions", total - len(d)

def drive(n, hasher=hashxor):
    from collections import defaultdict
    d = defaultdict(int)

    for t in genpowerset(range(n)):
        d[hasher(t)] += 1
    show_stats(d)

使用简单易用的哈希器是灾难性的：

>> drive(20)
total 1048576 unique hashes 32 collisions 1048544

kes！OTOH_hash()在这种情况下使用专为冷冻食品设计的产品可以完美地完成工作：

>>> drive(20, _hash)
total 1048576 unique hashes 1048576 collisions 0

然后，您可以尝试使用该工具，看看究竟有什么作用-以及没有-真正的作用_hash()。例如，如果

    h = h * 69069 + 907133923

已移除。而且我不知道为什么会有那条线。同样，如果^ 89869747删除了内部循环中的，它将继续在这些输入上做完美的工作-
不知道为什么也是如此。初始化可以从以下方式更改：

    h = 1927868237 * (n + 1)

至：

    h = n

这里也没有伤害。所有这些都符合我的期望：由于已经说明的原因，至关重要的是内部循环中的乘法常数。例如，向其添加1（使用3644798168），然后它不再是质数或奇数，并且统计信息降级为：

total 1048576 unique hashes 851968 collisions 196608

仍然相当有用，但是绝对更糟。将其更改为较小的素数，例如13，更糟糕的是：

total 1048576 unique hashes 483968 collisions 564608

使用具有明显二进制模式（例如）的乘法器0b01010101010101010101010101010101，然后再次恶化：

total 1048576 unique hashes 163104 collisions 885472

玩吧！这些东西很有趣:-)