ArrayDeque源码分析

techzealot
JCF, java

  1. 本质: 循环数组，支持双端存取

  2. JDK8中底层数组的大小必须为2的n次幂有多个好处:

    2.1 方便按顺序遍历数组中所有元素

    int mask=elements.length-1;
for(int i=head;i!=tail;i=(i+1)&mask){

}

    2.2 方便求size

    int size=(tail-head)&mask;

  3. 扩容时求下一个大于给定容量的最小2次幂算法

    //思路为将二进制第一个1后所有二进制位变为1，然后再+1
initialCapacity |= (initialCapacity >>> 1);
initialCapacity |= (initialCapacity >>> 2);
initialCapacity |= (initialCapacity >>> 4);
initialCapacity |= (initialCapacity >>> 8);
initialCapacity |= (initialCapacity >>> 16);
initialCapacity++;
//overflow back off,此时必为-2^31
if (initialCapacity < 0) {
    initialCapacity >>>= 1;//此时大小为2^30
}

    若是求不小于给定正整数的最小2次幂需要先-1,参见HashMap容量计算

    initialCapacity--;
initialCapacity |= (initialCapacity >>> 1);
initialCapacity |= (initialCapacity >>> 2);
initialCapacity |= (initialCapacity >>> 4);
initialCapacity |= (initialCapacity >>> 8);
initialCapacity |= (initialCapacity >>> 16);
initialCapacity++;

  4. 删除指定索引上的元素采用的原则是:尽可能移动最少量的元素

  5. 双端队列不允许存入null值,因为poll返回null用来表示队列为空,若允许存入null则与poll方法定义相悖