为什么 ArrayList 以 1.5 的速度增长，而 Hashmap 却是 2? [英] Why ArrayList grows at a rate of 1.5, but for Hashmap it's 2?

问题描述

根据 Sun Java 实现，在扩展期间，ArrayList 增长到初始容量的 3/2，而对于 HashMap，扩展率是原来的两倍.这背后的原因是什么?

As per Sun Java Implementation, during expansion, ArrayList grows to 3/2 it's initial capacity whereas for HashMap the expansion rate is double. What is reason behind this?

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

As per the implementation, for HashMap, the capacity should always be in the power of two. That may be a reason for HashMap's behavior. But in that case the question is, for HashMap why the capacity should always be in power of two?

推荐答案

增加 ArrayList 容量的昂贵部分是将支持数组的内容复制到一个新的(更大的)一个.

The expensive part at increasing the capacity of an ArrayList is copying the content of the backing array a new (larger) one.

对于 HashMap，它正在创建一个新的支持数组并将所有映射条目放入新数组中.而且，容量越高，发生碰撞的风险就越低.这更昂贵并解释了为什么膨胀系数更高.1.5 与 2.0 的原因?我认为这是最佳实践"或良好的权衡".

For the HashMap, it is creating a new backing array and putting all map entries in the new array. And, the higher the capacity, the lower the risk of collisions. This is more expensive and explains, why the expansion factor is higher. The reason for 1.5 vs. 2.0? I consider this as "best practise" or "good tradeoff".

这篇关于为什么 ArrayList 以 1.5 的速度增长，而 Hashmap 却是 2?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！