perl如何解决哈希中可能的哈希冲突？

Question

我们知道,perl将其'hash'类型实现为具有计算索引的表,其中这些索引是截断的哈希值.

我们也知道,散列函数可以(并且将通过概率)发生冲突,为2个或更多不同的输入提供相同的散列.

然后:当perl解释器发现密钥生成与另一个密钥相同的散列时,它如何处理？它完全处理它吗？

注意:这不是关于散列算法,而是关于散列表实现中的冲突解决方案.

Answer 1

Perl哈希是链表的数组.

+--------+       +--------+
|       -------->|        |
+--------+       +--------+
|        |       | key1   |
+--------+       +--------+
|      ------+   | val1   |
+--------+   |   +--------+
|        |   |
+--------+   |   +--------+     +--------+
             +-->|       ------>|        |
                 +--------+     +--------+
                 | key2   |     | key3   |
                 +--------+     +--------+
                 | val2   |     | val3   |
                 +--------+     +--------+

散列函数产生一个用作数组索引的值,然后执行相关链表的线性搜索.

这意味着查找的最坏情况是O(N).那么为什么人们会说它是O(1)？你可以声称,如果你保持列表不超过一定长度,那就是Perl所做的.它使用两种机制来实现这一目标:

• 增加桶的数量.
• 哈希算法扰动.

将桶的数量加倍应平均将给定的条目数除以一半.例如,

305419896 % 4 = 0 and 943086900 % 4 = 0
305419896 % 8 = 0 and 943086900 % 8 = 4

但是,恶意行为者可以选择不会发生这种情况的值.这是散列扰动发挥作用的地方.每个散列都有自己的随机数,它会扰乱(导致差异)散列算法的输出.由于攻击者无法预测随机数,因此他们无法选择会导致冲突的值.在需要时,Perl可以使用新的随机数重建哈希,导致键映射到不同的桶,从而分解长链.