JDK8 PriorityBlockingQueue(Collection＜? extends E＞ c)构造器源码解析

痛定思痛。 2023-03-06 05:52 4阅读 0赞

### 文章目录 ###

*  前言
 *  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`的重点理解内容，所以本文单独讲解。

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

1.  `if (pq.getClass() == PriorityBlockingQueue.class)`，为什么一定要类型就是PriorityBlockingQueue本身时，才可以置heapify为false？
2.  `if (a.getClass() != Object[].class)`，为什么如果数组类型不是`Object[].class`就一定要将其复制一个新数组出来，即使两个数组每个元素都是一样的？
3.  `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\[\]][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`有三种情况：

1.  `c`是一个支持比较的集合，比较方式是`Comparable`，所以它的`Comparator`成员为null。
2.  `c`是一个支持比较的集合，比较方式是`Comparator`，所以它的`Comparator`成员不为null。
3.  `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元素反而也不会抛出空指针异常。具体可见这个bug[Adding 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() ##

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`。

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元素。

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`的正确实现。

[Collection.toArray_ spec should be explicit about returning precisely an Object]: https://bugs.openjdk.java.net/browse/JDK-8160406
[Adding null key to empty TreeMap without Comparator should throw NPE]: https://bugs.openjdk.java.net/browse/JDK-5045147