【Java并发编程】18、PriorityBlockingQueue源码分析,mgm娱乐场

【Java并发编程】18、PriorityBlockingQueue源码分析,

PriorityBlockingQueue是一个基于数组实现的线程安全的无界队列,原理和内部结构跟PriorityQueue基本一样,只是多了个线程安全。javadoc里面提到一句,1:理论上是无界的,所以添加元素可能导致outofmemoryerror;2.不容许添加null;3.添加的元素使用构造时候传入Comparator排序,要不然就使用元素的自然排序。

PriorityBlockingQueue是基于优先级,不是FIFO,这是个好东西,可以用来实现优先级的线程池,高优先级的先执行,低优先级的后执行。跟之前看过的几个队列一样,都是继承AbstractQueue实现BlockingQueue接口。

对于优先级的实现,是采用数组来实现堆的,大概样子画个图容易理解:

mgm娱乐场 1

堆顶元素时最小的,对于各左右子堆也保证堆顶元素最小。

内部结构和构造:

//基于数组实现的,如果构造没有传入容量,就是用默认大小
private static final int DEFAULT_INITIAL_CAPACITY = 11;

/**
 * 数组最大容量
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/**
 * 优先级队列数组,记住queue[n]的2个左右子元素在数组的位置为在queue[2*n+1]和queue[2*(n+1)]
 */
private transient Object[] queue;

/**
 * 队列元素个数
 */
private transient int size;

/**
 * 比较器,构造时可以选择传入,没有就null,到时候就使用元素的自然排序
 */
private transient Comparator<? super E> comparator;

/**
 * 重入锁控制多有操作
 */
private final ReentrantLock lock;

/**
 * 队列为空的时候条件队列
 */
private final Condition notEmpty;

/**
 * 自旋锁
 */
private transient volatile int allocationSpinLock;

/**
 * 序列化的时候使用PriorityQueue,这个PriorityBlockingQueue几乎一模一样
 */
private PriorityQueue q;

/**
 * 默认构造,使用默认容量,没有比较器
 */
public PriorityBlockingQueue() {
    this(DEFAULT_INITIAL_CAPACITY, null);
}

public PriorityBlockingQueue(int initialCapacity) {
    this(initialCapacity, null);
}

/**
 * 最终调用的构造
 */
public PriorityBlockingQueue(int initialCapacity,
                             Comparator<? super E> comparator) {
    if (initialCapacity < 1)
        throw new IllegalArgumentException();
    this.lock = new ReentrantLock();
    this.notEmpty = lock.newCondition();
    this.comparator = comparator;
    this.queue = new Object[initialCapacity];
}

内部结构和构造没有什么特别的地方,基于数组实现优先级的堆,记住数组元素queue[n]的左节点queue[2*n+1]和右节点queue[2*(n+1)],每次出队的都是queue[0]。

看下常用方法:

add、put、offer都是最终调用offer()方法:

public boolean offer(E e) {
    if (e == null)
        throw new NullPointerException();
    final ReentrantLock lock = this.lock;
    lock.lock();
    int n, cap;
    Object[] array;
    while ((n = size) >= (cap = (array = queue).length))
        tryGrow(array, cap); //如果元素数量大于数组大小了,那就自动扩容,无界
    try {
        Comparator<? super E> cmp = comparator; //这个看构造的时候入参,没有就用自然排序
        if (cmp == null)
            siftUpComparable(n, e, array); //所有插入都用从底向上调整
        else
            siftUpUsingComparator(n, e, array, cmp);
        size = n + 1;
        notEmpty.signal(); //添加后通知非空条件队列可以take
    } finally {
        lock.unlock();
    }
    return true;
}
//数组扩容
private void tryGrow(Object[] array, int oldCap) {
    lock.unlock(); // 数组扩容的时候使用自旋锁,不需要锁主锁,先释放
    Object[] newArray = null;
    if (allocationSpinLock == 0 &&
        UNSAFE.compareAndSwapInt(this, allocationSpinLockOffset,
                                 0, 1)) { //cas占用自旋锁
        try {
            int newCap = oldCap + ((oldCap < 64) ?
                                   (oldCap + 2) : // grow faster if small
                                   (oldCap >> 1)); //这里容量最少是翻倍
            if (newCap - MAX_ARRAY_SIZE > 0) {    // possible overflow
                int minCap = oldCap + 1;
                if (minCap < 0 || minCap > MAX_ARRAY_SIZE)
                    throw new OutOfMemoryError();
                newCap = MAX_ARRAY_SIZE; //扩容后,默认最大
            }
            if (newCap > oldCap && queue == array)
                newArray = new Object[newCap];
        } finally {
            allocationSpinLock = 0; //扩容后释放自旋锁
        }
    }
    if (newArray == null) // 到这里如果是本线程扩容newArray肯定是不为null,为null就是其他线程在处理扩容,那就让给别的线程处理
        Thread.yield();
    lock.lock(); //这里重新重入锁,因为扩容后还有其他操作
    if (newArray != null && queue == array) { //这里不为null那就复制数组
        queue = newArray;
        System.arraycopy(array, 0, newArray, 0, oldCap);
    }
}
//所有插入都用从下向上调整
private static <T> void siftUpComparable(int k, T x, Object[] array) {
    Comparable<? super T> key = (Comparable<? super T>) x;
    while (k > 0) {
        int parent = (k - 1) >>> 1; //取待插入节点的父节点
        Object e = array[parent];
        if (key.compareTo((T) e) >= 0) //如果比父节点大,那就无所谓退出,直接放在k位置
            break;
        array[k] = e; //比父节点小,按照k位置给父节点,然后从父节点开始继续向上查找
        k = parent;
    }
    array[k] = key;
}
//所有插入都用从底向上调整,跟siftUpComparable方法类似就是比较的时候使用了构造传入的comparator
private static <T> void siftUpUsingComparator(int k, T x, Object[] array,
                                   Comparator<? super T> cmp) {
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Object e = array[parent];
        if (cmp.compare(x, (T) e) >= 0)
            break;
        array[k] = e;
        k = parent;
    }
    array[k] = x;
}

