为什么在指定精确容量时 HashMap 再次调整大小（）？

Question

代码胜于雄辩，所以：final int size = 100;Map<Integer, String> m = new HashMap<>(size);for (int i = 0; i < size; i++) m.put(i, String.valueOf(i));为什么 HashMap 内部调用时间！resize() 21 2（感谢 Andreas 发现 JVM 在内部使用 HashMaps，21 个 cals 中有 19 个来自其他进程）resize()我的应用程序仍然不能接受两次调用。我需要优化这个。如果我是一个新的 Java 开发人员，我对 HashMap 构造函数中的“容量”意味着什么的第一个直观猜测是，它是我（HashMap 的使用者）将要放入 Map 的元素数量的容量。但是这是错误的。如果我想优化我对 HashMap 的使用，以便它根本不需要调整自身大小，那么我需要足够密切地了解 HashMap 的内部结构，以准确了解 HashMap 存储桶数组需要有多稀疏。这在我看来很奇怪。HashMap 应该隐式地为你做这件事。这是 OOP 中封装的全部要点。注意：我已经确认 resize() 是我的应用程序用例的瓶颈，所以这就是为什么我的目标是减少对 resize() 的调用次数。问题：如果我知道条目的确切数量，我将事先放入地图中。我选择什么容量，以防止任何额外的呼叫resize()操作？像size * 10什么？我还想了解为什么HashMap以这种方式设计的一些背景知识。编辑：我经常被问到为什么这种优化是必要的。我的应用程序在 hashmap.resize() 中花费了大量 CPU 时间。我的应用程序使用的哈希映射的初始化容量等于我们放入其中的元素数量。因此，如果我们可以减少 resize() 调用（通过选择更好的初始容量），那么我的应用程序性能就会提高。

Answer 1

默认的负载因子是0.75，即3/4，这意味着在添加了 100 个值中的 75 个时，将调整内部哈希表的大小。

仅供参考： resize()只调用了两次。一次是在添加第一个值时，一次是在它达到 75% 时。

为了阻止调整大小，你需要确保第100价值不会引起调整，即size <= capacity * 0.75又名size <= capacity * 3/4又名size * 4/3 <= capacity，所以可以肯定的：

capacity = size * 4/3 + 1

随着size = 100，这意味着capacity = 134。

Answer 2

如有疑问，请阅读文档。文档很好地HashMap解释了initial capacity和 的权衡load-factor。

根据文档，如果initCapacity = (maxEntries / loadFactor) + 1添加条目时不会发生重新哈希操作。在这种情况下，maxEntries是100您指定的，loadFactor将是 的默认负载因子.75。

但是除了设置初始大小以避免重新散列 ( resize()) 之外，您还应该仔细阅读 的文档HashMap以正确调整它，同时考虑初始容量和负载因子。

如果您更关心查找成本而不是空间，那么如果您愿意，可以尝试使用较低的loadFactors.5或较低的s 。在这种情况下，您将使用两个参数创建哈希映射，如下所示：

final float loadFactor = 0.5;

final int maxEntries   = 100;

final int initCapacity = (int) maxEntries / loadFactor + 1;

new HashMap<>(initCapacity, loadFactor);

（强调我的）

HashMap 的实例有两个影响其性能的参数：初始容量和负载因子。容量是哈希表中的桶数，初始容量就是哈希表创建时的容量。负载因子是衡量哈希表在其容量自动增加之前允许达到多满的指标。当哈希表中的条目数超过负载因子和当前容量的乘积时，重新哈希表（即重建内部数据结构），使哈希表具有大约两倍的桶数。

...

作为一般规则，默认负载因子 (.75)在时间和空间成本之间提供了一个很好的权衡。较高的值会减少空间开销，但会增加查找成本（反映在 HashMap 类的大多数操作中，包括 get 和 put）。在设置其初始容量时，应考虑地图中的预期条目数及其负载因子，以尽量减少重新哈希操作的次数。如果初始容量大于最大条目数除以负载因子，则不会发生重新哈希操作。

Answer 3

这里有很多精彩的答案。我非常感谢这些贡献。

我决定不再重新发明这个轮子，因为看起来谷歌已经解决了这个问题。

我将使用实用方法Maps.newHashMapWithExpectedSize(int)，从谷歌的番石榴库