带你从头看完java集合框架源码之Queue

带你从头看完java集合框架源码之Queue

目录

  1. java集合框架源码之总体预览
  2. java集合框架源码之List
  3. 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)

带你从头看完java集合框架源码之Queue

初始值是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;
    }

这个调整可以看这张图,插入是从下往上调整小顶堆

带你从头看完java集合框架源码之Queue

接下来看移除的方法,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接口结束

上一篇:HashSet源码分析


下一篇:List<String> list = new ArrayList<String>(20)扩容次数