Java PriorityQueue 实现：为什么 Object[] 队列而不是 E[] 队列？ siftUp/siftDownComparable 中 "key" 的用途是什么？

Question

我正在研究JDK implementation of PriorityQueue。

1) 整个队列存储在

 transient Object[] queue;

为什么不使用泛型 E 声明数组？（相反，class 中的对象有很多强制转换 E。）

2) siftUpComparable/siftDownComparable方法的第一行是

    Comparable<? super E> key = (Comparable<? super E>)x;

这是一个保护子句来验证x是可比较的吗？（否则，为什么不直接使用 x 呢？）

这是整个方法：

private void siftDownComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>)x;
    int half = size >>> 1;        // loop while a non-leaf
    while (k < half) {
        int child = (k << 1) + 1; // assume left child is least
        Object c = queue[child];
        int right = child + 1;
        if (right < size &&
            ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
            c = queue[child = right];
        if (key.compareTo((E) c) <= 0)
            break;
        queue[k] = c;
        k = child;
    }
    queue[k] = key;
}

Answer 1

1) 如果没有对对象的 Class 的引用，则不能实例化泛型类型的数组。有关示例，请参见下面的 JavaDevil 评论。但是，通过创建对象数组，不需要将 Class 的实例提供给 PriorityQueue。

E[] array = new E[10]; // won't compile

2) PriorityQueue 可以通过 Comparable 的对象 compareTo() 方法或对不一定是 Comparable 的对象使用 Comparator 对其元素进行排序。只有在创建 PriorityQueue 时未提供 Comparator 时，才会调用 siftDownComparable 方法。由于类型参数没有规定<E extends Comparable>，所以需要显式强制转换。这是 siftDown() 方法。

private void siftDown(int k, E x) {
    if (comparator != null)
        siftDownUsingComparator(k, x);
    else
        siftDownComparable(k, x);
}

Java PriorityQueue 实现：为什么 Object[] 队列而不是 E[] 队列？ siftUp/siftDownComparable 中 "key" 的用途是什么？

Java PriorityQueue implementation: Why Object[] queue instead of E[] queue? What's the purpose of "key" in siftUp/siftDownComparable?

java

heap

openjdk