皮尔逊完美哈希

Question

我想写产生皮尔逊完美哈希发电机。请注意，我不需要最小的完美散列。维基百科说，使用随机算法（其中S是密钥集合）可以在O（| S |）时间找到Pearson完美哈希。但是，我一直无法在网上找到这样的算法。这甚至有可能吗？

注意：我不想用的gperf/CMPH /等，我宁愿写我自己的实现。

Answer 1

皮尔森original paper概述了一种算法构建置换表牛逼完美哈希：

在这个新的散列函数的心脏表牛逼有时可以进行修改，以产生最小的，完美的哈希函数在一个适度的单词列表上。实际上，通常可以为特定的单词选择函数的确切值。例如，Knuth的[3]示出了具有31个常见英语单词的列表映射到唯一整数− 10和30的表格Ť于表II中映射这些相同的31个词到从1之间的整数的算法完美散列到按字母顺序排列。

虽然表II构建数据表的过程是太涉及到在此详述，下面的亮点将让有兴趣的读者重复上述过程：

1. 一个表牛逼被构建整数的伪随机置换（0 ... 255）。
2. 一个接一个，所希望的值被分配到该列表中的话。每个任务都是通过交换表中的两个元素来实现的。
3. 对于每个单词，考虑用于交换第一候选是Ť [ħ [Ñ − 1] ⊕ Ç [Ñ]，最后的表元素中的散列的计算参考这个词的功能。
4. 甲表元素不能如果它先前分配的字的散列过程中引用或交换，如果它先前在相同的字的散列引用。
5. 如果必要的交换是由规则4禁止，人们的注意力转移到先前引用的表元素，Ť [H [Ñ − 2] ⊕ Ç [Ñ − 1]]。

的过程并不总是成功的。例如，如果使用ASCII字符代码，如果单词“a”散列为0并且单词“i”散列为15，则表明单词“in”必须散列为0.初始尝试将Knuth的31个单词映射到正因为这个原因，整数（0 ... 30）失败。转移到范围（1 ... 31）是解决这个问题的特别策略。

这样篡改T是否会损害散列函数的统计行为？不认真。当26,662字典条目被散列成256个分档时，所得到的分布与统一分布仍然没有显着差异（χ 2 = 266.03,255 d.f.，p = 0.30）。对128个随机选择的字典单词进行散列会导致平均27.5次碰撞，而对未修改的T的平均值为26.8次。当如上所述扩展该函数以产生16位散列索引时，相同的测试产生大量更多的冲突（与未修改的4,870比4,721相比），尽管分布仍然与统一（χ）没有显着不同2 = 565.2,532 df，，p = = 0.154）。