所有的添加元素最后都是调用offer方法,2步:扩容+存储,大体流程为:

1.加锁,检查元素数量是否大于等于数组长度,如果是,那就扩容,扩容没必要使用主锁,先释放锁,使用cas自旋锁,容量最少翻倍,释放自旋锁,可能存在竞争,检查下,是否扩容,如果扩容那就复制数组,再度加主锁;

2.看构造入参是否有comparator,有就使用,没有就自然排序,从数组待插入位置父节点开始比较大,如果大于父节点,那就直接待插入位置插入,否则就跟父节点交换,然后循环向上查找,数量加1,通知非空条件队列take,最后释放锁。

看下几个出队操作:

public E poll() {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        return dequeue();
    } finally {
        lock.unlock();
    }
}

public E take() throws InterruptedException {
    final ReentrantLock lock = this.lock;
    lock.lockInterruptibly(); //响应中断
    E result;
    try {
        while ( (result = dequeue()) == null)
            notEmpty.await(); //如果take,数组没有元素是要阻塞的
    } finally {
        lock.unlock();
    }
    return result;
}

public E poll(long timeout, TimeUnit unit) throws InterruptedException {
    long nanos = unit.toNanos(timeout);
    final ReentrantLock lock = this.lock;
    lock.lockInterruptibly(); //响应中断
    E result;
    try {
        while ( (result = dequeue()) == null && nanos > 0)
            nanos = notEmpty.awaitNanos(nanos); //响应超时,每次唤醒的超时时间要检查
    } finally {
        lock.unlock();
    }
    return result;
}

public E peek() {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        return (size == 0) ? null : (E) queue[0]; //只是获取元素,不移除
    } finally {
        lock.unlock();
    }
}
//获取的基本都调用这个方法
private E dequeue() {
    int n = size - 1;
    if (n < 0)
        return null;
    else {
        Object[] array = queue;
        E result = (E) array[0];
        E x = (E) array[n]; //将最后一个数组元素取出作为比较基准
        array[n] = null; //出队,最后一个数组清掉,相当于堆的最底层最右的叶子节点清掉
        Comparator<? super E> cmp = comparator;
        if (cmp == null)
            siftDownComparable(0, x, array, n); //从顶向下调整
        else
            siftDownUsingComparator(0, x, array, n, cmp);
        size = n;
        return result;
    }
}
//从顶向下调整
private static <T> void siftDownComparable(int k, T x, Object[] array,
                                           int n) {
    if (n > 0) { //元素数量大于0,数组非空
        Comparable<? super T> key = (Comparable<? super T>)x;
        int half = n >>> 1;           // 最后一个叶子节点的父节点位置
        while (k < half) {
            int child = (k << 1) + 1; // 待调整位置左节点位置
            Object c = array[child]; //左节点
            int right = child + 1; //右节点
            if (right < n &&
                ((Comparable<? super T>) c).compareTo((T) array[right]) > 0)
                c = array[child = right]; //左右节点比较,取小的
            if (key.compareTo((T) c) <= 0) //如果待调整key最小,那就退出,直接赋值
                break;
            array[k] = c; //如果key不是最小,那就取左右节点小的那个放到调整位置,然后小的那个节点位置开始再继续调整
            k = child;
        }
        array[k] = key;
    }
}

