这是一个创建于 1572 天前的主题，其中的信息可能已经有所发展或是发生改变。
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 ，应该不是版本问题。
求大佬们不吝赐教
 |
1
mind3x 2020-08-04 04:11:07 +08:00  1
哇，非常好的问题。先尝试回答第 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 的类型约束都是靠运行时强制转型的动态检查，没法静态声明。 |
 |
2
amiwrong123 OP @mind3x
谢谢回复 原来如此，大概就是： Integer[] array = new Integer[5]; Comparable<?> aa = (Comparable<?>)(new Integer(1)); array[4] = aa;//编译报错 我也很好奇为什么不把 array[k]=key 改成 array[k] = x，这样构造器里面就不用转换数组类型了嘛 PriorityBlockingQueue<E>的声明，你不提醒我，我都没注意到这一点。 |
|
3
amiwrong123 OP @mind3x
大佬，还想问个问题： 就是你 1 楼给的泛型函数里， 为什么一定要声明 Comparable<? super T> key = (Comparable<? super T>) x; 我觉得声明成 Comparable<T> key = (Comparable<T>) x;就完全可以了啊，完全不理解为啥这样。 因为 key.compareTo((T) e)比较时，也是和确定的 T 类型进行比较的啊。 |
|
4
mind3x 2020-08-04 22:11:56 +08:00
@amiwrong123
这里我怀疑原因是这样：这个 contravariant 类型 <? super T> 对于使用 Comparator 的情形是有意义的，例如有 type B, D 并且 D extends B，PriorityBlockingQueue<D>可以使用 Comparator<D>，但是也可以使用 Comparator<B>，因此一般这种情况会允许 Comparator<? super T>。 但 Comparable 是 obj.comparesTo(other)，这里用 contravariant 类型没有意义，因为类型擦除，运行时毫无区别，大概只是实习生照着 Comparator 分支抄过来的…… |
Select Language