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

Question

众所周知，perl 将其“散列”类型实现为具有计算索引的表，其中这些索引是截断的散列。

我们也知道，散列函数可以（并且将根据概率）碰撞，将相同的散列提供给 2 个或更多不同的输入。

然后：当 perl 解释器发现一个键生成的散列值与另一个键相同时，它如何处理？它会处理它吗？

注意：这不是关于哈希算法，而是关于哈希表实现中的冲突解决。

标签： perlhashmap

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 可以使用新的随机数重建散列，使键映射到与以前不同的存储桶，从而分解长链。