3

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

为什么库一开始就没有处理这个问题，而是允许初始化new HashMap(N)（不应该重新散列到 N 个元素）来处理这个计算(int)(N/0.75F)+1？

4

3 回答 3

2

更新

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

创建一个HashMap具有足够高的“初始容量”的实例，它应该可以容纳expectedSize没有增长的元素。

我必须将其初始化为 (int)(N/0.75F)+1

不，你没有。HashMap如果你从 other新建Map，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，从而避免以后调整大小和重新散列（地图从一开始就具有正确的大小）。

一个有趣的实现细节是初始容量被修剪到最接近的 2 次幂（请参阅：为什么 ArrayList 以 1.5 的速率增长，但对于 Hashmap，它是 2？）：

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

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

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

于 2012-11-11T09:18:16.437 回答
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 复制构造函数为您所做的那样。

于 2012-11-11T11:11:03.317 回答
0

大多数实现会随着您添加更多元素而自动增长。当容器变满时，大多数实现的性能也会下降。这就是为什么首先存在负载因素的原因：留下一些可用空间。

于 2012-11-11T09:08:35.007 回答