索引List时的最佳HashMap初始容量
我有一个列表( List list
),我想使用map( HashMap map
)通过id来索引其对象。 我总是使用list.size()
作为HashMap
构造函数中的初始容量 ,如下面的代码所示。 这是在这种情况下使用的最佳初始容量吗?
注意 :我永远不会在地图上添加更多项目。
List list = myList; Map map = new HashMap(list.size()); for(T item : list) { map.put(item.getId(), item); }
如果您希望避免重新散列HashMap
,并且您知道没有其他元素将放入HashMap
,那么您必须考虑加载因子以及初始容量。 HashMap
的加载因子默认为0.75 。
每当添加新条目时,确定是否需要重新散列的计算发生,例如, put
新的键/值。 因此,如果您指定list.size()
的初始容量和加载因子1,那么它将在最后一次put
后重新散列。 因此,为防止重新散列,请使用1的加载因子和list.size() + 1
的容量。
编辑
查看HashMap
源代码,如果旧大小达到或超过阈值,它将重新进行,因此它不会在最后一次put
。 所以看起来list.size()
的容量应该没问题。
HashMap map = new HashMap(list.size(), 1.0);
这是相关的HashMap
源代码:
void addEntry(int hash, K key, V value, int bucketIndex) { Entry e = table[bucketIndex]; table[bucketIndex] = new Entry<>(hash, key, value, e); if (size++ >= threshold) resize(2 * table.length); }
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来说却是如此。 也无法保证该方法不会无意中超大返回的地图。
根据定义,’capacity’关键字不正确,并且不按通常预期的方式使用。
默认情况下,HashMap的“加载因子”为0.75,这意味着当HashMap中的条目数达到所提供容量的75%时,它将调整数组的大小并重新散列。
例如,如果我这样做:
Map map = new HashMap<>(100);
当我添加第75个条目时,地图会将Entry表的大小调整为2 * map.size()(或2 * table.length)。 所以我们可以做一些事情:
- 更改负载系数 – 这可能会影响地图的性能
- 将初始容量设置为list.size()/ 0.75 + 1
最好的选择是两者中的后者,让我解释一下这里发生了什么:
list.size() / 0.75
这将返回list.size()+ list.size()的25%,例如,如果我的列表的大小为100,它将返回133.然后我们再添加1,因为如果地图的大小是等于初始容量的75%,所以如果我们有一个大小为100的列表,我们将初始容量设置为134,这意味着从列表中添加所有100个条目不会导致任何地图大小调整。
最终结果:
Map map = new HashMap<>(list.size() / 0.75 + 1);
你做的很好。 通过这种方式,您可以确保哈希映射至少具有足够的初始值容量。 如果您有关于哈希映射的使用模式的更多信息(例如:它是否经常更新?是否经常添加许多新元素?),您可能需要设置更大的初始容量(例如, list.size() * 2
),但永远不会降低。 使用分析器确定初始容量是否过早降低。
UPDATE
感谢@PaulBellora建议初始容量应设置为(int)Math.ceil(list.size() / loadFactor)
(通常,默认加载因子为0.75),以避免初始resize。
根据java.util.HashMap的参考文档 :
在设置其初始容量时,应考虑映射中的预期条目数及其负载因子,以便最小化重新散列操作的数量。 如果初始容量大于最大条目数除以加载因子,则不会发生重新加载操作。
这意味着,如果您事先知道HashMap应存储多少条目,则可以通过选择适当的初始容量和加载因子来防止重新散列。 然而:
作为一般规则,默认加载因子(.75)在时间和空间成本之间提供了良好的折衷。 较高的值会减少空间开销,但会增加查找成本(反映在HashMap类的大多数操作中,包括get和put)。