负载因子和重新哈希

本篇文章主要是结合我之前面试的各种经历和实战开发中遇到的问题解决经验整理的，希望这篇《负载因子和重新哈希》对你有很大帮助！欢迎收藏，分享给更多的需要的朋友学习~

负载因子衡量哈希表的满度。如果超过加载因子，则增加哈希表大小并将条目重新加载到新的更大的哈希表中。这称为重新哈希。负载因子 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。每当负载因子超过阈值时，您就需要增加哈希表的大小，并将映射中的所有条目重新哈希到一个新的更大的哈希表中。请注意，您需要更改哈希函数，因为哈希表大小已更改。为了减少重新散列的可能性，因为它的成本很高，您应该至少将散列表大小增加一倍。即使定期重新散列，散列也是映射的有效实现。

好了，本文到此结束，带大家了解了《负载因子和重新哈希》，希望本文对你有所帮助！关注golang学习网公众号，给大家分享更多文章知识！