java - 关于Java中ArrayDeque的实现

Question

文档说：

Deque 接口的可调整大小的数组实现。数组双端队列没有容量限制；它们根据需要增长以支持使用

但是我仍然想了解 ArrayDeque 的结构到底是什么，调整大小是如何工作的。如果有人可以提供可靠的来源，我可以找到答案，那将是很棒的。根据我发现的一些谷歌结果，它可能实现为一个循环数组。这是真的吗？什么是增长政策？它类似于 ArrayList 吗？如果是，ArrayDeque 在最后添加或删除元素等操作上是否具有与 ArrayList 相似的性能？

谢谢你。

Answer 1

ArrayList和的增长策略ArrayDeque没有记录，并且可能在 JDK 实现甚至 JDK 版本之间有所不同。例如，在Open JDK 6中它是(n*3/2+1).，但在Open JDK 8中它是(n*3/2). 同样在 JDK 6ArrayList中，默认构造函数最初是使用 10 个元素的数组创建的，而在 JDK 8 中，它仅在添加至少一个元素时才分配一个数组。

实现更改的ArrayDeque频率低于ArrayList. 它始终在内部使用大小为 2 的数组，默认情况下从16默认开始，并在必要时将其加倍，因此内存占用可能会有所不同，ArrayList并且ArrayDeque（因为ArrayDeque平均而言，您将有更少的重新分配，但更多的内存浪费）。

除非需要重新分配ArrayList，否则添加到尾部的速度大致相同。ArrayDeque重新分配事件可能发生在不同的点。例如，默认情况下，第一次重新分配 forArrayList将在添加元素 #11 时发生，但 forArrayDeque将发生在元素 #16 上。

的优点ArrayDeque是能够像尾部一样快地向头部添加/删除元素。相反，ArrayList它将O(n)及时完成，因为它必须移动所有现有元素。因此ArrayDeque，当您需要添加/删除头部和尾部时使用。如果您只需要修改尾部，通常ArrayList是首选。