读PriorityBlockingQueue源码记录

简介

    PriorityBlockingQueue是一个没有边界的优先级队列，它的排序规则和 java.util.PriorityQueue一样。PriorityBlockingQueue中允许插入null对象,所有插入PriorityBlockingQueue的对象必须实现java.lang.Comparable接口，队列优先级的排序规则就是按照我们对这个接口的实现来定义的。另外，从PriorityBlockingQueue获得一个迭代器Iterator，但这个迭代器并不保证按照优先级顺序进行迭代。

    PriorityBlockingQueue底层是基于数组实现的堆结构，这里对堆结构不做多介绍，可以参考

堆，最大堆（大顶堆）及最小堆（小顶堆）的实现​
常用数据结构与算法：二叉堆(binary heap)​

探索PriorityBlockingQueue

1.主要属性


//默认容量
private static final int DEFAULT_INITIAL_CAPACITY = 11;
//最大容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//内部堆数组，存放实际数据，可以看成二叉树
//顶点 queue[i] 左子节点 queue[2*i+1],右子节点queue[2*(i+1)]，父节点queue[(i-1)/2]
private transient Object[] queue;
//当前队列中元素个数
private transient int size;
//比较器，为空时根据元素实现的Comparable接口的逻辑进行比较
private transient Comparator<? super E> comparator;
//全局锁
private final ReentrantLock lock;
//非空阻塞条件
private final Condition notEmpty; 
//扩容数组分配资源时的自旋锁
private transient volatile int allocationSpinLock;
//?
private PriorityQueue q;

从属性可以看出，优先级队列PriorityBlockingQueue底层也是以数组的方式实现，与ArrayBlockingQueue一样，只有一把锁。

2.初始化

接着看构造方法：

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

3.入队

入列方法有offer()，和put()。

先看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)
            //比较器为空，以元素实现的Comparable接口进行堆调整
            siftUpComparable(n, e, array);
        else
            //比较器非空, 则按照比较器进行堆调整
            siftUpUsingComparator(n, e, array, cmp);
        //当前长度+1
        size = n + 1;
        //唤醒等待在notEmpty上的出队线程
        notEmpty.signal();
    } finally {
        lock.unlock();
    }
    return true;
}

这里需要注意的队列的扩容方法tryGrow(Object[] array, int oldCap)，该方法会首先释放全局锁，通过简单的自旋锁实现扩容时不影响容器其他并发操作的方式。

private void tryGrow(Object[] array, int oldCap) {
    //先释放锁，原因是PriorityBlockingQueue主要通过CAS设置allocationSpinLock来判断哪个线程获得了扩容权限，如果没抢到权限就会让出CPU使用权
    //通过CAS来控制扩容安全性，可以保证扩容和入队/出队同时进行, 所以先释放全局锁
    lock.unlock(); // must release and then re-acquire main lock
    Object[] newArray = null;
    if (allocationSpinLock == 0 && UNSAFE.compareAndSwapInt(this, allocationSpinLockOffset,0, 1)) {
        try {
            // 计算新的数组大小，当前长度小于64时，长度扩大到原来的2倍+2，否则扩大到原来的1.5倍
            int newCap = oldCap + ((oldCap < 64) ?(oldCap + 2) : (oldCap >> 1));
            //溢出判断
            if (newCap - MAX_ARRAY_SIZE > 0) {
                int minCap = oldCap + 1;
                if (minCap < 0 || minCap > MAX_ARRAY_SIZE)
                    throw new OutOfMemoryError();
                newCap = MAX_ARRAY_SIZE;
            }
            //queue == array主要是判断当前的数组是否已经发生改变
            if (newCap > oldCap && queue == array)
                newArray = new Object[newCap];
        } finally {
            allocationSpinLock = 0;
        }
    }
    if (newArray == null)
        //让出 CPU 调度(因为其他线程扩容后必定有其他的操作)
        Thread.yield();
    lock.lock();
    //再次判断数组是否发生变化
    if (newArray != null && queue == array) {
        //进行数据拷贝
        queue = newArray;
        System.arraycopy(array, 0, newArray, 0, oldCap);
    }
}

接着看堆调整siftUpComparable和siftUpUsingComparator方法，这两个方法内部几乎一样，这里以siftUpComparable为例，如果有细看上面链接的关于二叉堆文章，下面的源码应该不难理解，主要思路是将当前元素与父节点[(n-1)/2]比较，直到k>=parent(或k<=parent，这里根据实现的Comparable接口的逻辑来定)。

private static <T> void siftUpComparable(int k, T x, Object[] array) {
    Comparable<? super T> key = (Comparable<? super T>) x;
    while (k > 0) {
        // 相当于(k-1)/2, 即k结点的父结点索引parent
        int parent = (k - 1) >>> 1;
        Object e = array[parent];//parent的真实值
        if (key.compareTo((T) e) >= 0)//当前元素与parent进行比较
            break;
        array[k] = e;//将k索引位置的数据设置成parent的值
        k = parent; //将本次parent的索引作为下个循环比较的索引
    }
    array[k] = key;
}

再看offer()的重载方法offer(E e, long timeout, TimeUnit unit)和put()方法，其实调用的是offer()方法，由于队列是无界的，所以不会阻塞线程.

public boolean offer(E e, long timeout, TimeUnit unit) {
    return offer(e); // never need to block
}
public void put(E e) {
    offer(e); // never need to block
}

4.出队

出队同样有poll()和take()等方法，逻辑基本一致，所以这里以take()进行分析，从源码可以看到take()方法调用的dequeue()方法。

public E take() throws InterruptedException {
    //获取全局锁，并且设置可中断
    final ReentrantLock lock = this.lock;
    lock.lockInterruptibly();
    E result;
    try {
        //队列为空时等待
        while ( (result = dequeue()) == null)
            notEmpty.await();
    } finally {
        lock.unlock();
    }
    return result;
}

dequeue()方法：

private E dequeue() {
    //长度减1，如果队列为空，返回null
    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;
    }
}

接着看堆调整siftDownComparable和siftDownUsingComparator方法，这两个方法内部几乎一样，这里分析siftDownComparable源码。逻辑与上面链接上的删除操作基本一致。自己走一遍就能理解了。

private static <T> void siftDownComparable(int k, T x, Object[] array,int n) {
    if (n > 0) {
        Comparable<? super T> key = (Comparable<? super T>)x;      
        int half = n >>> 1; //获取x的parent的父节点索引位置
        while (k < half) {
            int child = (k << 1) + 1; //获取k索引的左子节点索引
            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)  //当前节点比子节点小或等于时，满足条件，结束循环。
                break;
            array[k] = c;   //将k索引设置为最小值的子节点
            k = child; //该子节点的索引作为下个循环的父节点
        }
        array[k] = key;
    }
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 204,189评论 6赞 478
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 85,577评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 150,857评论 0赞 337
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,703评论 1赞 276
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,705评论 5赞 366
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,620评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,995评论 3赞 396
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,656评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,898评论 1赞 298
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,639评论 2赞 321
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,720评论 1赞 330
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,395评论 4赞 319
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,982评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,953评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,195评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 44,907评论 2赞 349
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,472评论 2赞 342