电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛

标题: Java 容器源码分析之Queue（3） [打印本页]

作者: look_w 时间: 2018-12-17 17:40 标题: Java 容器源码分析之Queue（3）

ArrayDeque 有了我们前面几篇分析的基础，我们可以很容易猜到ArrayDeque的内部实现机制。它的内部使用一个数组来保存具体的元素，然后分别使用head, tail来指示队列的头和尾。他们的定义如下：
Java代码 [url=]

[/url]

[url=]

[/url]
private transient E[] elements; private transient int head; private transient int tail; private static final int MIN_INITIAL_CAPACITY = 8; [url=]

[/url]

ArrayDeque的默认长度为8，这么定义成2的指数值也是有一定好处的。在后面调整数组长度的时候我们会看到。关于tail需要注意的一点是tail所在的索引位置是null值，在它前面的元素才是队列中排在最后的元素。
调整元素长度在调整元素长度部分，ArrayDeque采用了两个方法来分配。一个是allocateElements，还有一个是doubleCapacity。allocateElements方法用于构造函数中根据指定的参数设置初始数组的大小。而doubleCapacity则用于当数组元素不够用了扩展数组长度。下面是allocateElements方法的实现：
Java代码 [url=]

[/url]

[url=]

[/url]
private void allocateElements(int numElements) { int initialCapacity = MIN_INITIAL_CAPACITY; // Find the best power of two to hold elements. // Tests "<=" because arrays aren't kept full. if (numElements >= initialCapacity) { initialCapacity = numElements; initialCapacity |= (initialCapacity >>> 1); initialCapacity |= (initialCapacity >>> 2); initialCapacity |= (initialCapacity >>> 4); initialCapacity |= (initialCapacity >>> 8); initialCapacity |= (initialCapacity >>> 16); initialCapacity++; if (initialCapacity < 0) // Too many elements, must back off initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements } elements = (E[]) new Object[initialCapacity]; } [url=]

[/url]

这部分代码里最让人困惑的地方就是对initialCapacity做的这一大堆移位和或运算。首先通过无符号右移1位，与原来的数字做或运算，然后在右移2、4、8、16位。这么做的目的是使得最后生成的数字尽可能每一位都是1。而且很显然，如果这个数字是每一位都为1，后面再对这个数字加1的话，则生成的数字肯定为2的若干次方。而且这个数字也肯定是大于我们的numElements值的最小2的指数值。这么说来有点绕。我们前面折腾了大半天，就为了求一个2的若干次方的数字，使得它要大于我们指定的数字，而且是最接近这个数字的数。这样子到底是为什么呢？因为我们后面要扩展数组长度的话，有了它这个基础我们就可以判断这个数字是不是到了2的多少多少次方，它增长下去最大的极限也不过是2的31次方。这样他每次的增长刚好可以把数组可以允许的长度给覆盖了，不会出现空间的浪费。比如说，我正好有一个数组，它的长度比Integer.MAX_VALUE的一半要大几个元素，如果我们这个时候设置的值不是让它为2的整数次方，那么直接对它空间翻倍就导致空间不够了，但是我们完全可以设置足够空间来容纳的。
我们现在再来看doubleCapacity方法：
Java代码 [url=]

[/url]

[url=]

[/url]
private void doubleCapacity() { assert head == tail; int p = head; int n = elements.length; int r = n - p; // number of elements to the right of p int newCapacity = n << 1; if (newCapacity < 0) throw new IllegalStateException("Sorry, deque too big"); Object[] a = new Object[newCapacity]; System.arraycopy(elements, p, a, 0, r); System.arraycopy(elements, 0, a, r, p); elements = (E[])a; head = 0; tail = n; } [url=]

[/url]

有了前面的讨论，它只要扩展空间容量的时候左移一位，这就相当于空间翻倍了。如果长度超出了允许的范围，就会发生溢出，返回的结果就会成为一个负数。这就是为什么有 if (newCapacity < 0)这一句来抛异常。

欢迎光临电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛 (http://bbs.eccn.com/)