HashMap初始化参数（加载/初始容量）

应该通过什么值来创建一个有效的基于N个项目的HashMap/HashMap？HashMap初始化参数（加载/初始容量）

在ArrayList中，有效数字是N（N已假定未来增长）。 HashMap应该是什么参数？（（int）（N * 0.75d），0.75d）？更多？减？改变载荷系数有什么影响？

2009-01-12 Ran Biron

最近，我问了一个[类似问题]（http://stackoverflow.com/questions/414109/）与.NET通用词典有关。你可能会发现这里的讨论也很有趣。 – 2009-01-12 10:21:35

另请参阅http://stackoverflow.com/questions/7115445/what-is-the-optimal-capacity-and-load-factor-for-a-fixed-size-hashmap – Raedwald 2014-09-17 16:52:56

关于客座率，我会简单地从HashMap javadoc引用：

作为一般规则，默认加载因子（.75）在时间和空间成本之间的良好平衡。较高的值会减少空间开销，但会增加查找成本（反映在大部分HashMap类的操作中，包括get和put）。在设置初始容量时，应考虑映射中的条目数量及其负载因子，以尽量减少重新运行操作的次数。如果初始容量大于最大入口数除以负载因子，则不会发生重新刷新操作。

意思是，除非你有一些特定的优化，否则载荷因子不应该从.75改变。初始容量是您想要更改的唯一内容，并根据您的N值（意为(N/0.75) + 1）或其他内容进行设置。这将确保表格总是足够大并且不会发生重新散列。

来源

2009-01-12 10:12:37

在ArrayList中，有效数字是N（N已假定未来增长）。

呃，不，它不会，除非我误解你在这里说什么。当您将一个整数传递给Arraylist构造函数时，它将创建一个完全相同大小的底层数组。如果事实证明你甚至需要一个额外的元素，那么当你下一次调用add（）时，ArrayList将需要调整底层数组的大小，导致这个调用花费的时间比通常长。

如果在另一方面，你在谈论你的N个兼顾成长价值 - 然后是的，如果你能保证该值将永远不会高于此，然后调用这样一个ArrayList构造是合适的。在这种情况下，正如汉克所指出的，地图的类似构造函数将是N和1.0f。即使您碰巧超过了N，这也应该合理地执行（尽管如果您希望定期发生这种情况，您可能希望为初始大小传递更大的数字）。

负荷系数，万一你不知道，是该地图将有它的容量增加，总容量的一小部分的点。

编辑：Yuval可能是正确的，对于通用地图而言，将负载系数保持在0.75左右是一个更好的主意。 1.0的客座率将执行出色，如果你的钥匙了连续哈希码（如顺序整数键），但其他的事，你可能会遇到与散列桶的碰撞，这意味着查询需要更长的一些元素。创造更多的桶比是绝对必要将减少碰撞的这个机会，这意味着有更多的在自己的桶是元素的机会，因此是在最短的时间量检索。正如文件所言，这是时间与空间的折衷。如果（！为由探查显示，而不是过早地优化），要么是对你特别重要的，你可以强调的是，否则，坚持默认。

来源

2009-01-12 10:18:33

还有一点值得注意的是，在小的一边使用HashMap会使得散列冲突更有可能，这会减慢查找速度。因此，如果您真的担心地图的速度，并且不太关注地图的大小，则可能需要使其对于需要保存的数据来说太大。由于内存很便宜，我通常初始化为已知数量的项目包含HashMap与

HashMap<Foo> myMap = new HashMap<Foo>(numberOfElements * 2);

随意不同意，其实我挺喜欢这个主意验证或抛出。

来源

2009-01-12 10:19:35 Zarkonnen

我不同意。从HashMap的JavaDoc：>>对集合视图的迭代需要的时间与HashMap实例的“容量”（桶的数量）加上其大小（键值映射的数量）成正比。因此，如果迭代性能很重要，不要将初始容量设置得太高（或者负载因子太低）是非常重要的。 << – 2011-05-05 09:19:36

整个地图的迭代速度会更慢，但查找（get）会更快。 – Jim 2013-07-18 13:29:52

引用HashMap源代码会有所帮助。

如果条目数达到阈值（容量*加载因子），则自动执行重新散列。这意味着，随着条目的增长，过小的负载因数可能会导致频繁的刷新。

来源

2009-02-25 02:02:08 grayger

对于关键系统中的非常大的HashMap，如果初始容量错误可能非常成问题，您可能需要经验性信息来确定如何最好地初始化您的Map。

CollectionSpy（collectionspy.com）是一个新的Java分析器，它可以让您在瞬间看到哪些HashMaps接近需要重新散列，它们过去被重新映射了多少次，等等。确定基于容量的容器构造函数的安全初始容量参数的理想工具。

来源

2009-07-03 19:24:55

看起来像一个非常好的工具 - 可惜没有试用版 – 2009-07-05 12:39:16

Yuval给出的答案只适用于Hashtable。 HashMap使用两个幂的桶，所以对于HashMap，Zarkonnen实际上是正确的。您可以从源代码进行验证：

// Find a power of 2 >= initialCapacity 
    int capacity = 1; 
    while (capacity < initialCapacity) 
    capacity <<= 1;

所以，虽然0.75f的客座率仍然是Hashtable和HashMap中的一样，你应该使用的初始容量N * 2，其中n为元素的数量你打算存储在HashMap中。这将确保最快的上/下速度。

来源

2009-11-25 15:02:39 NotEdible

它在List和Map初始化的大多数情况下的安全，使List或Map具有以下尺寸PARAMS。

List<T>(numElements + (numElements/2)); 
Map<T,T>(numElements + (numElements/2));

这遵循0.75规则以及节省超过上述* 2操作的小的开销。

来源

2010-07-27 16:03:17 lv2program

为什么要初始化一个列表，其容量比它将容纳的最大元素数量还要高？这不合逻辑。仅对于地图而言，因为它们的构造函数参数确实意味着与列表完全不同，所以计算更高的值是很好的！ – Zordid 2012-04-24 07:37:18

我跑到一些unit tests，看看这些问题的答案是正确的，它是利用原来：

(int) Math.ceil(requiredCapacity/loadFactor);

为初始容量给你想要的任何一个HashMap或Hashtable。通过“你想要什么”，我的意思是将requiredCapacity元素添加到映射中将不会导致它正在包装的数组调整大小，并且该数组不会超过所需的大小。由于默认负载能力是0.75，初始化一个HashMap像这样工作的：

... = new HashMap<KeyType, ValueType>((int) Math.ceil(requiredCapacity/0.75));

由于HashSet的有效仅仅是一个HashMap的包装，同样的逻辑也适用在那里，即你可以有效地构造一个HashSet是这样的：

.... = new HashSet<TypeToStore>((int) Math.ceil(requiredCapacity/0.75));

@Yuval亚当的回答是，除非(requiredCapacity/0.75)是2的幂，在这种情况下，分配太多的内存正确的所有情况。
@ NotEdible的答案使用太多的内存在许多情况下，作为HashMap中的构造本身的问题涉及它想要的地图阵列有一个大小在2

来源

2012-08-15 14:06:38

电源在guava libraries从谷歌有newHashMapWithExpectedSize

从文档：创建一个预计数项优化HashMap中的功能

创建一个HashMap实例，具有足够高的“初始容量”，它应保持不增长expectedSize元素...

来源

2013-04-18 11:19:40 linqu

HashMap初始化参数（加载/初始容量）

回答

相关问题