一、概述

假设你对ArrayDeque的源码一无所知，那么仅凭ArrayDeque名字来看的话，大概可以猜到它的实现和Array数组有关。

ArrayDeque是Java Collections Framework的一个成员，它的底层是基于定长数组实现的一个双端队列，如果数组存放满了，就会通过扩容机制重新生成一个更大的数组来存放数据，并且维护了双端队列头部元素的索引head和尾部元素的索引tail，使得它成为了一个逻辑上的循环数组，所谓循环是指元素到数组尾之后可以接着从数组头开始。

我们知道，数组非尾部的插入和删除效率是比较低的，然而，这在ArrayDeque上的表现却是效率高，这是怎么实现的呢？

接下来，本文会叙述ArrayDeque是如何维护这样一个循环数组，它的扩容机制是怎么实现的，这些都是ArrayDeque的核心所在；除此之外，本文还会叙述ArrayDeque的基本操作是怎样实现的，以及其它的细节。

好了，让我们一起逐步揭开它的神秘面纱。

二、ArrayDeque源码解读

2.1、继承关系

从UML类图中可以看到，ArrayDeque直接或间接实现了Iterable、Collection、Deque、Queue、Cloneable、Serializable这6个接口；ArrayDeque继承了AbstractCollection这个抽象类。

ArrayDeque和LinkedList在继承关系上是比较相似的，所以针对相同继承关系内容的叙述，比如说Deque接口、Queue接口的解读，本文不再次叙述，想去了解的话，可参考之前的Java集合系列：一文解读LinkedList源码「JDK11」一文。

2.2、成员变量

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


// 存储双端队列元素的数组。所有不包含双端队列元素的数组单元格始终为空。该数组始终至少有一个空槽（在尾部）。
transient Object[] elements;

// 双端队列头部元素的索引（这是将被 remove() 或 pop() 删除的元素）；或者任意数字 0 <= head < elements.length 等于 tail 如果双端队列为空。
transient int head;

// 将下一个元素添加到双端队列尾部的索引（通过 addLast(E)、add(E) 或 push(E)）； elements[tail] 始终为空。
transient int tail;

// 要分配的数组的最大大小。一些 VM 在数组中保留一些标题字。尝试分配更大的数组可能会导致 OutOfMemoryError: Requested array size exceeds VM limit
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

从成员变量head、tail的注释可以知道，数组的长度、头部元素、尾部元素都和这两个变量有关，那么当数组初始化后，这样的数组表现形式有4种情况：

头部元素的索引head == 尾部元素的索引tail，那么数组为空，也就是数组内部没有元素，如下图所示：

头部元素的索引head < 尾部元素的索引tail，那么头部元素为elements[head]，尾部元素为elements[tail-1]，元素索引从head到tail-1，如下图所示：

头部元素的索引head > 尾部元素的索引tail && 尾部元素的索引tail == 0，那么头部元素为elements[head]，尾部元素为elements[elements.length-1]，元素索引从head到elements.length-1，如下图所示：

头部元素的索引head > 尾部元素的索引tail && 尾部元素的索引tail != 0，那么头部元素为elements[head]，尾部元素为elements[tail-1]，元素索引从head到elements.length-1，然后再从0到tail-1，如下图所示：

2.3、构造方法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


// 构造一个空数组双端队列，其初始容量足以容纳16个元素
public ArrayDeque() {          
    elements = new Object[16]; 
}  

// 构造一个空数组双端队列，其初始容量足以容纳指定数量的元素
public ArrayDeque(int numElements) {                                        
    elements =                                                              
        new Object[(numElements < 1) ? 1 :                                  
                   (numElements == Integer.MAX_VALUE) ? Integer.MAX_VALUE : 
                   numElements + 1];                                        
}  

// 构造一个包含指定集合元素的双端队列，按照集合迭代器返回元素的顺序。（集合的迭代器返回的第一个元素成为第一个元素，或双端队列的前面。）
public ArrayDeque(Collection<? extends E> c) { 
    this(c.size());                            
    copyElements(c);                           
}   

