关于ArrayDeque在Java中的实现 [英] About implementation of ArrayDeque in Java

问题描述

文档说:

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

Resizable-array implementation of the Deque interface. Array deques have no capacity restrictions; they grow as necessary to support usage

但是，我仍然想了解ArrayDeque的确切结构，以及调整大小的工作方式.如果有人可以提供可靠的消息来源，我也可以找到答案，那也很好.根据我发现的一些Google结果，它可能实现为循环数组.是真的吗增长政策是什么?它类似于ArrayList吗?如果是，那么ArrayDeque在类似添加或删除元素的操作中是否具有与ArrayList相似的性能?

However I still want to understand what exactly the structure of ArrayDeque is, how the resizing works. Also it would be great if someone could provide a reliable source where I can find the answer. According to some of the Google results I found, it is possibly implemented as a circular array. Is it true? And what is the grow policy? Is it similar to ArrayList? If it is, does ArrayDeque have a similar performance to ArrayList in the operations like adding or removing the element at the end?

谢谢.

推荐答案

未记录ArrayList和ArrayDeque的增长策略，并且在JDK实现甚至JDK版本之间可能有所不同.例如，在

The grow policy of ArrayList and ArrayDeque is not documented and may vary between JDK implementations and even JDK versions. For example, in Open JDK 6 it was (n*3/2+1), but in Open JDK 8 it's (n*3/2). Also in JDK 6 ArrayList with default constructor was initially created with 10 elements array while in JDK 8 it allocates an array only when at least one element is added.

The ArrayDeque implementation changes less often than ArrayList. It always uses internally the power-of-two sized array starting with 16 by default and doubling it when necessary, thus memory footprint may be different for ArrayList and ArrayDeque (for ArrayDeque you will have in average less reallocations, but more wasted memory).

对于ArrayList和ArrayDeque，添加到尾部的速度大致相同，除非需要重新分配.重新分配事件可能发生在不同的位置.例如，默认情况下，添加元素#11时将首先重新分配ArrayList，而对于ArrayDeque则将在元素#16上重新分配.

Addition to the tail is roughly equally fast for both ArrayList and ArrayDeque unless reallocation is necessary. Reallocation events may occur at different points. For example, by default first reallocation for ArrayList will occur when adding element #11, but for ArrayDeque it will occur on element #16.

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

The advantage of ArrayDeque is ability to add/remove elements to the head as fast as to the tail. In contrast, ArrayList will do it in O(n) time as it will have to move all the existing elements. Thus use ArrayDeque when you need to add/remove both to head and tail. If you need to modify the tail only, usually ArrayList is preferred.

这篇关于关于ArrayDeque在Java中的实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！