最佳HashMap的初始容量，同时索引列表 [英] Best HashMap initial capacity while indexing a List

问题描述

我有一个列表（名单，其中，T＆GT;清单），我想索引的对象通过使用地图（的HashMap＆LT它们的ID，整数，T＆GT;地图）。我总是用则为list.size（）作为HashMap的构造函数中的初始容量（如在code以下）。这是最好的初始容量在这种情况下使用？

注意：我绝不会添加更多的项目到地图

 名单，其中，T＆GT;名单= myList中;
地图＆LT;整数，T＆GT;图=新的HashMap＆LT;整数，T＆GT;（则为list.size（））;
对于（T项目：名单）{
    map.put（item.getId（）项）;
}
 

解决方案

如果你希望避免老调重弹的的HashMap ，你知道，没有其他的元素会被放置到在的HashMap ，那么你必须考虑到负荷因子以及初始容量。客座率为的HashMap 默认为0.75 。

的计算，以确定重散列是否有必要发生每当添加新条目，如把将一个新的键/值。所以，如果您指定的初始容量则为list.size（），以及1负载率，那么它会在最后一个把。因此，要prevent重散列，使用1）负载因子和容量的则为list.size（+ 1 。

修改

纵观的HashMap 源$ C ​​$ C，它会老调重弹，如果的旧的大小达到或超过阈值，因此它赢得了在一个't'翻版把。因此，它看起来像一个容量则为list.size（）的应该没事。

 的HashMap＆LT;整数，T＆GT;图=新的HashMap＆LT;整数，T＆GT;（则为list.size（），1.0）;
 

下面是的HashMap 源$ C ​​$ C相关的段子：

 无效的addEntry（INT哈希，K键，V值，诠释bucketIndex）{
    进入＆LT; K，V＆GT; E =表[bucketIndex]
    表[bucketIndex] =新条目＆LT;＆GT;（哈希键，值，E）;
    如果（尺寸++盐=阈值）
        调整（2 * table.length）;
}
 

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?

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);
}

解决方案

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.

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.

EDIT

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);

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屋！