在索引列表时,最佳HashMap初始容量 [英] Best HashMap initial capacity while indexing a List
问题描述
我有一个列表( List< T> list
),并且我想使用映射( HashMap< Integer ,T>地图
)。我始终在 HashMap
构造函数中使用 list.size()
作为初始容量就像下面的代码一样。这是在这种情况下使用最好的初始容量吗?
I have a list (List<T> list
) and I want to index its objects by their ids using a map (HashMap<Integer, T> map
). I always use list.size()
as the initial capacity in the HashMap
constructor,like in the code below. Is this the best initial capacity to be used in this case?
注意:我不会在地图上添加更多的项目。 p>
Note: I'll never add more items to the map.
List<T> list = myList;
Map<Integer, T> map = new HashMap<Integer, T>(list.size());
for(T item : list) {
map.put(item.getId(), item);
}
推荐答案
如果您希望避免重复 HashMap
,您知道没有其他元素将被放入 HashMap
中,那么您必须考虑到负载系数以及初始容量。负载因子 HashMap
默认为0.75 。
If you wish to avoid rehashing the HashMap
, and you know that no other elements will be placed into the HashMap
, then you must take into account the load factor as well as the initial capacity. The load factor for a HashMap
defaults to 0.75.
每当添加新条目时,都需要进行重新排序的计算,例如 put
放置一个新的键/值。因此,如果您指定初始容量 list.size()
,加载系数为1,那么在最后一个 put
。所以为了防止rehashing,使用负载因子1,容量 list.size()+ 1
。
The calculation to determine whether rehashing is necessary occurs whenever an new entry is added, e.g. put
places a new key/value. So if you specify an initial capacity of list.size()
, and a load factor of 1, then it will rehash after the last put
. So to prevent rehashing, use a load factor of 1 and a capacity of list.size() + 1
.
编辑
查看 HashMap
源代码,如果 old size达到或超过阈值,所以它不会在最后一个 put
上重新显示。所以看起来像一个容量 list.size()
应该是正常的。
Looking at the HashMap
source code, it will rehash if the old size meets or exceeds the threshold, so it won't rehash on the last put
. So it looks like a capacity of list.size()
should be fine.
HashMap<Integer, T> map = new HashMap<Integer, T>(list.size(), 1.0);
这里是相关的 HashMap
源代码:
Here's the relevant piece of HashMap
source code:
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);
}
这篇关于在索引列表时,最佳HashMap初始容量的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!