// 将集合c的元素循环添加到队尾
private void copyElements(Collection<? extends E> c) { 
    c.forEach(this::addLast);                          
}                                                                                                                                                                                                      

我们看下第二个构造方法，需要传入一个numElements，这里有3种情况确定数组大小：

如果numElements < 1，那么数组大小为1；
如果numElements == Integer.MAX_VALUE，那么数组大小为Integer.MAX_VALUE；
如果numElements >= 1 && numElements < Integer.MAX_VALUE，那么数组大小为numElements + 1;

第三种情况：为什么要numElements + 1呢？

因为循环数组必须时刻至少留一个空位，tail变量指向下一个空位，为了容纳numElements个元素，至少需要numElements+1个位置。

2.4、核心方法

2.4.1、插入

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84


// ***********尾部插入***********

// 在此双端队列的末尾插入指定的元素
public boolean add(E e) {         
    addLast(e);                   
    return true;                  
}   

// 在此双端队列的末尾插入指定的元素
public void addLast(E e) {                    
    if (e == null)                            
        throw new NullPointerException();     
    final Object[] es = elements;      
    // 上面说了，tail索引对应的位置是一个空位，所以这里用来存放元素e       
    es[tail] = e;    
    // 计算tail的新索引位置，赋值给tail变量；如果(tail+1) >= es.length，那么tail = 0，否则就是tail+1                         
    // 判断是否head == tail，如果是则表示数组存满了，需要进行扩容
    if (head == (tail = inc(tail, es.length)))
        // 执行扩容
        grow(1);                              
}  

static final int inc(int i, int modulus) {
    if (++i >= modulus) i = 0;            
    return i;                             
}                                         

// 在此双端队列的末尾插入指定的元素
public boolean offer(E e) {        
    return offerLast(e);           
}                             

// 在此双端队列的末尾插入指定的元素
public boolean offerLast(E e) {         
    addLast(e);                         
    return true;                        
}  

// 将指定集合中的所有元素添加到此双端队列的末尾，就像对每个元素调用addLast一样，按照集合的迭代器返回它们的顺序。
public boolean addAll(Collection<? extends E> c) {    
    // s：原数组的元素个数
    // needed：所需的最低额外容量           
    final int s, needed;  
    // needed = 原数组的元素个数 + 集合c的长度 + 1（tail索引占位）- 原数组长度
    // 如果needed>0，说明数组元素个数 + 集合c的长度 + 1（tail索引占位) > 原数组长度，也就是原数组容量不够装集合c了，需要扩容                                      
    if ((needed = (s = size()) + c.size() + 1 - elements.length) > 0) 
        // 执行扩容
        grow(needed);  
    // 扩容完成后，将集合c的元素循环添加到队尾                                               
    copyElements(c);   
    // 如果此双端队列发生了更改，那么返回true                                               
    return size() > s;                                                
}    

// ***********头部插入*********** 

// 在此双端队列的前面插入指定的元素
public void addFirst(E e) {              
    if (e == null)                       
        throw new NullPointerException();
    final Object[] es = elements; 
    // 计算head的新索引位置，赋值给head变量；如果(head-1) < 0，那么head = es.length-1，否则就是head-1              
    es[head = dec(head, es.length)] = e; 
    // 判断是否head==tail，如果是则表示数组存满了，需要进行扩容
    if (head == tail)   
        // 执行扩容                 
        grow(1);                         
} 

static final int dec(int i, int modulus) {
    if (--i < 0) i = modulus - 1;         
    return i;                             
}                                          

// 在此双端队列的前面插入指定的元素
public boolean offerFirst(E e) {          
    addFirst(e);                          
    return true;                          
}     

// 将一个元素压入此双端队列所代表的堆栈。换句话说，将元素插入到这个双端队列的前面
public void push(E e) {         
    addFirst(e);                
}

2.4.2、删除

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61


// ***********尾部删除***********

