Python frozenset哈希算法/实现

除非Raymond Hettinger(代码的作者)插话,否则我们永远不会知道;-)但是这些东西通常没有你想象的那么"科学":你采用一些一般原则,一个测试套件,并且常数几乎是任意的,直到结果看起来"足够好".

一些一般原则"显然"在这里工作:

要获得所需的快速"位色散",您需要乘以一个大整数.由于CPython的散列结果必须在许多平台上适合32位,因此需要32位的整数才是最佳选择.而且,的确如此(3644798167).bit_length() == 32.

为避免系统地丢失低位,您希望想要乘以奇数.3644798167很奇怪.

更一般地说,为了避免在输入哈希中复合模式,您希望乘以素数.并且3644798167是素数.

而且你还想要一个乘法器,它的二进制表示没有明显的重复模式. 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

简单地xor'ing哈希将在这样的输入上产生大量的消除.

所以这里有一个小函数来生成所有子集,另一个是在所有哈希码上做一个简单的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

哎呀!_hash()在这种情况下,OTOH使用专为frozensets设计的完美工作:

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

玩转!这些东西很有趣:-)

正在解决的问题是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)xor-equal in h ^= (hx ^ (hx << 16) ^ 89869747) * 3644798167是必要的,因此算法是可交换的(散列不依赖于遇到集合元素的顺序).由于集合具有无序的相等性测试,因此散列frozenset([10, 20])需要与for相同frozenset([20, 10]).

2)89869747选择xor with 是因为它有趣的位模式101010110110100110110110011用于在乘以之前分解附近散列值的序列3644798167,随机选择的大素数与另一个有趣的位模式.

3)hx << 16包含xor with ,使得较低位有两次机会影响结果(导致附近散列值更好地分散).在这一点上,我的灵感来自于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.