Java PriorityQueue initElementsFromCollection 方法

Question

我很难从 java.util.PriorityQueue#initElementsFromCollection 方法中消化这个特定的代码块。

/**
 * Initializes queue array with elements from the given Collection.
 *
 * @param c the collection
 */
private void initFromCollection(Collection<? extends E> c) {
    initElementsFromCollection(c);
    heapify();
}

private void initElementsFromCollection(Collection<? extends E> c) {
    Object[] es = c.toArray();
    int len = es.length;
    if (c.getClass() != ArrayList.class)
        es = Arrays.copyOf(es, len, Object[].class);
    if (len == 1 || this.comparator != null)
        for (Object e : es)
            if (e == null)
                throw new NullPointerException();
    this.queue = ensureNonEmpty(es);
    this.size = len;
}

我可以理解这里的代码试图从构造函数提供的集合元素构建堆，但为什么他们要检查 Collection 参数的 class 类型与 ArrayList 和再次复制元素，它已经被复制到 Object[] es 使用 toArray?

    if (c.getClass() != ArrayList.class)
        es = Arrays.copyOf(es, len, Object[].class);

java.util.Arrays#copyOf(U[], int, java.lang.Class<? extends T[]>) 有什么神奇的事情发生吗？

java-11

Answer 1

构造函数（或者说它的作者）不信任传入的集合。该集合的 toArray 方法可能会违反约定，并且 return 共享数组而不是创建一个新数组。这样，调用者就可以得到构造的 PriorityQueue 实例的内部使用数组。

因此，构造函数制作了另一个防御性副本，除非传入集合恰好是 ArrayList，即甚至不是它的子类。换句话说，它相信 ArrayList 的 toArray 实现遵守合约，在这种特定情况下跳过额外的复制步骤。这就是为什么甚至不接受 ArrayList 的子类，因为子类可能已经覆盖了 toArray 方法。

Stream.toList() 的默认实现中显示了类似的不信任，如 and the comment section beneath 中所述。

默认实现已指定为

default List<T> toList() {
    return (List<T>) Collections.unmodifiableList(new ArrayList<>(Arrays.asList(this.toArray())));
}

因为它不信任第 3 方 Stream 实现的 toArray() 实现（无论如何 JDK 实现都会覆盖 toList() 方法）。

这种妄想症的惩罚甚至还付了两次。过去，ArrayList 的构造函数确实信任任何传入集合的 toArray() 实现，但今天，它看起来像

public ArrayList(Collection<? extends E> c) {
    Object[] a = c.toArray();
    if ((size = a.length) != 0) {
        if (c.getClass() == ArrayList.class) {
            elementData = a;
        } else {
            elementData = Arrays.copyOf(a, size, Object[].class);
        }
    } else {
        // replace with empty array.
        elementData = EMPTY_ELEMENTDATA;
    }
}

与您在 PriorityQueue 的构造函数中看到的完全相同，只有当集合恰好是 ArrayList.

时才相信 toArray()

由于在 toList() 的情况下，传入集合是 Arrays.asList(…) 的结果，即不是 ArrayList，toArray() 方法将进行复制，然后是 ArrayList 的构造函数制作另一个副本。所有这一切，虽然原始数组无论如何都是一个新数组，但为了表现良好 Stream 实现…

我们可以概括这个问题。集合的惯用初始化，如 new ArrayList<>(Arrays.asList(…)) 或 new ArrayList<>(List.of(…)) 或 PriorityQueue，尽管只使用 JDK 集合应该有正确的 toArray实施。

我可能会使用 c.getClass().getClassLoader() != null 而不是 c.getClass() != ArrayList.class，以信任所有 built-in 集合，其实现已由 bootstrap 加载程序加载。但也许，该测试结果会比 ArrayList 测试 1 更昂贵，或者有太多不可信的 built-in 集合……

¹ 关键在于优化器是否充分理解构造以预测其结果。

Java PriorityQueue initElementsFromCollection 方法

Java PriorityQueue initElementsFromCollection method

java

heap

collections

priority-queue