Python 冻结集合哈希算法/实现

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

- Rufflewind

---

编辑：我删除了关于哈希组合函数为什么是可交换和可结合的问题：由于分散元素哈希与累加器进行异或运算，所以它必须是可交换和可结合的，因为异或运算是如此！我太傻了。 - Rufflewind

Answer 1

问题的解决是在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-equal是必要的，这样算法才是可交换的（哈希不依赖于集合元素遇到的顺序）。由于集合具有无序相等性测试，因此对于frozenset([10, 20])的哈希值需要与frozenset([20, 10])的哈希值相同。

2）选择使用89869747进行异或是因为它的有趣位模式为101010110110100110110110011，用于在乘以另一个有趣位模式的随机选择的大质数3644798167之前打破附近哈希值的序列。

3) 包含对 hx << 16 进行异或的原因是为了使低位有两次机会影响结果（从而获得更好的附近哈希值分散）。在这方面，我受到了 CRC算法 如何将位重新洗回自身的启发。

4) 如果我记得正确，唯一一个特殊的常数是 69069。它在 线性同余随机数生成器 的世界中有一些历史。请参见 https://www.google.com/search?q=69069+rng 获取一些参考资料。

5) 计算 hash = hash * 69069U + 907133923UL 的最后一步被添加以处理嵌套 frozensets 的情况，并使算法在与其他对象的哈希算法（字符串、元组、整数等）正交的模式下分散。

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。

- Raymond Hettinger

---

我在这个过程中向 Raymond 提供了一些测试代码。对于各种集合嵌套模式，它会随机生成数千个集合，并将碰撞数量与理想哈希的预期数量进行比较。我还提供了一个初始哈希实现，它与 Raymond 的实现类似，但步骤更多，常数选择不够精细。Raymond 的最终结果在速度和简洁性方面有了显著提高，并且在随机性测试方面表现几乎一样好。 - Yitz

对于一个multiset，如果以Set._hash(['a', 'a', b'])的形式使用该算法，是否会失败？重复元素会对其产生影响吗？ - JamesTheAwesomeDude

@JamesTheAwesomeDude 你是对的，Set._hash 不适用于多重集合。然而，它很容易修改。对于多重集合，只需改变元素哈希值以包含元素的计数：hx = hash(x) → hx = hash((x, cnt))。 - Raymond Hettinger

@RaymondHettinger 这样做是否合适，将一个常量混入以防止不同类型之间的冲突（例如 hash(frozenset({('a', 2), ('b', 1)})) == hash(FrozenMultiset(['a', 'a', 'b']))）？类似于 Set._hash({self.__HASH_CONSTANT}.union(self._impl_dict.items())) 这样的方式，其中常量是一个简单的一次性 object()，似乎能够产生可用的结果，并且我没有看到任何明显的问题出现... - JamesTheAwesomeDude

Answer 2

除非代码作者Raymond Hettinger发表意见，否则我们永远不会确定；-)但通常这些事情中的“科学”要比你想象的少：你采用一些通用原则和测试套件，并且几乎是任意地调整常量，直到结果看起来“足够好”。

这里明显起作用的一些通用原则：

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

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

3.更一般地说，为了避免在输入哈希中复合模式，您需要乘以一个质数。而3644798167是质数。

4.您还需要一个二进制表示法没有明显重复模式的乘数。bin(3644798167) == '0b11011001001111110011010011010111'。那很混乱，这是一件好事；-)

其他常量对我来说看起来完全是任意的。

if h == -1:
    h = 590923713

这个部分还有另一个原因：在内部，CPython将从整数值C函数返回的-1视为“需要引发异常”，也就是说，这是一个错误返回。因此，在CPython中，您永远不会看到任何对象的哈希代码为-1。取而代之的是返回一个完全任意的值 - 它只需要每次都与-1不同。

编辑：玩耍

我不知道Raymond用什么来测试这个。这是我会用的方法：查看一组连续整数的所有子集的哈希统计信息。这些数据有问题，因为对于很多整数i，hash(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

哎呀！然而，在这种情况下，使用为frozensets设计的_hash()函数完美地完成了工作：

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

那么，你可以尝试一下，看看在_hash()中什么会产生真正的区别，什么不会。例如，如果这些输入仍然可以完美地完成任务：

    h = h * 69069 + 907133923

被移除了。我不知道为什么会有那一行代码。同样地，如果内部循环中的^ 89869747被移除，它仍然可以完美地处理这些输入 - 我也不知道那是为什么。初始化可以改为：

    h = 1927868237 * (n + 1)

to:

    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

玩得开心！这些东西很有趣 :-)

- Tim Peters

---

谢谢你，我很感激你对算法的分析！ :) - Rufflewind

Answer 3

In

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

乘法整数是一个大质数，可以减少碰撞。这尤其重要，因为操作是在模数下进行的。

其他部分可能是任意的；我看不出 89869747 具体的原因。你会从中获得最重要的用途是扩大小数字的哈希值（大多数整数哈希到它们自己）。这可以防止小整数集合的高碰撞率。

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

- Veedrac

---

主要是出于好奇。需要一种方法来哈希具有关联和可交换分支的树（即每个节点都是无序多重集：Data.HashMap），并想看看Python如何处理frozensets的哈希。 - Rufflewind