java - 为什么库没有正确处理 HashMap 初始容量？

Question

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

为什么库没有首先处理这个问题并允许像 new HashMap(N) 这样的初始化(不应该重新散列直到 N 个元素)来处理这个计算 (int )(N/0.75F)+1?

22 年 11 月 9 日更新:

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

Java文档:

Creates a new, empty HashMap suitable for the expected number of mappings. The returned map uses the default load factor of 0.75, and its initial capacity is generally large enough so that the expected number of mappings can be added without resizing the map.

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

Answer 1

更新

更新以反射(reflect)已更改的问题。不，没有这样的标准 API，但似乎有一种方法 Maps.newHashMapWithExpectedSize(int)在 guava :

Creates a HashMap instance, with a high enough "initial capacity" that it should hold expectedSize elements without growth.

---

i have to initialize it to (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);
}

使用 HashMap(int initialCapacity, float loadFactor) 构造函数的唯一原因是当您从一开始就知道要在 HashMap 中存储多少元素时，从而避免稍后调整大小和重新散列( map 从一开始就具有正确的大小)。

一个有趣的实现细节是初始容量被修剪为最接近的二的幂(参见:Why ArrayList grows at a rate of 1.5, but for Hashmap it's 2?):

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

因此，如果您希望您的 HashMap 具有定义的精确容量，只需使用 2 的幂即可。

选择不同的 loadFactor 允许您以空间换取性能 - 较小的值意味着更多的内存，但冲突更少。