Python freezeset 散列算法/实现

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;
}

还有一个 equivalent implementation in 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

正在解决的问题是，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 中的异或相等是必要的，因此算法是 commutative (散列不依赖于遇到集合元素的顺序)。由于集合具有无序相等性测试，frozenset([10, 20]) 的哈希值需要与 frozenset([20, 10]) 相同.

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

3) 与 hx << 16 的异或被包括在内，以便低位有两次影响结果的机会(导致附近散列值更好地分散)。在此，我受到 CRC algorithms 的启发。重新洗牌。

4) 如果我没记错的话，唯一特殊的常量之一是 69069。它有一些来自 linear congruential random number generators 世界的历史。 .见 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。