出队的大体流程:

1.加锁,获取queue[0],清掉堆的最后一个叶子节点,并将其作为比较节点。等价于把最后一个叶子节点移到了queue[0]位置。然后从顶向下比较,找到新的queue[0]应该在的位置

2.调用从顶向下调整的方法:待调整位置节点左右节点和之前的叶子节点比较,如果之前叶子节点最小,那就直接放入待调整位置,如果是叶子节点小,那就取小的那个放入待调整位置,并且将小的部分重新循环查找,循环次数根据2分查找,基本是元素数量的一半就到找到位置。

再看一个remove,因为remove方法,2中调整方式都用到了:

public boolean remove(Object o) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        int i = indexOf(o); //查找o在数组中位置
        if (i == -1)
            return false;
        removeAt(i); //remove掉
        return true;
    } finally {
        lock.unlock();
    }
}
//o在数组中的位置
private int indexOf(Object o) {
    if (o != null) {
        Object[] array = queue;
        int n = size;
        for (int i = 0; i < n; i++)
            if (o.equals(array[i]))
                return i;
    }
    return -1;
}
//remove掉数组指定位置的元素
//跟之前take的dequeue相似的地方,dequeue是remove掉0的位置,然后调整也是从0的位置开始调整,这里是从指定位置调整
private void removeAt(int i) {
    Object[] array = queue;
    int n = size - 1;
    if (n == i) // removed last element
        array[i] = null;
    else {
        E moved = (E) array[n]; //跟dequeue一样也是最后一个叶子节点作为比较
        array[n] = null;
        Comparator<? super E> cmp = comparator;
        if (cmp == null)
            siftDownComparable(i, moved, array, n); //从指定位置调整
        else
            siftDownUsingComparator(i, moved, array, n, cmp);
        //经过从上向下调整后,如果是直接将比较节点放在待调整位置,那只能说明这个节点在以它为堆顶的堆里面最小,但不能说明从这个节点就向上查找就最大
        //这里需要自底向上再来一次调整
        if (array[i] == moved) { 
            if (cmp == null)
                siftUpComparable(i, moved, array);
            else
                siftUpUsingComparator(i, moved, array, cmp);
        }
    }
    size = n;
}

remove的时候有2个调整,先自顶向下调整,保证最小,然后再向上调整。

出处:http://blog.csdn.net/xiaoxufox/article/details/51860543

http://www.bkjia.com/Javabc/1309378.htmlwww.bkjia.comtruehttp://www.bkjia.com/Javabc/1309378.htmlTechArticle【Java并发编程】18、PriorityBlockingQueue源码分析,
PriorityBlockingQueue是一个基于数组实现的线程安全的无界队列,原理和内部结构跟PriorityQue…

概述

  首先,Priority翻译之后是优先级的意思,而PriorityQueue,也就是优先级队列的意思。优先级队列,和普通的先进先出(FIFO)的队列不同,优先队列每次取出的元素都是队列中优先级最高的,而PriorityQueue默认优先级是取出元素最小的值,当然也可以按照我们指定的规则来自定义优先级。
首先,我们先看下官方API:
https://docs.oracle.com/javase/8/docs/api/java/util/PriorityQueue.html
通过文档,我们可以看到PriorityQueue优先级队列的一些性质:

  1. PriorityQueue是基于优先级堆来实现的无界优先队列,是在JDK1.5之后引入的类;
  2. 优先队列的元素按照它们的自然排序顺序排列,或者根据使用的构造方法提供的比较器来进行排序;
  3. 优先队列不允许null元素;
  4. 优先队列不允许插入非可比的对象,有可能会抛出ClassCastException,比如对int排序,你添加了一个字符串类型的元素。
  5. 该优先队列每次取出的元素都是最小的。接口offer, poll,
    remove(),add方法,查询时间都是O(log(n)),
  6. 优先队列迭代器迭代的顺序无法保证,如果想有序遍历,请考虑使用Arrays.sort(priorityQueue.toArray());而对于remove(Object)
    and contains(Object)方法,查询是线性时间;而对于peek, element, and
    size方法,查询是常数时间。
  7. 该优先队列不是线程安全的,如果要在线程安全的场景下使用,建议使用线程安全的PriorityBlockingQueue类(优先级阻塞队列);

  PriorityQueue是基于堆来实现的,而堆这个数据结构是怎样的呢。我们来大概说下,学过数据结构的应该都知道,堆是利用完全二叉树来进行处理数据,而完全二叉树又是怎样的呢。

  若二叉树的深度是h,那么除第h层外,其他各层(1~h-1)层的结点数都达到最大个数,第h层所有的结点都连续集中在最左边,这就是完全二叉树。而堆就是基于这种数据结构来处理数据的。我们用一张图大致来看下完全二叉树:

