HashMap初始化参数(load/initialcapacity)

Question

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

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

Answer 1

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

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

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

Answer 2

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

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

因为初始容量给出了你想要的a HashMap或a 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 Adam的答案对于所有情况都是正确的,除了(requiredCapacity / 0.75)2的幂,在这种情况下它分配了太多的内存.
@ NotEdible的答案在很多情况下使用了太多的内存,因为HashMap的构造函数本身处理的问题是它希望maps数组的大小是2的幂.

Answer 3

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

来自文档:

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

Answer 4

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

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

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

Answer 5

Yuval 给出的答案仅对于 Hashtable 是正确的。HashMap 使用二次方存储桶，因此对于 HashMap，Zarkonnen 实际上是正确的。您可以从源代码中验证这一点：

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

因此，尽管 Hashtable 和 HashMap 的负载系数 0.75f 仍然相同，但您应该使用初始容量 n*2，其中 n 是您计划在 HashMap 中存储的元素数量。这将确保最快的获取/放置速度。