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

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

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

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

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

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

我可以想到两个原因。

  1. 您可以快速确定哈希码进入的存储桶。 你只需要一个按位AND而且没有昂贵的模数。 int bucket = hashcode & (size-1);

  2. 假设我们的增长因子为1.7。 如果我们从11开始,下一个大小将是18,然后是31.没问题。 对? 但是Java中的字符串的哈希码是以素数因子31计算的。字符串进入的桶, hashcode%31 ,然后仅由字符串的最后一个字符确定。 再见O(1)如果您存储所有以/结尾的文件夹。 如果使用的大小例如为3^n则增加n分布不会变差 。 从大小39 ,桶2每个元素现在将转到桶57 ,具体取决于更高的数字。 就像将每个桶分成三块一样。 因此,优选整数生长因子的大小。 (当然,这一切都取决于你如何计算哈希码,但任意增长因素都不会感觉’稳定’。)

HashMap的设计/实现方式其底层数量的桶必须是2的幂(即使你给它一个不同的大小,它使它的功率为2),因此它每次增长两倍。 ArrayList可以是任何大小,它可以更加保守。

散列利用将数据均匀分布到存储桶中。 该算法试图阻止桶中的多个条目(“散列冲突”),因为它们会降低性能。

现在,当达到HashMap的容量时,扩展大小并使用新存储桶重新分配现有数据。 如果尺寸增加太小,则重新分配空间和重新分配会经常发生。

我不能告诉你为什么会这样(你不得不问Sun开发人员),但要看看这是怎么回事看看来源:

  1. HashMap:看看HashMap如何resize( 源代码行799)

      resize(2 * table.length); 
  2. ArrayList: source ,第183行:

     int newCapacity = (oldCapacity * 3)/2 + 1; 

更新:我错误地链接到Apache Harmony JDK的源代码 – 将其更改为Sun的JDK。

避免地图上的冲突的一般规则是将加载因子最大值保持在0.75左右。为了减少冲突的可能性并避免昂贵的复制过程,HashMap以更大的速率增长。

正如@Peter所说,它必须是2的幂。