大家好,又见面了,我是你们的朋友全栈君。
ArrayDeque双端队列完全解析
重点:
我们知道,ArrayDeque是通过数组实现队列功能 的;而且具有对数组头尾双端添加和移除对象的功能,但如果数组不能实现循环功能,会出现以下情况
图一
在构建一个ArrayDeque对象时,会初始化head和tail的值为0.当有对象加入数组时,tail的值加1,当有对象出列时,head的值会加1. 而head值 == tail值 ,可以帮我们判断数组是已经满。
如果数组容量固定的情况下,从尾追加数据,从头出列数据,会出现实际数组有空的单元,但却tail会超过数组容量的情况,这种现象称为“假溢出” ;但往往,不可能是一种容量固定的数组,一般会有实现自动扩容的方法,但即便可以扩容,按照上面的逻辑,数组容量不断扩大,tail值一直向后,但从头出列的数据越来起多,前面空的内存单造成的浪费更是不能忽略了。
再往下想,不是说Deque接口实现了头和尾添加和删除数据的功能吗?那它不是可以从头添加数据,不就可以利用到前面已经出列的空的单元吗? 但如果就是单纯的就是在往后追加数据呢?那前面空出的内存单元,就这样舍弃掉?简直“暴殄天物”。
所以,为了解决数组单元浪费的问题,就产生了循环数组。且看图 图二
从上图可知,当tail值超过数组索引后,就回到了索引为0的地方,实现了内存单元循环利用。 你可以想象成,数组尾和头尾首相连,形成逻辑上的”环形“。 但同时,你要清楚,上图中的例子,是头部已经有出列,有空的单元时,tail值回到的索引0的地方,但如果索引为0的地方有值时,此时,想要实现新对象的保存,也只能重新去扩容了。 可知,循环数组可以实现有限数组容量的的高效利用,但新值不会覆盖原值。
讲到这里,如果有细心猿会现,我图一在初始化时,tail和head都是对应索引为0的数组,我说数据从尾部追加,那应该调用的是addlast方法,但上图添加数据分明是从索引0开始追加的,是按照数组顺序的,和实际情况不相符啊。而且,如果从后面追加数据的话,你的tail值怎么移动?
正如猿发现的问题一样,确实,我上面的例子不够严谨,请看下图
图三
我先调用addLast方法,把1加入数组,1位于数组尾部 我再调用addLast方法,把2加入数组,2替换1的位置,追加尾部,1向前存储一个单元 我先调用addFirst方法,把A加入数组,A位于数组头部 我再调用addFirst方法,把B加入数组,B替换A的位置,放置数组头部,A向后存储一个单元
所以,严格来说,无论是addLast 还是addFirst方法,都不按照数组顺序加入数据的(按照索引顺序);而是根据头尾,新追加数据会占用头尾位置,原来头尾位置的数据后移或前移 ;
那么,tail值和head值怎么移动呢? 其实,每增加一个对象,tail值就会+1 ,每移除一个对象,head值+1 ; 并非如图一那样,head和tail值都要从左到右移动的那种样式。 tail值和head值可以理作为一个标的,最后,通过tail和head值来确定数组是否已满
那么这个标的是怎么实现判断数组已满的呢?
jdk源码里面,通过 (tail = (tail + 1) & (elements.length – 1)) == head 来判断数组已满 ,并且要求数组每次扩容的长度为2的n次方来使得上面的等式有效;
这个怎么理解呢?
注意,
我们来看一个源码
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
elements[tail] = e;
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}
在这个方法中,tail值的+1是放在if判断中的,并没有单独写tail++ 这样的语句,而不管if条件是否成立,tail的值都是会+1,而我上图中的标注的tail值是已+1过的。
情况一,数组未出列,往数组里添加8个元素后,tail值每次+1,最后值为8 代入公式中(tail = (tail + 1) & (elements.length – 1)) == head 为(8 & 7)==0 转为二进制为(1000 & 111 )==0 000 结果返回true.
情况二,数组出列2个,往数里面加了10个数据,tail值变为10.代入公式为 (10 & 7)==2 转为二进制为(1010 & 111)=10 ,返回true.
可见,上述公式是在数组为2的n次长度时,是成立的。但如果是非2的n次方容量呢,还成立吗?
举例
代入公式为 (7 & 6)==0 转为二进制为 ((111 & 110)=110 )≠ 000
当然上面的例子你也可以再多找几个,你会发现真的只有当数组容量为2的n次方时,jdk提供的等式是成立的。
另外,ArrayDeque提供了可以指定数组容量的构造器,那我输入非2的n次方数值,内部会发生什么?
private void allocateElements(int numElements) {
elements = new Object[calculateSize(numElements)];
}
private static int calculateSize(int numElements) {
int initialCapacity = MIN_INITIAL_CAPACITY;
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
}
return initialCapacity;
}
它的内部是通过位移动算符 >>> 和 位运算符 | 实现的 | = 这样的符号表示右边的值和左边的值 通过 位运算符 | 操作后赋值给左边的值。 通过一系列的运算符操作,随机输入的数值,最后转换成比原数值大,且和它最近的2的n次方数值。
费话不说, 我们来举例 传入 12
真是妙哉!
其实也好理解,因为ArrayDeque实现了双端的操作 所以使得这一切都成为了可能
特别注意,在操作数组时,有些方法遇问题,会直接抛出异常;有些方法,会反回Special value 也就是null值
更多简析思路,可参考以下博文
Java 容器源码分析之 Deque 与 ArrayDeque
Java进阶–ArrayDeque双端队列完全解析 End!
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/191274.html原文链接:https://javaforall.cn