ArrayDeque源码分析
2021-09-24 本文已影响0人
gcno93
allocateElements（） 初始化容器
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 = new Object[initialCapacity];
}
上面的代码，我看了几个鈡，终于有点理解了，也不知对，还是错，这段代码主要是获取initialCapacity 最近的2的幂次方，下面是我分析的结果，有点长，我也不知怎么简化
initialCapacity |= (initialCapacity >>> 1);
initialCapacity |= (initialCapacity >>> 2);
initialCapacity |= (initialCapacity >>> 4);
initialCapacity |= (initialCapacity >>> 8);
initialCapacity |= (initialCapacity >>> 16);
假设我的initialCapacity = 32
我们先来看第一个 initialCapacity |= (initialCapacity >>> 1);
32的二进制是：00000000000000000000000000100000
initialCapacity >>> 1 也就是无符号右移1位，也就是等于16，
16的二进制：00000000000000000000000000010000
initialCapacity = initialCapacity | (initialCapacity >>> 1) 也就是 32 | 16
00000000000000000000000000100000 =====》32
或（|）
00000000000000000000000000010000 =====》16
00000000000000000000000000110000 =====》48
仔细观察，你会发现最后的结果110000（48） 比 原来的数据100000（32）第二位的0变成了1
我们继续 initialCapacity |= (initialCapacity >>> 2);
这时 initialCapacity = 48
48的二进制： 00000000000000000000000000110000
initialCapacity >>> 2 也就是 48 无符号右移2位 也就是等于12
12的二进制：00000000000000000000000000111100
00000000000000000000000000110000 =====》48
或（|）
00000000000000000000000000001100 =====》12
00000000000000000000000000111100 =====》60
仔细观察，你会发现最后的结果111100（60） 比 原来的数据100000（110000）第三位，第四位的0都变成了1
我们继续 initialCapacity |= (initialCapacity >>> 4);
这时 initialCapacity = 60
initialCapacity >>> 4 也就是 60无符号右移2位 也就是等于3
12的二进制：00000000000000000000000000000011
00000000000000000000000000111100 =====》48
或（|）
00000000000000000000000000000011 =====》3
00000000000000000000000000111111 =====》63
仔细观察，你会发现最后的结果111111（63） 比 原来的数据111100（110000）第五位，第六位的0都变成了1
经过这三步，我发现，这代码就是为了把100000（32）的不是1的位弄成1的位
那这是为什么呢？
你看看 1， 4 ，8 ，16，32，64的二进制就完事了
64 = 1000000
比喻上面的63 （111111） + （000001） = 1000000
所以上面的代码是为了找出 2的幂次方-1的数，也就是说32的最近2的幂次方不就是64吗？？？？
至于 为啥是 >>> 1 >>>2 >>>4 >>>8 >>>16 ?
>>> 1 : 这个时候110000（48） 比 原来的数据100000（32）第二位的0变成了1，那我们就可以确定2位，第1位，第二位肯定是1了，下面我直接>>>2 就好
>>> 2 这个时候111100（60） 比 原来的数据100000（110000）第三位，第四位的0都变成了1，那我们可以确定第1,2,3,4,肯定是1了，所以下面我直接>>>4就好
>>>4 这个时候 111111（63） 比 原来的数据111100（110000）第五位，第六位的0都变成了1，那我们可以确定 第1，2,3,4,5,6,都是1了，尽管下面>>>8,>>>16,最后的结果还是111111（63），因为
00000000000000000000000000111111 =====》63 >>>8 右移8位
或（|）
00000000000000000000000000000000 =====》0
00000000000000000000000000111111 =====》63 结果还是不变的
doubleCapacity() 扩容
private void doubleCapacity() {
assert head == tail;//head == tail是否相等
int p = head; //头部下标
int n = elements.length; //旧数组长度
int r = n - p; // 右边的元素
int newCapacity = n << 1;//原来的*2
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 = a;//elements = 新的数组
head = 0;//最开始0
tail = n;//旧数组长度
}
addFirst(E e) 首端插入元素，也就是在head的前面插入元素
public void addFirst(E e) {
if (e == null) //可见不能插入空值
throw new NullPointerException();
//第一次的时候 head =0 0-1=-1 但是-1的二进制是所有位都是1
//(head - 1) & (elements.length - 1) 也即是 elements.length - 1
//保证了head一定在0到elements.length- 1之间
elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail)
doubleCapacity();
}
addLast(E e) 在Deque的尾端插入元素，也就是在tail的位置插入元素，由于tail总是指向下一个可以插入的空位
public void addLast(E e) {
if (e == null) //可见不能插入空值
throw new NullPointerException();
elements[tail] = e; //应为tail总是指向下一个可插入的位置，所以可以直接赋值
//elements.length的长度一定是2的幂次方，所以elements.length - 1的二进制肯定是1111111
//当(tail + 1) & (elements.length - 1) 肯定是(tail + 1)
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity(); //扩容，上面已经分析了
}
pollFirst() 删除并返回Deque首端元素，也即是head位置处的元素
public E pollFirst() {
int h = head; //头部下标
@SuppressWarnings("unchecked")
E result = (E) elements[h]; //获取头部值
// Element is null if deque empty
if (result == null) //不等null 返回
return null;
elements[h] = null; // Must null out slot//头部元素删除
head = (h + 1) & (elements.length - 1);//h 需要加1
return result;//返回
}
pollLast() 作用是删除并返回Deque尾端元素，也即是tail位置前面的那个元素
public E pollLast() {
int t = (tail - 1) & (elements.length - 1); //最后一个
@SuppressWarnings("unchecked")
E result = (E) elements[t];//获取最后一个值
if (result == null) //null 返回null
return null;
elements[t] = null; //最后一个值删除
tail = t; //设置tail 下标，因为t 位置已经null 是下一个可以插入的位置，所以 tail = t;
return result;
}
peekFirst() 返回但不删除Deque首端元素，也即是head位置处的元素
public E peekFirst() {
// elements[head] is null if deque empty
return (E) elements[head]; //直接返回
}
peekLast() 返回但不删除Deque尾端元素，也即是tail位置前面的那个元素
public E peekLast() {
return (E) elements[(tail - 1) & (elements.length - 1)] ;//tail - 1的元素
}
