带你从头看完java集合框架源码之Queue
目录:
上一篇文章我们介绍了List接口的实现类,这一篇我们来看Queue下的各种接口以及类
接口Deque(双端队列):
方法:基本上就是在Queue的基础上,增加了一些双端队列的特性,两头存取,我们可以看到基本每种操作都有两种形式(从头,或从尾)
//添加元素(头、尾),失败抛IllegalStateException异常
void addFirst(E e);
void addLast(E e);
//添加元素(头、尾),与add的区别是,失败返回false,不会抛异常
boolean offerFirst(E e);
boolean offerLast(E e);
//返回并删除元素(头、尾),失败抛NoSuchElementException异常
E removeFirst();
E removeLast();
//返回并删除元素(头、尾),队列为空时返回null
E pollFirst();
E pollLast();
//返回元素但不删除(头、尾),队列空时抛NoSuchElementException异常
E getFirst();
E getLast();
//返回元素但不删除(头、尾),队列空时返回null
E peekFirst();
E peekLast();
//删除第一次出现的指定元素(从头遍历和从尾遍历)
boolean removeFirstOccurrence(Object o);
boolean removeLastOccurrence(Object o);
从接口中方法的说明可以看出,如果实现类是大小受限的Deque,在修改队列时应该调用offer、poll、peek这些失败不会抛异常的方法。如果实现类容量不受限制,则应该调用add、remove、get这些方法
往下,有一个实现了Queue接口的抽象类AbstractQueue
类AbstractQueue:
同样,这个抽象类提供了Queue接口的最小实现。如果不允许添加nul元素时,抽象类的实现就是合适的。如果有其他需要,则应该继承抽象类,对方法进行重写
public abstract class AbstractQueue<E>
extends AbstractCollection<E>
implements Queue<E>
add方法、remove方法element方法调用了offer、poll和peek(继承与Queue),会抛出异常
接下来是Queue的两个实现类,ArrayDeque、PriorityQueue
类ArrayDeque:
特点:数组实现的双向循环队列,没有容量限制可以动态扩容,线程不安全,不允许添加NULL
This class is likely to be faster than {@link Stack} when used as a stack, and faster than {@link LinkedList} when used as a queue.
注释里有这么一段话,该类用做堆栈或者队列时,可能比Stack和LinkedList块,比Stack快是因为Stack的方法都用synchronized进行了同步,会产生开销
而比LinkedList快,是因为LinkedList是链表实现,而ArrayDeque是数组实现,链表在查找时是O(n)的时间复杂度,数组是O(1),这个是查找时的时间复杂度差距。至于在头尾添加元素,两个实现类都是O(1)的时间复杂度,但是由于LinkedList是链表实现,每次添加时需要new结点,new一个对象的开销是比较大的,而数组则不需要。
实际测试下,1000万添加,大概快个7倍左右
public static void main(String[] args) {
LinkedList<String> linkedList = new LinkedList<>();
long start = System.currentTimeMillis();
for (int i = 0; i < 10000000; i++) {
linkedList.add("1234");
}
long end = System.currentTimeMillis();
System.out.println("LinkedList" +" "+ (end - start));
ArrayDeque<String> arrayDeque = new ArrayDeque<>();
start = System.currentTimeMillis();
for (int i = 0; i < 10000000; i++) {
arrayDeque.add("1234");
}
end = System.currentTimeMillis();
System.out.println("ArrayDeque" +" " + (end - start));
}
输出:LinkedList 2313
ArrayDeque 313
//继承的和实现的基本都是老熟人了
public class ArrayDeque<E> extends AbstractCollection<E>
implements Deque<E>, Cloneable, Serializable
看看成员变量
//元素数组
transient Object[] elements;
//头指针
transient int head;
//尾指针
transient int tail;
//最小初始化容量8,且容量必须是2的倍数,为啥呢?后边说
private static final int MIN_INITIAL_CAPACITY = 8;
往下,分析构造方法
//无参构造方法,默认初始容量16
public ArrayDeque() {
elements = new Object[16];
}
//有参构造,指定容量,调用allocateElements
public ArrayDeque(int numElements) {
allocateElements(numElements);
}
//有参构造,传入一个集合,调用allocateElements确认容量,调用addAll方法添加元素
public ArrayDeque(Collection<? extends E> c) {
allocateElements(c.size());
addAll(c);
}
看看确定容量的allocateElements方法
private void allocateElements(int numElements) {
elements = new Object[calculateSize(numElements)];
}
调用了calculateSize,接着看:
private static int calculateSize(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
}
return initialCapacity;
}
这段代码是找到一个值,他的大小是大于8和numElements且最接近numElements的2的方幂。也就是8<2^n && numElements<2^n
很多人看到中间一连串|=就蒙了,我也是,查了一下资料后才理解为什么这样操作可以获得比numElements大且最接近numElements的2^n。原理是这样的,看下面这张图,来源(https://www.imooc.com/article/75047)
初始值是89,图中对应的是二进制01011001,这时候我们想找比89大的最小2的方幂,这个值我们都知道是10000000(二进制),就是把01011001中1的最高位
左移,然后剩下的变成0就可以了,怎么通过位运算来完成这件事呢?我们可以把10000000 看做 01111111 + 00000001,也就是说把最高位的1之后的所有位都变成1,最后再+1,就可以得到这个值,那么问题又来了,怎么把所有位变成1呢?
这时,我们可以关注从右往左的任意一个为1的值,假设是第n位。令他右移一位,然后和原来的值或,这样,得到的值中,第n位和第n - 1位就都为1了,这样我们就得到了两个1
之后,因为第n和n - 1位都是1,我们右移两位,和原来的值或,得到的值中,除了n和n - 1外,第n - 2和n - 3位也是1了。是不是有点感觉了?java中int是32位,所以只需要右移1、2、4、8、16位,每次都和移位前的值或一次,就可以把最高位之后的所有位都变成1,之后+1,就可以得到最接近numElements的2^n
我们用50来推演一遍,50的二进制是0011 0010(省略前24位为0的值,这里只看8位),按照前面解释的,任意找一个为1的位观察,这里我们挑第二位(从右往左)
先右移一位,得到0001 1001,和0011 0010或,得到0011 1011,现在可以看到,第2(n)位和第1(n - 1)位都是1了
然后右移两位,得到000 1110,和0011 1011或,得到0011 1111
然后右移四位,得到0000 0011,和0011 1111或,得到0011 1111,从这里就已经可以看到,1的最高位之后的所有位已经都是1了
之后8...16,都是同样的效果
方法最后是判断是不是溢出了,如果溢出了直接返回最大值2^30次方
看一看扩容方法,容量不足是扩大两倍
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 = a;
head = 0;
tail = n;
}
前面讲过容量必须是2的倍数,扩容也是两倍扩容,确定容量大小也是二的倍数,这是为什么呢?我们来看看addFirst/addLast方法
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail)
doubleCapacity();
}
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
elements[tail] = e;
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}
//add调用的是addLast方法,add默认插到队尾
public boolean add(E e) {
addLast(e);
return true;
}
ArrayDeque是个循环双端队列,容量是二的倍数是为了取模方便,容量是二的倍数,减一之后就成了掩码,当head = length时,和length - 1与,就变成了0,当head = -1时(补码表示为全1),和length - 1与,就变成了length - 1,达到循环的效果。当head != length - 1时,和length - 1与还是保持原来的值(因为2^n的二进制是最高位为1,后边全是0,减一后,除了原最高位外,剩余位全是1,任意值和这个值与,在没有溢出时可以起到保留原来位的效果,溢出时则得到0)
后面的方法,addFirst/Last、getFirst/Last等等基本上和介绍Queue接口的差不多,都是在相互调用
为啥要设置那么多方法呢?其实主要是为了模拟不同的数据结构,如栈操作:pop,push,peek,队列操作:add,offer,remove,poll,peek,element,双端队列操作:addFirst,addLast,getFirst,getLast,peekFirst,peekLast,removeFirst,removeLast,pollFirst,pollLast。不过确实稍微多了一点。(引用自(https://www.imooc.com/article/75047))
最后看一眼迭代器,和其他集合类不同的是,ArrayDeque没有使用modcount来实现fail-fast机制,而是在next方法中使用这样一个判断
if (tail != fence || result == null)
throw new ConcurrentModificationException();
就是检查标记的尾指针fence和当前尾指针tail是否一致或者当前获取的元素是不是空,这种检查是偏弱的,例如我先移除一个元素再添加一个元素,这时tail指针的值还是没变,但是集合结构已经被我修改过了,这样就没办法检测出并发修改异常了
类PriorityQueue:
看Queue接口下最后一个实现类了
特点:基于优先级的队列,底层数据结构是数组实现的二叉小顶堆(每一个非叶子节点都小于他的左右节点,可以用完全二叉树表示),存放进去的元素基于构造时提供的Comparator排序或基于自然排序,不允许存放null且存放进去的元素要可排序,该类线程不安全。
二叉树的数组表示法如下:
当前结点:index
当前结点的左结点:(index * 2 + 1)
当前结点的右节点:(index * 2 + 2)
当前结点的父结点:(index - 1)/ 2
public class PriorityQueue<E> extends AbstractQueue<E>
implements java.io.Serializable
看一看成员变量
//序列化ID
private static final long serialVersionUID = -7720805057305804111L;
//默认容量大小
private static final int DEFAULT_INITIAL_CAPACITY = 11;
//存放元素的数组
transient Object[] queue;
//元素个数
private int size = 0;
//比较器
private final Comparator<? super E> comparator;
//修改结构的次数
transient int modCount = 0;
构造方法:有点多,一个一个分析
//无参构造,调用另一个构造方法public PriorityQueue(int initialCapacity,Comparator<? super E> comparator)
public PriorityQueue() {
this(DEFAULT_INITIAL_CAPACITY, null);
}
//根据容量构造,同样调用另一个构造方法public PriorityQueue(int initialCapacity,Comparator<? super E> comparator)
public PriorityQueue(int initialCapacity) {
this(initialCapacity, null);
}
//构造一个默认容量指定比较器的队列
public PriorityQueue(Comparator<? super E> comparator) {
this(DEFAULT_INITIAL_CAPACITY, comparator);
}
//构造一个指定容量指定比较器的队列
public PriorityQueue(int initialCapacity,
Comparator<? super E> comparator) {
// Note: This restriction of at least one is not actually needed,
// but continues for 1.5 compatibility
if (initialCapacity < 1)
throw new IllegalArgumentException();
this.queue = new Object[initialCapacity];
this.comparator = comparator;
}
//根据集合构造队列
public PriorityQueue(Collection<? extends E> c) {
//判断c是不是排序Set的子类
if (c instanceof SortedSet<?>) {
SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
//获取c的比较器,调用initElementsFromCollection
this.comparator = (Comparator<? super E>) ss.comparator();
initElementsFromCollection(ss);
}
//否则判断是不是PriorityQueue的子类
else if (c instanceof PriorityQueue<?>) {
PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
//获取比较器,调用initFromPriorityQueue
this.comparator = (Comparator<? super E>) pq.comparator();
initFromPriorityQueue(pq);
}
else {
//否则比较器为空,调用initFromCollection
this.comparator = null;
initFromCollection(c);
}
}
//这个和上面PriorityQueue的情况一样
public PriorityQueue(PriorityQueue<? extends E> c) {
this.comparator = (Comparator<? super E>) c.comparator();
initFromPriorityQueue(c);
}
//这个和上面SortedSet的情况一样
public PriorityQueue(SortedSet<? extends E> c) {
this.comparator = (Comparator<? super E>) c.comparator();
initElementsFromCollection(c);
}
构造方法中调用了initElementsFromCollection、initFromPriorityQueue和initFromCollection初始化方法,我们来看这几个方法
//这个方法就是拷贝数组,然后判断是否有空元素
private void initElementsFromCollection(Collection<? extends E> c) {
Object[] a = c.toArray();
// If c.toArray incorrectly doesn't return Object[], copy it.
if (a.getClass() != Object[].class)
a = Arrays.copyOf(a, a.length, Object[].class);
int len = a.length;
if (len == 1 || this.comparator != null)
for (int i = 0; i < len; i++)
if (a[i] == null)
throw new NullPointerException();
this.queue = a;
this.size = a.length;
}
//判断是不是PriorityQueue集合,不是的话调用initFromCollection
private void initFromPriorityQueue(PriorityQueue<? extends E> c) {
if (c.getClass() == PriorityQueue.class) {
this.queue = c.toArray();
this.size = c.size();
} else {
initFromCollection(c);
}
}
//先调用initElementsFromCollection拷贝数组,然后调用heapify调整堆的顺序
private void initFromCollection(Collection<? extends E> c) {
initElementsFromCollection(c);
heapify();
}
这里调用了heapify调整堆成为二叉小顶堆,我们看看是如何调整的
private void heapify() {
for (int i = (size >>> 1) - 1; i >= 0; i--)
siftDown(i, (E) queue[i]);
}
可以看到对每个非叶子结点调用了siftDown方法,我们看看siftDown
private void siftDown(int k, E x) {
if (comparator != null)
siftDownUsingComparator(k, x);
else
siftDownComparable(k, x);
}
根据有没有比较器分别调用siftDownUsingComparator和siftDownComparable,这两个方法只是使用的比较器不同而已,如果队列没有指定比较器则使用元素的比较器,逻辑上没有区别,我们看其中一个siftDownComparable就好
private void siftDownComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>)x;
//求当前最后一个非叶子结点的下标 + 1
int half = size >>> 1; // loop while a non-leaf
//调整的结点是非叶子结点时
while (k < half) {
//获得该结点左节点的下标
int child = (k << 1) + 1; // assume left child is least
Object c = queue[child];
//获得该结点右节点的下标
int right = child + 1;
//比较左右结点哪个比较小,然后跟x结点比较
if (right < size &&
((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
//c是临时变量,保存左右结点中最小的那个
c = queue[child = right];
//如果x结点比左右都小,则不需要调整
if (key.compareTo((E) c) <= 0)
break;
//否则x结点和左右结点中最小的那个互换,然后调整那个被换的结点
queue[k] = c;
k = child;
}
queue[k] = key;
}
往下,看一下扩容的grow方法
private void grow(int minCapacity) {
int oldCapacity = queue.length;
// Double size if small; else grow by 50%
//扩容的规则,如果当前大小小于64,则新容量 = 旧容量 + 2;否则,新容量 = 旧容量 * 1.5
int newCapacity = oldCapacity + ((oldCapacity < 64) ?
(oldCapacity + 2) :
(oldCapacity >> 1));
// overflow-conscious code
//判断溢出
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
queue = Arrays.copyOf(queue, newCapacity);
}
判断溢出的方法也是老方法了,这里就不再赘述
接下来是添加元素的方法,add调用的是offer,我们看offer
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
modCount++;
int i = size;
//容量不够,扩容
if (i >= queue.length)
grow(i + 1);
size = i + 1;
if (i == 0)
queue[0] = e;
else
//插入并从下往上调整
siftUp(i, e);
return true;
}
因为小顶堆的排序,插入元素有可能会破坏排序,所以每次插入都需要调整,看看siftUp方法
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}
同样的也是根据比较器调用不同的方法,我们看其中一个就好
private void siftUpUsingComparator(int k, E x) {
while (k > 0) {
//找到要插入节点的父节点
int parent = (k - 1) >>> 1;
Object e = queue[parent];
//不会破坏排序,不需要调整
if (comparator.compare(x, (E) e) >= 0)
break;
//否则互换父节点和子节点
queue[k] = e;
//向上调整
k = parent;
}
queue[k] = x;
}
这个调整可以看这张图,插入是从下往上调整小顶堆
接下来看移除的方法,remove调用了removeAt
private E removeAt(int i) {
// assert i >= 0 && i < size;
modCount++;
int s = --size;
if (s == i) // removed last element
queue[i] = null;
else {
//获取当前最后一个结点
E moved = (E) queue[s];
queue[s] = null;
//直接把要移除的结点换成队列最后的结点,然后该顶点的堆进行调整
siftDown(i, moved);
//这里是一个判断,判断刚刚换过去的那个结点是不是就是这个堆的堆顶,如果是的话,有可能破坏了上层的排序,要进行向上调整
if (queue[i] == moved) {
//向上调整
siftUp(i, moved);
if (queue[i] != moved)
return moved;
}
}
return null;
}
poll方法和removeAt方法类似,但是他移除的是堆顶,所以和最后一个元素互换之后,只需要从上往下调整
至此,PriorityQueue类就看完了,Queue接口结束