HashMap初始化参数(load/initialcapacity)

我应该传递什么值来为N个项目创建有效HashMap/ HashMap基础的结构？

在一个ArrayList,有效数字是N(N已经假定未来增长).应该是什么参数HashMap？((int)(N*0.75d),0.75d)？更多？减？改变负载系数有什么影响？

1> Yuval Adam..：

---

关于加载因子,我只是引用HashMap javadoc:

作为一般规则,默认加载因子(.75)在时间和空间成本之间提供了良好的权衡.较高的值会减少空间开销,但会增加查找成本(反映在HashMap类的大多数操作中,包括get和put).在设置其初始容量时,应考虑映射中的预期条目数及其加载因子,以便最小化重新散列操作的数量.如果初始容量大于最大条目数除以加载因子,则不会发生重新加载操作.

这意味着,.75除非您要进行某些特定的优化,否则不应更改负载系数.初始容量是您想要更改的唯一内容,并根据您的N值设置它- 意思(N / 0.75) + 1或该区域中的某些内容.这将确保表格总是足够大并且不会发生重新散列.

2> Mark Rhodes..：

---

我运行了一些单元测试,看看这些答案是否正确,结果证明使用:

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

因为初始容量给出了你想要的a HashMap或a Hashtable.通过"你想要的"我的意思是向requiredCapacity地图添加元素不会导致它包装的数组调整大小,并且数组不会大于所需的数组.由于默认加载容量为0.75,因此初始化HashMap的工作原理如下:

... = new HashMap((int) Math.ceil(requiredCapacity / 0.75));

由于HashSet实际上只是HashMap的包装器,因此同样的逻辑也适用于此,即您可以像这样有效地构造HashSet:

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

@Yuval Adam的答案对于所有情况都是正确的,除了(requiredCapacity / 0.75)2的幂,在这种情况下它分配了太多的内存.
@ NotEdible的答案在很多情况下使用了太多的内存,因为HashMap的构造函数本身处理的问题是它希望maps数组的大小是2的幂.

---

相当于`(int)Math.ceil(requiredCapacity/0.75)`,避免方法调用以及与浮点之间的转换,是`(requiredCapacity*4 + 2)/ 3`.使用纯粹的"int"算法时,这会得到相同的结果.

3> linqu..：

---

在Google 的guava库中,有一个函数可以创建一个针对预期数量的项目优化的HashMap:newHashMapWithExpectedSize

来自文档:

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

4> Zarkonnen..：

---

另外值得注意的是,在较小的一侧使用HashMap会使哈希冲突更有可能,这可能会减慢查找速度.因此,如果你真的担心地图的速度,而不是它的大小,可能值得让它有点太大而无法容纳它需要的数据.由于内存很便宜,我通常会使用HashMaps初始化已知数量的项目

HashMap myMap = new HashMap(numberOfElements * 2);

随意不同意,事实上我非常希望验证或抛弃这个想法.