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 (代码的作者)插话，否则我们永远无法确定;-)但是这些事情中通常没有那么“科学”：你采取一些一般原则和测试套件，几乎任意地篡改常量，直到结果看起来“足够好”为止。

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

1. 要获得所需的快速“位分散”，您需要乘一个大整数。因为CPython的散列结果必须适合许多平台上的32位，所以需要32位的整数才是最好的。事实上，还有(3644798167).bit_length() == 32。
2. 为了避免系统地丢失低阶位，您需要乘一个奇数。3644798167是奇怪的。
3. 更广泛地说，为了避免输入散列中的复合模式，您需要用素数进行乘法。3644798167是素数。
4. 你还想要一个乘法器，它的二进制表示没有明显的重复模式。bin(3644798167) == '0b11011001001111110011010011010111'。真是一团糟，这是件好事-)

其他常量在我看来完全是武断的。这个

if h == -1:
    h = 590923713

需要部分是因为另一个原因:在内部，CPython将整数值C函数中的-1返回值作为“异常需要引发”的意思；也就是说，它是一个错误返回。因此，您将永远不会看到-1的散列代码用于CPython中的任何对象。返回的值(而不是-1 )完全是任意的--每次都需要相同的值(而不是-1)。

编辑:绕着玩

我不知道雷蒙德过去是怎么测试这个的。下面是我应该使用的内容:查看一组连续整数的所有子集的散列统计信息。这些都是有问题的，因为hash(i) == i用于许多整数，i。

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

简单的xor‘hashes在一起将产生对这样的输入的大规模取消。

因此，这里有一个小函数来生成所有子集，另一个函数用于对所有哈希代码执行一个非常简单的xor：

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

呀！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

到处玩！这些都很有趣-)

Answer 2

正在解决的问题是，以前在Lib/sets.py中的散列算法在一些图算法(其中节点表示为frozensets)中出现的数据集上具有可怕的性能：

# Old-algorithm with bad performance

def _compute_hash(self):
    result = 0
    for elt in self:
        result ^= hash(elt)
    return result

def __hash__(self):
    if self._hashcode is None:
        self._hashcode = self._compute_hash()
    return self._hashcode

提出了一种新的算法，因为它具有更好的性能。这里概述了新算法的主要部分：

1) h ^= (hx ^ (hx << 16) ^ 89869747) * 3644798167中的xor-相等是必要的，因此算法是交换性 (散列不取决于遇到set元素的顺序)。由于sets具有无序的等式测试，所以frozenset([10, 20])的哈希必须与frozenset([20, 10])相同。

2)选择具有89869747的xor作为其有趣的比特模式101010110110100110110110011，用于在被随机选择的大素数与另一个有趣的位模式相乘之前分解邻近哈希值的序列。

3)包含了带有hx << 16的xor，使得较低的比特有两次机会影响结果(从而使附近的哈希值更好地分散)。在这种情况下，我受到了CRC算法如何将比特移回自己的启发。

4)如果我没记错的话，唯一一个特殊的常量是69069。它有一些来自线性同余随机数发生器世界的历史。有关一些参考资料，请参阅https://www.google.com/search?q=69069+rng。

5)增加了计算hash = hash * 69069U + 907133923UL的最后一步，以处理嵌套冻结集的情况，并使算法分散成与其他对象(字符串、元组、int等)的哈希算法正交的模式。

6)其它常数大多是随机选取的大素数。

虽然我想宣称哈希算法得到了神圣的启示，但现实是我获取了一堆性能不佳的数据集，分析了它们的散列不散的原因，然后玩弄该算法，直到碰撞统计数据不再如此尴尬。

例如，下面是来自Lib/ test /test_set.py的有效性测试，对于扩散较少的算法来说，它失败了：

def test_hash_effectiveness(self):
    n = 13
    hashvalues = set()
    addhashvalue = hashvalues.add
    elemmasks = [(i+1, 1<<i) for i in range(n)]
    for i in xrange(2**n):
        addhashvalue(hash(frozenset([e for e, m in elemmasks if m&i])))
    self.assertEqual(len(hashvalues), 2**n)

其他失败示例包括字符串和小整数范围的强大集以及测试套件中的图形算法:参见Lib/ test /test_set.py中的TestGraphs.test_cuboctahedron和TestGraphs.test_cube。

Answer 3

在……里面

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

乘法整数是减少碰撞的一个大素数。这一点特别相关，因为操作是在模块化下进行的。

其余的可能是任意的；我认为89869747没有具体的理由。最重要的用法是放大小数字的散列(大多数整数散列本身)。这防止了小整数集的高碰撞。

这就是我所能想到的。你要这个做什么？