当指定精确容量时，为什么HashMap会再次调整大小(resize())？

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()2次！（Andreas指出JVM在内部使用HashMap，其中19个调用来自其他进程）两次resize()调用对于我的应用程序仍然不可接受。我需要优化这个问题。如果我是一个新的Java开发者，我第一直觉猜测HashMap构造函数中的"容量"是我(HashMap的消费者)要放入Map的元素数量的容量。但这是不正确的。如果我想优化我的HashMap使用，使其根本不需要重新调整大小，那么我需要非常熟悉HashMap的内部情况，以便准确地知道HashMap桶数组需要多么稀疏。在我看来，这很奇怪。HashMap应该为您隐式执行此操作。这是面向对象编程中封装的全部意义。注：我确认resize()是我的应用程序使用情况的瓶颈，所以我的目标是减少对resize()操作的调用次数。问题是:如果我预先知道我要放入地图的项目的确切数量，我选择什么容量，以防止任何额外的resize()操作？类似于size*10这样的东西？我也想了解一些为什么HashMap被设计成这样的背景知识。编辑：我被问了很多为什么这种优化是必要的。我的应用程序在hashmap.resize()中花费了相当多的CPU时间。我的应用程序使用的哈希图是用与我们放入其中的元素数量相等的容量初始化的。因此，如果我们可以减少resize()调用(通过选择更好的初始容量)，那么我的应用程序性能就会得到改善。

- James Wierzba

---

那个 HashMap 应该只需要调整一次大小，从初始容量 128 到最终容量 256。你是如何测量它在代码执行期间调整大小的次数的？ - Bobulous

你提供的这段代码在执行过程中调用了 21 次 resize() 函数，但是我们不清楚你是如何计算出这个数字的。仅编译代码肯定无法展示循环导致 HashMap 对象实际重新调整大小的次数。你采用了哪些方法来计算 resize() 实际被调用的次数？ - Bobulous

它被称为2次的问题是什么？第一次=第一次创建；第二次=因为负载因子为0.75-如果您知道有多少元素，请将负载因子更改为1.0（或将元素数量除以负载因子以获取初始容量） - user85421

如果您不希望它调整大小两次（技术上一次），那么要么指定更大的初始大小（~134），要么使用更高的负载因子创建它，顺便说一下，这是您不应该在没有仔细考虑其文档中描述的情况下进行调整的东西。 - Mark Rotteveel

而且你不需要深入了解内部细节，只需要阅读API文档。这种行为是其合同的一部分，不仅仅是实现细节。 - Mark Rotteveel

Answer 1

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

提示:resize()仅被调用两次。第一次在添加第一个值时，第二次在达到75%容量时。

为了防止调整大小，您需要确保第100个值不会导致调整大小，即size<= capacity * 0.75，也就是size<= capacity * 3/4，即size * 4/3 <= capacity，所以为了确保：

capacity = size * 4/3 + 1

如果 size = 100，那意味着 capacity = 134。

- Andreas

---

Andreas，resize()函数确实被调用了21次。也许函数在执行调整大小之前就退出了，我会进一步深入研究。 - James Wierzba

没错，这是一种节省内存的优化方法。测试结果表明，集合对象通常在没有添加值的情况下就被创建了，因此现在集合的初始容量非常小，只有在添加第一个元素时才会应用初始容量。 - Andreas

@JamesWierzba 如果您将100个元素添加到初始化容量为100的映射中，则resize()仅调用一次或两次。如果您创建一个仅包含问题中代码的小型测试程序，请注意JVM启动会创建其他 HashMap对象，因此不要计算所有这些其他对象上的resize()调用。只计算对m实例的调用。--- 在Java 10上进行了测试。您正在运行哪个版本？ - Andreas

@Andreas -- 你说得对！我确认HashMap被JVM引导程序调用了19次，而我的代码只调用了2次 :) - James Wierzba

@JamesWierzba 是的，我运行了那个测试，并看到了很多 resize()，但是注意到调用堆栈不正确，所以在我的代码第一行上设置了 触发器 断点，这将调用计数减少到 2。 - Andreas

Answer 2

当你不确定时，请阅读文档。关于HashMap的文档非常清晰地解释了initial capacity和load-factor之间的权衡。

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

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

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

final float loadFactor = 0.5;
final int maxEntries   = 100;
final int initCapacity = (int) maxEntries / loadFactor + 1;
new HashMap<>(initCapacity, loadFactor);

