hash - 皮尔逊完美哈希

Question

我正在尝试编写一个生成 Pearson 完美哈希的生成器。请注意，我不需要最小的完美哈希。维基百科说，可以使用随机算法（其中 S 是密钥集）在 O(|S|) 时间内找到 Pearson 完美哈希。但是，我一直无法在网上找到这样的算法。这甚至可能吗？

注意：我不想使用 gperf/cmph/etc.，我宁愿编写自己的实现。

Answer 1

Pearson 的原始论文概述了一种构造置换表T以实现完美散列的算法：

有时可以修改这个新散列函数的核心表T ，以在适度的单词列表上生成最小的、完美的散列函数。事实上，人们通常可以为特定单词选择函数的确切值。例如，Knuth [3] 用一种算法说明了完美散列，该算法将 31 个常见英语单词列表映射到 -10 到 30 之间的唯一整数。表 II 中的表T将这 31 个相同的单词映射到 1 到 31 的整数按字母顺序。

虽然构建表二中的表格的过程过于复杂，此处无法详述，但以下重点将使感兴趣的读者重复该过程：

1. 表T由整数 (0 ... 255) 的伪随机排列构成。
2. 将所需的值一一分配给列表中的单词。每个分配都是通过交换表中的两个元素来实现的。
3. 对于每个单词，考虑交换的第一个候选词是T [ h [ n - 1] ⊕ C [ n ]]，这是在计算该单词的哈希函数时引用的最后一个表元素。
4. 如果一个表元素在之前分配的词的散列期间被引用，或者如果它在同一个词的散列中被更早地引用，则无法交换表元素。
5. 如果规则 4 禁止了必要的交换，则注意力转移到先前引用的表元素T [h[ n - 2] ⊕ C [ n - 1]]。

该过程并不总是成功的。例如，使用 ASCII 字符代码，如果单词“a”散列为 0，单词“i”散列为 15，结果表明单词“in”必须散列为 0。最初尝试将 Knuth 的 31 个单词映射到整数 (0 ... 30) 正是由于这个原因而失败的。转移到范围 (1 ... 31) 是规避此问题的临时策略。

这种对T的篡改是否会破坏散列函数的统计行为？不认真。当 26,662 个字典条目被散列到 256 个 bin 中时，得到的分布与均匀分布仍然没有显着差异（χ² = 266.03, 255 df, p = 0.30）。对 128 个随机选择的字典单词进行散列处理后，平均发生 27.5 次冲突，而未修改的T则为 26.8 次。当此函数按上述方式扩展以产生 16 位哈希索引时，相同的测试会产生更多的冲突（4,870 与未修改的T的 4,721 相比），尽管分布与均匀分布仍然没有显着差异 (χ² = 565.2 , 532 df, p = 0.154)。