PriorityBlockingQueue 的构造器好奇怪啊？

    public PriorityBlockingQueue(Collection<? extends E> c) {
        this.lock = new ReentrantLock();
        this.notEmpty = lock.newCondition();
        boolean heapify = true; // true if not known to be in heap order
        boolean screen = true;  // true if must screen for nulls
        if (c instanceof SortedSet<?>) {
            SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
            this.comparator = (Comparator<? super E>) ss.comparator();
            heapify = false;
        }
        else if (c instanceof PriorityBlockingQueue<?>) {
            PriorityBlockingQueue<? extends E> pq =
                (PriorityBlockingQueue<? extends E>) c;
            this.comparator = (Comparator<? super E>) pq.comparator();
            screen = false;
            if (pq.getClass() == PriorityBlockingQueue.class) // exact match  第一处
                heapify = false;
        }
        Object[] a = c.toArray();
        int n = a.length;
        // If c.toArray incorrectly doesn't return Object[], copy it.
        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)
                    throw new NullPointerException();
        }
        this.queue = a;
        this.size = n;
        if (heapify)
            heapify();
    }

为什么一定要if (pq.getClass() == PriorityBlockingQueue.class)才不用重新建堆（ heapify 为 false，就不用重新建堆），大概意思就是 PriorityBlockingQueue 的子类可能重写了方法，所以可能 PriorityBlockingQueue 的子类的内部数组根本不是堆吗？
为什么当if (a.getClass() != Object[].class)时，就一定要新建一个类型为Object[].class的数组，即使两个数组里面的元素都是一样的。而且意思 c.toArray()返回的实际类型不一定是Object[].class了呗
if (screen && (n == 1 || this.comparator != null))时重新检查有没有 null 元素，但是后面的(n == 1 || this.comparator != null)不是很理解为什么这么判断？

看最近的 jdk 的源码也是这样，http://hg.openjdk.java.net/jdk/jdk15/file/d2c6eb3b2c8d/src/java.base/share/classes/java/util/concurrent/PriorityBlockingQueue.java#l242 ，应该不是版本问题。

求大佬们不吝赐教

mind3x

2020-08-04 04:11:07 +08:00

哇，非常好的问题。先尝试回答第 2 个:

PriorityBlockingQueue<E>的类型参数 E 本身没有类型约束(例如 E extends Comparable<E>)，因此在 PriorityBlockingQueue 的实现内部，要插入或删除一个 E 类型的元素时，是通过先把元素强转成接口类型 Comparable<? super E>，再进行比较，再赋值给对应的位置 queue[???]。例如

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)
break;
array[k] = e;
k = parent;
}
array[k] = key;
}

这里的问题是，如果 queue 不是在构造函数里初始化成 Object[]类型，而是 E[]类型，上面的 array[k] = key 将会导致 ArrayStoreException 。例如，如果 E 是 Integer，cast 成 Comparable 没问题，但 Comparable 不是 Integer，没法存回 Integer[]。所以 queue 需要初始化成什么都能存的 Object[]。

但其实还有更简单的办法——把 array[k]=key 改成 array[k] = x，queue 就可以安安全全的使用 E[] type，也不需要那么多强制转型。至于为什么 Java 没这么做，就不是我能回答的了。

至于 PriorityBlockingQueue<E>为什么不直接声明成 PriorityBlockingQueue<E extends Comparable<E>>，是因为 PriorityBlockingQueue 同时支持 Comparable 和 Comparator 两种比较接口，插入删除都是两种版本，E 的类型约束都是靠运行时强制转型的动态检查，没法静态声明。