为什么HashMap的初始容量在库中没有被正确处理？

Question

为什么HashMap的初始容量在库中没有被正确处理？

javahashmapcapacity

4

为了创建N个元素的HashMap/HashSet，我们通常会使用new HashMap((int)(N/0.75F)+1)，这很烦人。

为什么库没有一开始就考虑到这一点，并允许像new HashMap(N)这样的初始化（不应该在N个元素之前重新哈希），并处理计算(int)(N/0.75F)+1？

更新于11月22日：

Java 19引入了HashMap<K,V> newHashMap(int numMappings) Javadoc：

创建一个适合预期映射数量的新的、空的HashMap。返回的映射使用默认负载因子0.75，其初始容量通常足够大，以便可以添加预期的映射而无需调整大小。

其他Map类也引入了类似的方法。

- Venkata Raju

我不明白问题出在哪里，因为HashMap按照你所说的方式运行。 - Peter Lawrey

1

仅使用数字的重载指定了包括空闲空间在内的大小。Venkata 希望它是重新散列之前的条目数。库开发人员做出了另一种选择。现在没有争论的必要了。 - jackrabbit

@jackrabit 你说得对。我只是想知道它被设计成这样是否有任何技术上的原因。 - Venkata Raju

3个回答

1

我已经运行了以下程序

public static void main(String... args) throws IllegalAccessException, NoSuchFieldException {
    for (int i = 12; i < 80; i++) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>((int) Math.ceil(i / 0.75));
        int beforeAdding = Array.getLength(getField(map, "table"));
        for (int j = 0; j < i; j++) map.put(j, j);
        int afterAdding = Array.getLength(getField(map, "table"));
        map.put(i, i);
        int oneMore = Array.getLength(getField(map, "table"));
        System.out.printf("%,d: initial %,d, after N %,d, after N+1 %,d%n ",
                i, beforeAdding, afterAdding, oneMore);
    }
}

private static <T> T getField(Map<Integer, Integer> map, String fieldName) throws NoSuchFieldException, IllegalAccessException {
    Field table = map.getClass().getDeclaredField(fieldName);
    table.setAccessible(true);
    return (T) table.get(map);
}

打印输出

 12: initial 16, after N 16, after N+1 32
 13: initial 32, after N 32, after N+1 32
 .. deleted ..
 24: initial 32, after N 32, after N+1 64
 25: initial 64, after N 64, after N+1 64
 .. deleted ..
 47: initial 64, after N 64, after N+1 64
 48: initial 64, after N 64, after N+1 128
 49: initial 128, after N 128, after N+1 128
 .. deleted ..
 79: initial 128, after N 128, after N+1 128

这表明默认初始化器的初始容量会被舍入到下一个二次幂。这个值的问题在于，如果你希望这是最终大小，你必须考虑负载因子，以避免调整大小。理想情况下，你不应该这样做，就像 Map 的复制构造函数为你所做的那样。

- Peter Lawrey

@VenkataRaju 感谢您提供的链接。它是多余的。您只需要指定 N 作为初始容量即可。 - Peter Lawrey

你只需要指定 N 作为初始容量。嗯...我觉得不是这样，那为什么 Maps.newHashMapWithExpectedSize(int expectedSize) 存在呢？请参见 @Tomasz 的更新回复。 - Venkata Raju

@VenkataRaju 我现在明白你的意思了。我更新了我的答案。 - Peter Lawrey

0

大多数实现会随着您添加更多元素而自动增长。当容器变得更满时，大多数实现的性能也往往会降低。这就是为什么首先有一个负载因子：留出一些空闲空间。

- jackrabbit

呃...不确定你是否理解了问题。如果我创建一个 new HashMap(N)，我会认为它不会增长/重新散列不会发生，直到我放置第N+1个元素，但现实是，在那之前会进行重新散列。为了防止重新散列，我们将初始化为 new HashMap((int)(N/0.75F)+1)。现在我的问题是，库是否会处理这个并允许我们使用 new HashMap(N) 并在内部处理此计算。 - Venkata Raju

从你的问题中完全不清楚。看看Tomasz的答案。他们一定认为你的是一个不常见的用例，如果需要，可以轻松实现。 - jackrabbit

据我所知，您甚至不能确定在这样初始化时重新散列是否发生。您真的有重新散列的（可测量的）问题吗？还是您只是担心如果发生重新散列会失去性能？否则，这似乎是过早优化的情况... - Axel

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Tomasz Nurkiewicz · Accepted Answer

更新

更新以反映更改的问题。不，没有这样的标准API，但似乎在guava中有一个方法Maps.newHashMapWithExpectedSize(int)：

创建一个HashMap实例，其“初始容量”足够高，可以容纳expectedSize个元素而不需要增长。

“我必须将它初始化为(int)(N/0.75F)+1。”

不，你不需要这样做。如果你从其他Map创建新的HashMap，HashMap默认会先计算容量：

public HashMap(Map<? extends K, ? extends V> m) {
    this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                  DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
    putAllForCreate(m);
}

如果您逐个添加元素，则同样会发生相同的过程：

void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);
        //...
    }

    createEntry(hash, key, value, bucketIndex);
}

只有当您从一开始就知道要存储多少元素以避免后期调整大小和重新哈希（map 从一开始就具有正确的大小）时，才使用HashMap(int initialCapacity, float loadFactor) 构造函数。

一个有趣的实现细节是，初始容量被修剪为最接近的2的幂（参见：为什么ArrayList以1.5增长率增长而Hashmap却是2?）。

// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
    capacity <<= 1;

因此，如果您希望您的HashMap具有与定义完全相同的容量，请使用二的幂。选择不同的loadFactor可以让您在空间和性能之间进行权衡 - 较小的值意味着更多的内存，但冲突较少。