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

我可以理解，这里的代码尝试从通过构造函数提供的集合元素构建堆，但为什么他们要针对 ArrayList 检查 Collection 参数的类类型，并再次复制元素，它已经使用 toArray 复制到 Object[] es<​​/code> 中吗？

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

java.util.Arrays#copyOf(U[], int, java.lang.Class) 中发生了什么神奇的事情吗？

java-11

Answer 1

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

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

正如这个问题Stream.toList()的默认实现中也显示出类似的不信任。 a> 以及该问题下面的评论部分。

已指定默认实现，

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，尽管仅使用应该具有正确的toArray实现的JDK集合，但仍会受到防御性副本的惩罚。

我可能会使用 c.getClass().getClassLoader() != null 而不是 c.getClass() != ArrayList.class 来信任所有内置的集合，其实现已由引导加载程序加载。但也许，该测试会比 ArrayList 测试更昂贵，或者有太多不值得信赖的内置集合……

关键点是优化器是否足够好地理解该构造以预测其结果结果。