0

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

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

但是负载因子如何帮助我确定是否应该调整表格大小并重新散列？我也找不到任何地方如何计算下/上负载因子。他们甚至需要吗？

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

4

2 回答 2

1

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

从概念上讲，区分是合理的

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

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

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

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

上述所有关注链式哈希，对于带有墓碑的开放寻址哈希，事情变得更加复杂。

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

对于链式哈希，非 2 的幂容量是多余的，除非您需要非常精确地控制内存使用（你不需要，相信我）或 2^30 和 2^31-1 之间的容量（因为你不能在 Java 中创建一个大小为 2^31 的数组，它是Integer.MAX_VALUE+ 1)。

于 2014-05-02T23:43:11.443 回答
0

反之亦然：不是负载因子对您有帮助；您根据性能测试明确决定负载因子，以避免浪费时间重新散列并仍然具有可接受的检索和迭代性能。

于 2014-05-02T19:49:29.327 回答