27

我目前正在尝试了解为 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
4

3 回答 3

42

正在解决的问题是Lib/sets.py中以前的哈希算法在许多图形算法中出现的数据集上具有可怕的性能（其中节点表示为freezesets）：

# 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) xor-equal inh ^= (hx ^ (hx << 16) ^ 89869747) * 3644798167是必要的，这样算法是可交换的（哈希不依赖于遇到集合元素的顺序）。由于 sets 具有无序相等性测试，因此 for 的哈希值frozenset([10, 20])需要与 for 相同frozenset([20, 10])。

2) 选择 xor89869747是因为其有趣的位模式101010110110100110110110011，用于在乘以 之前分解附近哈希值的序列3644798167，随机选择的大素数与另一个有趣的位模式。

3) 包含 xor 以hx << 16使低位有两次机会影响结果（导致附近哈希值更好地分散）。在这篇文章中，我受到了CRC 算法如何将位重排回自身的启发。

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

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

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。

于 2014-01-05T08:13:47.670 回答
32

除非 Raymond Hettinger（代码的作者）插话，否则我们永远无法确定 ;-) 但这些东西中的“科学”通常比您预期的要少：您采用一些一般原则和一个测试套件，然后摆弄常数几乎是任意的，直到结果看起来“足够好”。

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

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

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

  3. 更一般地，为了避免输入哈希中的复合模式，您希望乘以一个素数。而 3644798167 是素数。

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

其他常数在我看来完全是任意的。这

if h == -1:
    h = 590923713

需要 part 的另一个原因是：在内部，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

哎呀！OTOH，_hash()在这种情况下，使用为frozensets 设计的功能非常出色：

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

然后你可以用它来看看有什么 - 什么 - 没有 - 在_hash(). 例如，它仍然在这些输入上做得很好，如果

    h = h * 69069 + 907133923

已移除。我不知道为什么那条线在那里。同样，如果内部循环中的 in 被删除，它会继续在这些输入上做得很好^ 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

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

于 2013-12-30T04:18:04.700 回答
4

在

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

乘法整数是减少冲突的大素数。这一点尤其重要，因为该操作是在模下进行的。

其余的可能是任意的；我认为没有理由89869747要具体。你会得到的最重要的用途是扩大小数字的散列（大多数整数散列到它们自己）。这可以防止小整数集的高冲突。

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

于 2013-12-30T03:51:38.103 回答