mgm娱乐场 2

完全二叉树图示

  如图所示,图1是完全二叉树,而图二由于第三层所有的节点并非连续集中在最左侧,所以不是完全二叉树;而图三,由于第三层的结点没有达到最大个数(最大个数是4),所以也不是完全二叉树。

其中堆一般还分为两种:最大堆和最小堆。

  1. 顾名思义,最小堆就是根结点是所有数据中最小的元素,并且堆中每个结点的值总是不大于其孩子结点的值。
  2. 而最大堆就是根结点是所有结点中最大的元素,并且堆中每个结点的值总是不小于其孩子结点的值。

  而PriorityQueue则是基于最小堆来实现的,并且底层是通过数组来构建堆的数据结构。由于本文的重点并不是堆亦或是完全二叉树,所以堆的介绍就到这里来了。接下来我们来学习PriorityQueue的源码。

继承结构及属性

public class PriorityQueue<E> extends AbstractQueue<E>
    implements java.io.Serializable {

    // 使用数组来构造堆,也就是优先级队列
    transient Object[] queue;
    // 数组默认的初始化容量
    private static final int DEFAULT_INITIAL_CAPACITY = 11;
    // 队列的容量
    private int size = 0;
    // 比较器
    private final Comparator<? super E> comparator;
    // 结构化修改次数
    transient int modCount = 0;
    // 数组最大容量限制,Integer最大值-8是说一些虚拟机可能会在数组中保留一些header words的空间,
    // 所以没有取Integer最大值
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
}

首先,PriorityQueue是继承自AbstractQueue,AbstractQueue则是实现了Queue接口,封装了一些队列基础的方法。

  1. 优先队列底层使用数组来操作数据,并且数组的默认初始化容量是11,如果我们没有指定比较器,那系统将按照自然顺序来构建优先队列。
  2. 根据数组queue的注释,我们可以知道,父节点与子节点的下标值之间的关联关系是:childLeftNode= 2 * parentNode + 1;
    childRightNode= 2 * (parentNode + 1);,那么根据当前结点计算父结点也很简单:parentNode = (thisNode - 1) / 2

  Priority queue represented as a balanced binary heap: the two
children of queue[n] are queue[2n+1] and queue[2mgm娱乐场,(n+1)]. The
priority queue is ordered by comparator, or by the elements natural
ordering, if comparator is null: For each node n in the heap and each
descendant d of n, n <= d. The element with the lowest value is in
queue[0], assuming the queue is nonempty.

比如依次调用PriorityQueue的add方法,放入:3,5,7,1,9,12,18,7,6。画了一张图,大概如下:

mgm娱乐场 3

优先队列数据

构造方法

了解了优先队列的大致结构及父子间关联关系之后,我们来看几个常用的构造方法。

/**
 * 默认构造方法,初始化容量为11,比较器为空
 */
public PriorityQueue() {
    this(DEFAULT_INITIAL_CAPACITY, null);
}

/**
 * 指定具体容量的构造方法
 */
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) {
    if (c instanceof SortedSet<?>) {
        SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
        this.comparator = (Comparator<? super E>) ss.comparator();
        initElementsFromCollection(ss);
    }
    else if (c instanceof PriorityQueue<?>) {
        PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
        this.comparator = (Comparator<? super E>) pq.comparator();
        initFromPriorityQueue(pq);
    }
    else {
        this.comparator = null;
        initFromCollection(c);
    }
}

还有几个构造方法是是实现方式和上面这几个差不多,就不一一贴上了。

方法
add方法
public boolean add(E e) {
    return offer(e);
}

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;
}

首先,add方法内部全是通过offer方法来实现的,我们来看一下offer方法的大致实现过程:

  1. 判空,添加数据不能为null;
  2. 根据size与数组长度比较,判断是否扩容;
  3. 判断添加的是不是第一个元素,如果不是,进行调整,增加完元素之后,我们需要进行调整才能维护最大堆或最小堆的性质。而这里的这个调整在堆中被称为上浮(对应的方法是siftUp)。
grow方法

那么我们就接着来看扩容方法grow。

private void grow(int minCapacity) {
    int oldCapacity = queue.length;
    // Double size if small; else grow by 50%
    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);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

扩容的时候,先判断当前队列容量是否<64,如果是扩容一倍容量,如果不是,扩容原容量的1/2。而hugeCapacity方法我们也看到多次了,参考List的扩容就知道了,就是溢出检查,而拷贝的方法也还是Arrays.copyOf方法。

相关文章