public E removeLast() {                    
    E e = pollLast();                      
    if (e == null)                         
        throw new NoSuchElementException();
    return e;                              
}      

public E pollLast() {                                        
    final Object[] es; 
    // 记录tail的新索引位置                                      
    final int t;  
    // 计算tail的新索引位置，赋值给临时变量t；如果(tail-1) < 0，那么tail = es.length-1，否则就是tail-1   
    // 在数组中取出t索引对应的元素
    E e = elementAt(es = elements, t = dec(tail, es.length));
    if (e != null)      
        // 将t赋值给tail，然后将tail索引位置的元素置为null                              
        es[tail = t] = null;                                 
    return e;                                                
} 

// ***********头部删除***********

// 检索并删除由此双端队列表示的队列的头部。此方法与poll()的不同之处仅在于，如果此双端队列为空，它会抛出异常。
public E remove() {        
    return removeFirst();  
}      

// 检索并移除此双端队列所表示的队列的头部（换句话说，此双端队列的第一个元素），或者如果此双端队列为空，则返回null 。
public E poll() {       
    return pollFirst(); 
}          

public E removeFirst() {                   
    E e = pollFirst();                     
    if (e == null)                         
        throw new NoSuchElementException();
    return e;                              
}         

public E pollFirst() {                       
    final Object[] es;
    // 记录head索引位置                       
    final int h;
    // 在数组中取出head索引对应的元素                          
    E e = elementAt(es = elements, h = head);
    if (e != null) { 
        // 将head索引位置的元素置为null                     
        es[h] = null; 
        // 计算head的新索引位置，赋值给head；如果(head+1) >= es.length，那么head = 0，否则就是head+1                        
        head = inc(h, es.length);            
    }      
    // 返回head索引对应的元素                                 
    return e;                                
}                                            

// 从此双端队列表示的堆栈中弹出一个元素。换句话说，删除并返回此双端队列的第一个元素。
public E pop() {          
    return removeFirst(); 
}                                                                                                                                                                                          

2.4.3、检索

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49


// ***********头部检索*********** 

// 检索但不删除由此双端队列表示的队列的头部。此方法与peek不同之处仅在于，如果此双端队列为空，它会抛出异常。
public E element() {   
    return getFirst(); 
}            

// 检索但不删除由此双端队列表示的队列的头部，或者如果此双端队列为空则返回null 。
public E peek() {       
    return peekFirst(); 
}      

public E getFirst() {
    // 在数组中取出head索引对应的元素                      
    E e = elementAt(elements, head);       
    if (e == null)                         
        throw new NoSuchElementException();
    // 返回head索引对应的元素 
    return e;                              
} 

// 返回数组索引 i 处的元素。这是对泛型的轻微滥用，被 javac 所接受
static final <E> E elementAt(Object[] es, int i) {
    return (E) es[i];                             
}                                                  

public E peekFirst() {  
    // 在数组中取出head索引对应的元素               
    return elementAt(elements, head);  
}      

// ***********尾部检索***********

public E getLast() {                           
    final Object[] es = elements;  
    // 计算tail的新索引位置，如果(tail-1) < 0，那么tail = es.length-1，否则就是tail-1                                                        
    // 在数组中取出tail新索引对应的元素            
    E e = elementAt(es, dec(tail, es.length)); 
    if (e == null)                             
        throw new NoSuchElementException();    
    return e;                                  
}                            

public E peekLast() {                                     
    final Object[] es;  
    // 计算tail的新索引位置，如果(tail-1) < 0，那么tail = es.length-1，否则就是tail-1                                                        
    // 在数组中取出tail新索引对应的元素                                    
    return elementAt(es = elements, dec(tail, es.length));
}                                                                                                                                                                              

2.4.4、扩容机制

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61