HashMap是一种映射表，其性能受两个参数影响：初始容量和负载因子。容量是哈希表中的桶数，而初始容量就是哈希表创建时的容量。负载因子是哈希表在自动增加容量之前允许填满的程度的衡量标准。当哈希表中的条目数超过负载因子和当前容量乘积时，哈希表会重新散列（即内部数据结构被重建），使哈希表具有大约两倍的桶数。

通常情况下，默认负载因子（.75）在时间和空间成本之间提供良好的平衡。较高的值会减少空间开销，但会增加查找成本（反映在HashMap类的大多数操作中，包括获取和放置）。在设置初始容量时应考虑映射中预期的条目数及其负载因子，以便最小化重新散列操作的数量。如果初始容量大于最大条目数除以负载因子，则不会再进行重新散列操作。

- xtratic

---

0.75 也可以表示为 3/4，因此 (maxEntries / 0.75) + 1 最好写成 maxEntries * 4 / 3 + 1（不需要括号），以便使用 int 进行计算（无需转换）。 - Andreas

另一方面，Java本身在计算时使用了float。 - Mark Rotteveel

@MarkRotteveel 当然可以，但是 new HashMap<>(size * 4/3 + 1) 比 new HashMap<>((int) (size / 0.75 + 1)) 更短、更简单，因为你不需要进行强制类型转换。 - Andreas

@xtratic，我不是很确定，但似乎你把重新散列和重新调整大小混淆了，这些是不同的东西。 - Eugene

@Eugene，就我所知，resize()在Java的HashMap实现中充当了rehash的作用。它可能不会计算新的哈希码，但它确实重新分配元素，在文档和代码中被视为重新哈希操作。 - xtratic

Answer 3

这很容易证明：

这很容易证明：

private static <K, V> void debugResize(Map<K, V> map, K key, V value) throws Throwable {

    Field table = map.getClass().getDeclaredField("table");
    AccessibleObject.setAccessible(new Field[] { table }, true);
    Object[] nodes = ((Object[]) table.get(map));

    // first put
    if (nodes == null) {
        map.put(key, value);
        return;
    }

    map.put(key, value);

    Field field = map.getClass().getDeclaredField("table");
    AccessibleObject.setAccessible(new Field[] { field }, true);
    int x = ((Object[]) field.get(map)).length;
    if (nodes.length != x) {
        ++currentResizeCalls;
    }
}

并且一些用法：

static int currentResizeCalls = 0;

public static void main(String[] args) throws Throwable {

    int size = 100;
    Map<Integer, String> m = new HashMap<>(size);
    for (int i = 0; i < size; i++) {
        DeleteMe.debugResize(m, i, String.valueOf(i));
    }

    System.out.println(DeleteMe.currentResizeCalls);
}     

我只记录当resize实际调整大小时所需的时间，因为第一次调用是初始化;正如文档规定的那样：

初始化或加倍表格大小

---

你提出的第二个观点更有趣。HashMap 定义了 capacity，那么它指的是什么呢？这并不那么明显：

对于 HashMap，capacity 是 resize 发生前的桶数，而对于 ConcurrentHashMap，则是执行 resize 前的条目数。

因此，为了不在内部调用 resize，在 HashMap 的情况下使用以下公式：

(int)(1.0 + (long)initialCapacity / LOAD_FACTOR)

但这远非理想，比如说你想要1024个条目而不需要调整大小，使用那个公式会得到1367个桶，内部会被舍入为2的幂次方，因此是2048，比你要求的多得多。

对于CHM，请直接指定大小。只需在先前的代码中进行一次单一修改即可证明。

 // use CHM instead of HashMap
 Map<Integer, String> m = new ConcurrentHashMap<>(size);

这将导致实际上将数组增大两倍的零次调整大小。但有时候甚至CHM内部代码也很混乱，需要进行一些修补。

- Eugene

Answer 4

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

我决定不再重复发明轮子，因为似乎谷歌已经解决了这个问题。

我将使用Google guava库中的实用方法Maps.newHashMapWithExpectedSize(int)

- James Wierzba

---

你有没有查看过它的实现？这不是魔法：return (int) ((float) expectedSize / 0.75F + 1.0F); - Eugene

