ArrayDeque的调整大小

huangapple go评论82阅读模式
英文:

Resizing of ArrayDeque

问题

引用:ArrayDeque 的默认初始容量为 16。当大小超过容量时,它会按照2的幂增加(24、25、26等等)。

这是否意味着它的行为类似于 ArrayList?每次大小超过容量时,都会有一个新的数组,旧元素会被复制到其中吗?我能否说 ArrayDequeueArrayList 的内部实现都是基于数组(正如它们的名称所示)?只是调整大小的方式不同?

英文:

Quote: Default initial capacity of ArrayDeque is 16. It will increase at a power of 2 (24, 25, 26 and so on) when size exceeds capacity.

Does this mean it behaves similar to ArrayList? Each time size exceeds capacity there is new array where older elements are copied to? Can I say internal implementation of ArrayDequeue and ArrayList is array (as their name says)? Just the resizing differs?

答案1

得分: 1

是的,ArrayDeque 的行为与 ArrayList 类似:它在内部使用一个对象数组。如果容量不足,它会创建一个新的、更大的数组,并将项目从旧数组复制到新数组。

Java API 规范并不要求任何特定的调整大小行为。实际上,OpenJDK 中当前的实现在数组小于 64 时会将数组的大小加倍,否则会增长 50%:

// 如果较小,则加倍容量;否则增长 50%
int jump = (oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1);

看起来,“加倍”行为是近似的:在第一次调整大小后,由于有“+2”,容量为 16+16+2 = 34。在第二次调整大小后,它变为 34+34+2 = 70。此后,数组在每次调整大小时增长 50%。

英文:

Yes ArrayDeque behaves similarly to ArrayList: Internally it uses an Object array. If the capacity is not enough, it creates a new, larger array, and copies items from the old array to the new.

The Java API specification does not require any particular resizing behavior. In fact the current implementation in OpenJDK doubles the size of the array if it's small (64), otherwise it grows by 50%:

    // Double capacity if small; else grow by 50%
    int jump = (oldCapacity &lt; 64) ? (oldCapacity + 2) : (oldCapacity &gt;&gt; 1);

It seems that the"doubling" behavior is approximate: thanks to the "+2" after the first resize the capacity is 16+16+2 = 34. After the second resize it's 34+34+2 = 70. After that the array increases by 50% in every resize.

huangapple
  • 本文由 发表于 2020年8月26日 21:36:19
  • 转载请务必保留本文链接:https://go.coder-hub.com/63598894.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定