// 将此双端队列的容量至少增加给定的数量
// need：所需的最低额外容量
private void grow(int needed) {                                                  
    // overflow-conscious code 

    // 获取旧容量大小                                                  
    final int oldCapacity = elements.length;    
    // 记录新容量大小                                 
    int newCapacity;                                                             
    // Double capacity if small; else grow by 50%   
    // jump：可译为跳跃，是基于旧容量计算的一个值，姑且叫跳跃容量
    // 如果oldCapacity < 64，那么jump = oldCapacity + 2，为什么这里是+2？+1不行吗？因为+2有两个含义，一个是给tail占位使用，另一个就是给新元素插入使用                             
    // 如果oldCapacity >= 64，那么jump = oldCapacity >> 1，右移一位表示除2，相当于oldCapacity/2
    int jump = (oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1);      
    // 如果跳跃容量 < 所需的最低额外容量，说明是计划赶不上变换，比如说调用构造方法时传入numElements为1，然后调用addAll方法，一次性添加一个很大的集合进来，就有可能出现这种情况
    // 如果（跳跃容量 + 旧容量）> MAX_ARRAY_SIZE，说明超过数组长度允许最大值了
    // 
    // newCapacity的值有两个情况：
    // 如果oldCapacity < 64，那newCapacity为oldCapacity * 2 + 2
    // 如果oldCapacity >= 64，那newCapacity为oldCapacity * 1.5
    if (jump < needed                                                            
        || (newCapacity = (oldCapacity + jump)) - MAX_ARRAY_SIZE > 0) 
        // 出现上面说的两种情况时，需要重新调整新容量大小           
        newCapacity = newCapacity(needed, jump); 
    // 将原数组的元素全部拷贝到新数组中去                                
    final Object[] es = elements = Arrays.copyOf(elements, newCapacity);         
    // Exceptionally, here tail == head needs to be disambiguated    
    // 此时数组只是扩大了，但是tail==head，即依然指向同一位置，为避免歧义，需要调整head和tail的位置  
    if (tail < head || (tail == head && es[head] != null)) {                     
        // wrap around; slide first leg forward to end of array 
        // 计算扩容后数组的剩余空间                 
        int newSpace = newCapacity - oldCapacity;      
        // 将旧数据复制到新位置                          
        System.arraycopy(es, head,                                               
                         es, head + newSpace,                                    
                         oldCapacity - head);  
        //  将旧位置的旧数据全部清空，head成为新位置⾸元素的位置                                  
        for (int i = head, to = (head += newSpace); i < to; i++)                 
            es[i] = null;                                                        
    }                                                                            
}     

// 边缘条件的容量计算，尤其是溢出
private int newCapacity(int needed, int jump) {                     
    final int oldCapacity = elements.length, minCapacity;  
    // 边界处理：判断旧容量 + 所需的最低额外容量是否超过数组长度允许最大值        
    if ((minCapacity = oldCapacity + needed) - MAX_ARRAY_SIZE > 0) {
        if (minCapacity < 0)                                        
            throw new IllegalStateException("Sorry, deque too big");
        return Integer.MAX_VALUE;                                   
    }        
    // 如果跳跃容量 < 所需的最低额外容量，说明是计划赶不上变换，比如说调用构造方法时传入numElements为1，然后调用addAll方法，一次性添加一个很大的集合进来，就有可能出现这种情况                                                      
    // 返回minCapacity = oldCapacity + needed 
    if (needed > jump)                                              
        return minCapacity;  
    // 如果最小容量minCapacity没有超过数组长度允许最大值，并且need <= jump
    // 边界处理：判断旧容量+跳跃容量是否超过数组长度允许最大值                                    
    return (oldCapacity + jump - MAX_ARRAY_SIZE < 0)                
        ? oldCapacity + jump                                        
        : MAX_ARRAY_SIZE;                                           
}                                                                                                                                              

下面通过一个小例子去演示扩容机制的执行流程，如下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


