java - 索引列表时的最佳 HashMap 初始容量

Question

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

注意:我永远不会在 map 上添加更多项目。

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，那么您必须将负载因子考虑在内以及初始容量。负载率for a HashMap defaults to 0.75 .

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

编辑

查看HashMap源码，如果old大小达到或超过阈值就会rehash，所以不会在最后一个put上rehash 。所以看起来 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);
}