索引List时的最佳HashMap初始容量

Question

我有一个list(List<T> list),我想使用map(HashMap<Integer, T> map)通过id来索引它的对象.我总是用list.size()作为初始容量的HashMap构造函数,如下面的代码.这是在这种情况下使用的最佳初始容量吗？

注意:我永远不会在地图上添加更多项目.

List<T> list = myList;
Map<Integer, T> map = new HashMap<Integer, T>(list.size());
for(T item : list) {
    map.put(item.getId(), item);
}

Answer 1

如果你想避免重复HashMap,并且你知道没有其他元素被放入HashMap,那么你必须考虑负载系数和初始容量.默认负载系数为HashMap0.75.

每当添加新条目时,确定是否需要重新散列的计算,例如put放置新的键/值.因此,如果指定初始容量为list.size()1,加载因子为1,则它将在最后一次之后重新进行put.因此,为防止重新散列,请使用1的加载因子和容量list.size() + 1.

编辑

查看HashMap源代码,如果旧的大小达到或超过阈值,它将重新进行,因此它不会在最后一次重新散列put.所以看起来容量list.size()应该没问题.

HashMap<Integer, T> map = new HashMap<Integer, T>(list.size(), 1.0);

这是相关的HashMap源代码:

void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    if (size++ >= threshold)
        resize(2 * table.length);
}

Answer 2

根据定义,'capacity'关键字不正确,并且不按通常预期的方式使用.

默认情况下,HashMap的"加载因子"为0.75,这意味着当HashMap中的条目数达到所提供容量的75%时,它将调整数组的大小并重新散列.

例如,如果我这样做:

Map<Integer, Integer> map = new HashMap<>(100);

当我添加第75个条目时,映射会将Entry表的大小调整为2*map.size()(或2*table.length).所以我们可以做一些事情:

1. 更改负载系数 - 这可能会影响地图的性能
2. 将初始容量设置为list.size()/ 0.75 + 1

最好的选择是两者中的后者,让我解释一下这里发生了什么:

list.size() / 0.75

这将返回list.size()+ list.size()的25%,例如,如果我的列表的大小为100,它将返回133.然后,如果地图的大小调整为大小,我们会向其添加1等于初始容量的75%,所以如果我们有一个大小为100的列表,我们将初始容量设置为134,这意味着从列表中添加所有100个条目不会导致任何地图大小调整.

最终结果:

Map<Integer, Integer> map = new HashMap<>(list.size() / 0.75 + 1);

Answer 3

你做的很好.通过这种方式,您可以确保哈希映射至少具有足够的初始值容量.如果您有关于哈希映射的使用模式的更多信息(例如:它是否经常更新？是否经常添加许多新元素？),您可能希望设置更大的初始容量(例如list.size() * 2),但从不降低.使用分析器确定初始容量是否过早降低.

UPDATE

感谢@PaulBellora建议初始容量应设置为(int)Math.ceil(list.size() / loadFactor)(通常,默认加载因子为0.75),以避免初始调整大小.

Answer 4

Guava Maps.newHashMapWithExpectedSize使用这个辅助方法0.75根据一些预期的值来计算默认加载因子的初始容量:

/**
 * Returns a capacity that is sufficient to keep the map from being resized as
 * long as it grows no larger than expectedSize and the load factor is >= its
 * default (0.75).
 */
static int capacity(int expectedSize) {
    if (expectedSize < 3) {
        checkArgument(expectedSize >= 0);
        return expectedSize + 1;
    }
    if (expectedSize < Ints.MAX_POWER_OF_TWO) {
        return expectedSize + expectedSize / 3;
    }
    return Integer.MAX_VALUE; // any large value
}

参考:来源

从newHashMapWithExpectedSize文档:

创建一个HashMap具有足够高"初始容量" 的实例,它应该保持expectedSize元素不增长.这种行为无法得到广泛保证,但对于OpenJDK 1.6来说却是如此.也无法保证该方法不会无意中超大返回的地图.