// 初始时，数组⻓度是5，真实索引是0-4，head = tail = 0
ArrayDeque<Integer> arrayDeque = new ArrayDeque<>(4);
// 执行完，head = 0, tail = 1；此时数组为：[1, null, null, null, null]
arrayDeque.addLast(1);
// 执行完，head = 4，tail = 1；此时数组为：[1, null, null, null, 2]
arrayDeque.addFirst(2);
// 执行完，head = 3，tail = 1；此时数组为：[1, null, null, 3, 2]
arrayDeque.addFirst(3);
// 执行完，head = 2，tail = 1；此时数组为：[1, null, 4, 3, 2]
arrayDeque.addFirst(4);
// 执行完，head = tail = 1，触发扩容；此时数组为：[1, 5, 4, 3, 2]，扩容容量为5*2+2
// 然后将旧数据复制到新位置，此时数组为：[1, 5, 4, 3, 2, null, null, null, 5, 4, 3, 2]
// 接着清掉旧数据，这时head = 8，tail = 1；此时数组为：[1, null, null, null, null, null, null, null, 5, 4, 3, 2]
arrayDeque.addFirst(5);
// 执行完，head = 8, tail = 2；此时数组为：[1, 6, null, null, null, null, null, null, 5, 4, 3 ,2]
arrayDeque.addLast(6);

2.5、其它方法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


// 返回此双端队列中的元素数
public int size() { 
    // i = tail，j = head，modulus = elements.length
    // 那么i -= j为i = i-j，代入后是tail = tail - head，然后判断计算后的tail是否 < 0
    // 如果 < 0，说明是head > tail的情况，对应于前面讲成员变量提到的数组情况3或4，这种情况下， tail会再次计算，tail = tail + elements.length，这样计算就可以求出数组的元素个数，不明白可以对照图来看
    // 如果 >= 0，说明是head <= tail的情况，对应于前面讲成员变量提到的数组情况1或2，这种情况下，直接把tail返回即可，因为if条件判断时已经计算过了，这样计算就可以求出数组的元素个数，不明白可以对照图来看
    return sub(tail, head, elements.length);
}

static final int sub(int i, int j, int modulus) {
    if ((i -= j) < 0) i += modulus;              
    return i;                                    
} 

// 如果此双端队列包含指定元素，则返回true 。更正式地说，当且仅当此双端队列包含至少一个满足o.equals(e)的元素e时才返回true 
public boolean contains(Object o) {                                       
    if (o != null) {                                                      
        final Object[] es = elements;  
        // to = (i <= end) ? end : es.length;  代入为：to = （head <= tail）? tail : es.length;                                   
        // 这里要判断head <= tail，如果是true，那么to==end，即to为tail，说明内层for循环只需要遍历区间[head,tail)中是否存在和o元素相同的元素，如果存在，返回true，否则break结束外层循环，返回false
        // 如果head > tail，如果为true，那么to = es.length，说明内层for循环要遍历区间[head,es.length)中是否存在和o元素相同的元素，如果存在，返回true
        // 否则，内存for循环执行完成，外层for循环此时执行 i = 0, to = end；
        // 接着内存for循环继续要遍历区间[0,tail)中是否存在和o元素相同的元素，如果存在，返回true，否则break结束外层循环，返回false
        for (int i = head, end = tail, to = (i <= end) ? end : es.length; 
             ; i = 0, to = end) {                                         
            for (; i < to; i++)                                           
                if (o.equals(es[i]))                                      
                    return true;                                          
            if (to == end) break;                                         
        }                                                                 
    }                                                                     
    return false;                                                         
}                                                                                                                                                                                                                                          

三、总结

在ArrayDeque的源码中，并没有与并发相关的代码，所以说ArrayDeque是非线程安全类，在并发环境下多个线程同时操作，会引发不可预知的错误。

ArrayDeque没有索引位置的概念，不能根据索引位置进行操作，所以没有更改操作，如set方法。

另外，ArrayDeque禁止添加空元素。最关键一点是：ArrayDeque用作堆栈时很可能比Stack快，用作队列时比LinkedList快。

Java集合系列：一文解读ArrayDeque源码「JDK11」

文章目录