为什么增加哈希表的大小会减少冲突次数？

Question

根据我在网上看到的，有两种减少碰撞次数的方法：

1. 使用更好的散列函数
2. 增加哈希的大小table

我能理解第一个原因，但我似乎无法理解第二个原因。

假设我有 5 个密钥，它们的哈希值都相同。假设我们正在使用链接来解决冲突。所有 5 个键将形成一条链，从等于哈希值的索引开始。现在，假设我将 table 的大小加倍并重新散列所有 5 个键。这 5 个键将 still 散列到相同的索引并将 still 形成大小 5 的变化。如何增加散列的大小 table 减少碰撞？

Answer 1

这是因为在计算散列的同时，还要考虑数组的大小。因此，如果数组大小很大，在计算散列时，它需要更大的模值。

例如：
假设如果数组大小是 3 并且传递值是 2 和 5
然后 2%3 和 5%3 放在同一个地方，即 1.

现在以数组大小 5
为例 然后 2%5 和 5%5 分别占据不同的位置，即 2 和 0。

所以随着 hash table size 的增加，碰撞次数减少。
希望这个解释对你有帮助。

Answer 2

我想通了。

Hashing有两部分：散列函数和压缩函数。 更改散列的大小 table 将更改压缩函数，从而导致将密钥分配给不同的存储桶。