@Eugene 取决于你对魔法的定义。如果负载因子或任何其他实现细节发生变化，我希望谷歌库会处理这个问题，而不是我自己去处理。所以这是另一个好处。 - James Wierzba

当然，如果您始终升级Guava并且他们始终跟上内部细节的话，那当然可以；但是这当然取决于您的选择。 - Eugene

@JamesWierzba 错了。首先，如果开发人员使用别人的代码（即使是Guava），他将对自己编写的代码负责（因为他本可以自己编写而不是使用别人的代码）。其次，尽管Java具有向后兼容性，但Oracle JDK 7和Oracle JDK 8中的HashMap内部非常不同，我没有看到Guava为JDK 8+提供了不同版本的Maps＃newHashMapWithExpectedSize。 - blackr1234

@JamesWierzba 第三，该方法的Javadoc声明：“这种行为不能被广泛保证，但在OpenJDK 1.7中观察到是正确的。也不能保证该方法没有意外地超出返回的映射大小。”此外，在Oracle JDK 8中，+ 1.0F实际上是不必要的。如果expectedSize是12，则该方法提供了一个容量为32而不是16的HashMap。16 * 0.75 = 12，只有当添加第13个条目时，HashMap才会将自己调整为容量为32。 - blackr1234

Answer 5

• 重新调整大小是哈希表工作的重要部分，以保持负载因子低。

• 负载因子需要低，因为哈希表的哈希函数在哈希表桶达到最大值时不可避免地会开始发生冲突。如果您的条目每次都散列到已占用的桶中，则冲突可能从第二个条目开始。

---

然而，在你的特定情况下，碰撞不是问题，只有哈希表的调整大小是。

哈希表通常在0.75（=分数中的3/4）负载因子下调整大小。使用这些信息，您可以设置一个哈希表，其容量为所需存储条目数量的4/3倍。

---

关于您对于破坏封装的异议：

我同意您的观点，这是一个有争议的问题。

您可以说如果capacity表示的是调整大小之前可存储的条目数，而不是哈希表中最大可能存储的条目数，那么会更好 - 我倾向于同意您的观点。

但是其他人也可以提出反对意见，认为哈希表占用的空间比预留的空间多。

解决这个问题的方法在于Java领域。Java可以提供两个构造函数，明确说明它们将要做什么，然后开发人员可以在初始化哈希表时进行选择。

- displayName

Answer 6

Java有许多发行版和版本，因此您必须自己进行测试。

在 Oracle JDK 7 中，由于它有 2 个条件用于调整大小（(size >= threshold) && (null != table[bucketIndex])），因此 HashMap 给出的调整大小结果是不可预测的。首先，大小必须是 >= 阈值（cap * load factor）。其次，当前桶必须已经有一个条目，这意味着发生了冲突。 运行下面的代码并亲自查看： 当容量为 4 时，在放置第 5 个条目时进行调整大小。 当容量为 8 时，在放置第 9 个条目时进行调整大小。 当容量为 16 时，在放置第 16 个条目时进行调整大小（而不是 17 个）。 当容量为 32 时，在放置第 32 个条目时进行调整大小（而不是 33 个）。 当容量为 64 时，在放置第 64 个条目时进行调整大小（而不是 65 个）。

在 Oracle JDK 8 中，HashMap 在大小大于阈值（容量*负载因子）时调整大小。 使用容量为 16 和默认负载因子为 0.75，当放置第 13 个条目时调整大小（到容量为 32）。 运行下面的代码并亲自查看： 当容量为 4 时，在放置第 4 个条目时进行调整大小。 当容量为 8 时，在放置第 7 个条目时进行调整大小。 当容量为 16 时，在放置第 13 个条目时进行调整大小。 当容量为 32 时，在放置第 25 个条目时进行调整大小。 当容量为 64 时，在放置第 49 个条目时进行调整大小。

public class HashMapTest {

    public static void main(String[] args) {
        int cap = 4;
        int size = 64;
        Map<Integer, String> map = new HashMap<>(cap);

        for (int i=1; i<=size; i++) {
            map.put(i, i+"");
            print(map);
        }
    }

    public static void print(Map map) {
        try {
            Class<?> mapType = map.getClass();
            Method capacity = mapType.getDeclaredMethod("capacity");
            capacity.setAccessible(true);
            System.out.println("capacity : " + capacity.invoke(map) + "    size : " + map.size());
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

- blackr1234