java - 哈希表中的下/上负载因子

Question

我要用java编写一个链式哈希集类。

我知道负载系数是M/容量，其中M是表中当前元素的数量，容量是表的大小。

但是负载因子如何帮助我确定是否应该调整表大小并重新散列？此外，我在任何地方都找不到如何计算下/上负载系数。他们还需要吗？

我希望这是足够的信息，谢谢!!

Answer 1

用于配置标准 Java 哈希(以及其他语言的许多哈希 API)的单个 loadFactor 是一种简化。

从概念上来说，区分是合理的

• 目标负载，指示默认内存占用——性能权衡配置。当您构建已知大小的哈希时，您可以选择容量，以便大小/容量尽可能接近目标负载。

• 最大负载，您希望哈希永远不会超过此负载。如果哈希达到此负载，您将触发调整大小。

• 增长因子，在调整大小时将散列放大多少的默认配置。如果容量是 2 的幂，则增长因子只能是 2 或 4。

• 最小负载，您希望哈希负载永远不会低于最小负载，也许除非您删除元素或清除哈希。如果容量是2的幂，则最小负载不能大于0.5。此外，最大负载/最小负载比率应大于或等于增长因子。

以上所有内容都涉及链式哈希，对于带有逻辑删除的开放寻址哈希，事情变得更加复杂。

在java.util.HashMap中，loadFactor同时扮演目标负载和最大负载的角色。增长因子为 2，最小负载为 0.0。

对于链式哈希，非 2 的幂容量是过大的，除非您需要极其精确控制内存使用情况(您不需要，相信我)或 2^30 到 2 之间的容量^31-1(因为在 Java 中无法创建大小为 2^31 的数组，所以它是 Integer.MAX_VALUE + 1)。