负载因子和重新哈希

负载因子衡量哈希表的满度。如果超过加载因子，则增加哈希表大小并将条目重新加载到新的更大的哈希表中。这称为重新哈希。负载因子 l (lambda) 衡量哈希表的填充程度。是
数量的比例
元素与哈希表的大小，即 l = n / N，其中 n 表示元素的数量，N 表示哈希表中位置的数量。

请注意，如果哈希表为空，则 l 为零。对于开放寻址方案，l 介于 0 和 1 之间；如果哈希表已满，则 l 为1。对于单独的链接方案，l 可以是任何值。

随着 l 的增加，碰撞的概率也会增加。研究表明，对于开放寻址方案，您应该将负载因子保持在0.5以下，对于单独链接方案，您应该将负载因子维持在0.9以下。

将负载因子保持在一定阈值以下对于哈希的性能很重要。在 Java API 中java.util.HashMap类的实现中，使用了阈值0.75。每当负载因子超过阈值时，您就需要增加哈希表的大小，并将映射中的所有条目重新哈希到一个新的更大的哈希表中。请注意，您需要更改哈希函数，因为哈希表大小已更改。为了减少重新散列的可能性，因为它的成本很高，您应该至少将散列表大小增加一倍。即使定期重新散列，散列也是映射的有效实现。

以上就是负载因子和重新哈希的详细内容，更多请关注叮当号网其它相关文章！