为什么ArrayList以1.5的速度增长,但对于Hashmap,它是2？

Question

根据Sun Java Implementation,在扩展期间,ArrayList增长到3/2它的初始容量,而对于HashMap,扩展速率是双倍.这背后的原因是什么？

根据实现,对于HashMap,容量应始终为2的幂.这可能是HashMap行为的原因.但在这种情况下,问题是,对于HashMap,为什么容量应始终为2的幂？

Answer 1

增加ArrayList容量的昂贵部分是将后备阵列的内容复制为新的(更大的)内容.

对于HashMap,它正在创建一个新的后备数组并将所有映射条目放在新数组中.而且,容量越高,碰撞的风险就越低.这更昂贵,并解释了为什么扩展因子更高.1.5 vs. 2.0的原因？我认为这是"最佳实践"或"良好的权衡".

此外，哈希表通常会增加 2 倍（并且支持它的存储桶列表的大小为 2 的幂），因为几乎所有实现中都使用了优化：当计算哈希时，进行模运算（` %`) 是为了找到存储桶以将值放入：`bucketIndex = hash % numBuckets`。昂贵的 `x % n` 操作可以简化为按位 `x & (n - 1)`，**但前提是 `n` 是 2 的幂**。哈希图/表必须每次增长 2 倍，以保持支持它的存储桶的 2 的幂大小。_见下面的其他答案。_ (3认同)
危害在于ArrayList的大小越大，分配给它的内存就越多（如果不使用空间，这可能会浪费掉）。由于增加ArrayList的容量要比增加HashMap的容量便宜得多，因此随着ArrayList容量的增加而变得更加保守是有道理的。本质上，@ Andreas_D解释了为什么HashMap的因子应该大于ArrayList的因子。为什么特别是2.0和1.5？这可能基于使用情况测试，但是我猜您必须问一下Java开发人员本身。 (2认同)
@Arnab Biswas：另一个原因：ArrayList中未使用的内存被浪费了，与HashMap中的不同，后者使冲突发生率降低，从而加快了访问速度。 (2认同)

Answer 2

对于HashMap,为什么容量应始终为2的幂？

我可以想到两个原因.

您可以快速确定哈希码进入的存储区.您只需要一个按位AND并且不需要昂贵的模数.int bucket = hashcode & (size-1);
假设我们的增长因子为1.7.如果我们从11开始,下一个大小将是18,然后是31.没问题.对？但是Java中的字符串的哈希码是以素数因子31计算的.字符串进入的存储桶hashcode%31只能由字符串的最后一个字符确定.O(1)如果您存储所有文件夹的文件夹,请再见/.如果您使用的尺寸,例如3^n,分布也不会,如果你增加变得更糟n.从大小3到9存储桶中的每个元素2现在都会变为存储桶2,5或者7取决于更高的数字.就像将每个桶分成三块一样.因此,优选整数生长因子的大小.(当然,这一切都取决于你如何计算哈希码,但任意增长因子都不会感觉'稳定'.)

Answer 3

HashMap 的设计/实现方式是它的底层桶数必须是 2 的幂（即使你给它不同的大小，它也会变成 2 的幂），因此它每次都会增长两倍。ArrayList 可以是任意大小，并且在增长方式上可以更加保守。