PriorityBlockingQueue原理探究

PriorityBlockingQueue是带优先级的无界阻塞队列，每次出队都返回优先级最高或者最低的元素。

其内部是使用平衡二叉树堆实现的，所以直接遍历队列元素不保证有序。

默认使用对象的compareTo方法提供比较规则，如果你需要自定义比较规则则可以自定义comparators。

类图结构

下面首先通过类图结构来从全局了解PriorityBlockingQueue的原理。

PriorityBlockingQueue内部有一个数组queue,用来存放队列元素，size用来存放队列元素个数。

allocationSpinLock是个自旋锁，其使用CAS操作来保证同时只有一个线程可以扩容队列，状态为0或者1,其中0表示当前没有进行扩容，1表示当前正在扩容。

由于这是一个优先级队列，所以有一个比较器comparator用来比较元素大小。

lock独占锁对象用来控制同时只能有一个线程可以进行入队、出队操作。

notEmpty条件变量用来实现take方法阻塞模式。

这里没有notFull条件变量是因为这里的put操作是非阻塞的，为啥要设计为非阻塞的，是因为这是无界队列。

在如下构造函数中，默认队列容量为11,默认比较器为null,也就是使用元素的compareTo方法进行比较来确定元素的优先级，这意味着队列元素必须实现了Comparable接口。

原理介绍

offer操作

offer操作的作用是在队列中插入一个元素，由于是无界队列，所以一直返回true。如下是offer函数的代码。

如上代码的主流程比较简单，下面主要看看如何进行扩容和在内部建堆。首先看下面的扩容逻辑。

这里为啥在扩容前要先释放锁，然后使用CAS控制只有一个线程可以扩容成功?其实这里不先释放锁，也是可行的，也就是在整个扩容期间一直持有锁，但是扩容是需要花时间的，如果扩容时还占用锁那么其他线程在这个时候是不能进行出队和入队操作的，这大大降低了并发性。

所以为了提高性能，使用CAS控制只有一个线程可以进行扩容，并且在扩容前释放锁，让其他线程可以进行入队和出队操作。

然后看下面的具体建堆算法。

poll操作

poll操作的作用是获取队列内部堆树的根节点元素，如果队列为空，则返回null。poll函数的代码如下。

在如上代码中，如果队列为空则直接返回null,否则执行代码(1)获取数组第一个元素作为返回值存放到变量Result中，这里需要注意，数组里面的第一个元素是优先级最小或者最大的元素，出队操作就是返回这个元素。

然后代码(2)获取队列尾部元素并存放到变量x中，且置空尾部节点，然后执行代码(3)将变量x插入到数组下标为0的位置，之后重新调整堆为最大或者最小堆，然后返回。

这里重要的是，去掉堆的根节点后，如何使用剩下的节点重新调整一个最大或者最小堆。下面我们看下siftDownComparable的实现代码。

put操作

put操作内部调用的是offer操作，由于是无界队列，所以不需要阻塞。

take操作

take操作的作用是获取队列内部堆树的根节点元素，如果队列为空则阻塞，如以下代码所示。

size操作

计算队列元素个数。如下代码在返回size前加了锁，以保证在调用size()方法时不会有其他线程进行入队和出队操作。

另外，由于size变量没有被修饰为volatie的，所以这里加锁也保证了在多线程下size变量的内存可见性。