文章目录
- 前言
- if (pq.getClass() == PriorityBlockingQueue.class)
- if (a.getClass() != Object[].class)
- if (screen && (n == 1 || this.comparator != null))
- heapify()
- PriorityBlockingQueue的BUG？！
- 总结
前言
PriorityBlockingQueue的这个(Collection<? extends E> c)重载版本构造器的源码有几个地方有点难懂，但本文讲述内容不是PriorityBlockingQueue的重点理解内容，所以本文单独讲解。
java"> public PriorityBlockingQueue(Collection<? extends E> c) {
this.lock = new ReentrantLock();
this.notEmpty = lock.newCondition();
boolean heapify = true; // 为true代表数组需要重新建堆
boolean screen = true; // 为true代表需要扫描一遍数组，看里面有没有null元素（此类不支持null元素）
if (c instanceof SortedSet<?>) {
SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
this.comparator = (Comparator<? super E>) ss.comparator();
heapify = false;//SortedSet的内部数据已经按照升序排序好了，自然也是堆结构的
}
else if (c instanceof PriorityBlockingQueue<?>) {
PriorityBlockingQueue<? extends E> pq =
(PriorityBlockingQueue<? extends E>) c;
this.comparator = (Comparator<? super E>) pq.comparator();
screen = false;//PriorityBlockingQueue不可能包含null元素
if (pq.getClass() == PriorityBlockingQueue.class) // 第一处
heapify = false;
}
Object[] a = c.toArray();
int n = a.length;
if (a.getClass() != Object[].class) // 第二处
a = Arrays.copyOf(a, n, Object[].class);
if (screen && (n == 1 || this.comparator != null)) {// 第三处
for (int i = 0; i < n; ++i)
if (a[i] == null)//检查到有null元素，直接抛出异常
throw new NullPointerException();
}
this.queue = a;
this.size = n;
if (heapify)//建堆
heapify();
}
if (pq.getClass() == PriorityBlockingQueue.class)，为什么一定要类型就是PriorityBlockingQueue本身时，才可以置heapify为false？if (a.getClass() != Object[].class)，为什么如果数组类型不是Object[].class就一定要将其复制一个新数组出来，即使两个数组每个元素都是一样的？if (screen && (n == 1 || this.comparator != null))，为什么后面的条件写成(n == 1 || this.comparator != null)？
if (pq.getClass() == PriorityBlockingQueue.class)
因为c instanceof PriorityBlockingQueue<?>只能证明c是PriorityBlockingQueue的子类，但只有c的实际类型就是PriorityBlockingQueue本身时，才能说明c的内部数组逻辑上已经是堆的结构了。毕竟PriorityBlockingQueue的子类的实现是不确定的。
另外，本人觉得，screen = false这句也应该放到if (pq.getClass() == PriorityBlockingQueue.class)的判断里，也许这是假设PriorityBlockingQueue的子类没有去重写offer（此函数判断了null元素）之类的方法。即使PriorityBlockingQueue的子类重写了offer从而使得内部数组持有null元素，最后heapify()也会发现任何的null元素并抛出异常（之后再讲）。
if (a.getClass() != Object[].class)
Collection.toArray() spec should be explicit about returning precisely an Object[]
从上面的bug介绍可知，Collection.toArray()返回的数组的实际类型要求是Object[]，但由于数组的协变，实际类型有可能是别的。
所以，当我们发现这种情况，新建一个Object[].class的数组，把所有元素浅拷贝一遍。
if (screen && (n == 1 || this.comparator != null))
screen为true代表需要扫描一遍数组里的null元素。问题在于后面&& (n == 1 || this.comparator != null)为什么这么写。
传入参数c有三种情况：
c是一个支持比较的集合，比较方式是Comparable，所以它的Comparator成员为null。c是一个支持比较的集合，比较方式是Comparator，所以它的Comparator成员不为null。c是一个不支持比较的集合，它根本就没有就没有Comparator成员。
Note that null is not an instance of any class, and e.compareTo(null) should throw a NullPointerException even though e.equals(null) returns false.
如果n == 1成立，说明元素只有一个。即使比较方式是Comparable，由于只有一个元素，比较行为可能不会发生，所以刚开始加入null元素反而也不会抛出空指针异常。具体可见这个bugAdding null key to empty TreeMap without Comparator should throw NPE。所以如果发现元素个数为1，就直接扫描。
Unlike Comparable, a comparator may optionally permit comparison of null arguments, while maintaining the requirements for an equivalence relation.
如果this.comparator != null)成立，说明c肯定是一个支持比较的集合，由于Comparator的实现是允许比较null的，所以Comparator成员不为null，则可能c的内部数组包含null。所以也需要扫描。
你可能会说，大部分情况是，size大于1，而且this.comparator为null的情况，这样就不会去做扫描了，这样难道不会有问题吗？
不会。因为heapify()会把所有元素顺便检查一遍。
heapify()
java"> private void heapify() {
Object[] array = queue;
int n = size;
int half = (n >>> 1) - 1;//最后一个非叶子节点的索引
Comparator<? super E> cmp = comparator;
if (cmp == null) {
for (int i = half; i >= 0; i--)
siftDownComparable(i, (E) array[i], array, n);
}
else {
for (int i = half; i >= 0; i--)
siftDownUsingComparator(i, (E) array[i], array, n, cmp);
}
}
heapify()函数从最后一个非叶子节点的索引 往 0 遍历，每个索引执行一遍下沉函数，根据上面this.comparator为null的假设，调用的下沉函数是siftDownComparable。
java"> 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; // 这是第一个叶子节点的索引，也就是说当k到达一个叶子节点时，它就不能再下沉了
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)
break;
array[k] = c;
k = child;
}
array[k] = key;
}
}
siftDownComparable函数执行下沉逻辑，while (k < half)说明当k到达一个叶子节点时，它就不能再下沉了。但k到达一个叶子节点的上一次循环时，k肯定是停留在了一个非叶子节点，而且这次循环中会负责检查两个孩子是否为null元素（左孩子一定存在，右孩子如果存在right < n才去检查）。
Note that null is not an instance of any class, and e.compareTo(null) should throw a NullPointerException even though e.equals(null) returns false.
根据compareTo的介绍，(Comparable<? super T>) c).compareTo((T) array[right])负责检查右孩子，同时，如果局部变量c为null的话，也会抛出异常，所以这句也会检查到左孩子。
如果右孩子不存在，(Comparable<? super T>) c).compareTo((T) array[right])将不会执行了，但没关系。key.compareTo((T) c)负责检查左孩子。
综上，heapify()会遍历每一个非叶子节点执行下沉函数，siftDownComparable下沉函数在最后一次循环会负责检查两个叶子节点，所以最终每个元素都会被检查到是否为null。
PriorityBlockingQueue的BUG？！
siftDownComparable下沉函数虽然在最后一次循环会负责检查两个叶子节点，但这是依靠于Comparable接口的正确实现。一旦Comparable接口实现允许比较null而不抛出异常，那么PriorityBlockingQueue的内部数组将会包含null元素。
java">import java.util.ArrayList;
import java.util.Queue;
import java.util.concurrent.PriorityBlockingQueue;
public class test16 {
static class Holder implements Comparable<Holder> {
int i;
Holder(int i) {
this.i = i;
}
public int compareTo(Holder h) {
if(h == null)//注意，正确做法是抛出异常
return -1;
return this.i - h.i;//去掉上面两句，也会抛出异常
}
}
public static void main(String[] args) {
ArrayList<Holder> al = new ArrayList<>();
al.add(new Holder(1));
al.add(new Holder(2));
al.add(null);
Queue a = new PriorityBlockingQueue<>(al);
}
}
测试用例如上，执行完毕后，并没有抛出异常，而PriorityBlockingQueue包含了一个null元素。
我已经给JDK提了bug，但维护人员不一定会认为这是个bug（因为Comparable的实现不符合文档），如果被认定了，我再来贴bug链接。
总结
不管screen扫描null元素有没有执行，最终的heapify()其实也顺便检查每个元素是否为null了。检查叶子节点是否null，则依靠于Comparable的正确实现。
