java - 为什么toArray在java中是这样实现的？

Question

如我所见:java.util.AbstractCollection.toArray()的源码，是这样实现的:

 public Object[] toArray() {
    // Estimate size of array; be prepared to see more or fewer elements
    Object[] r = new Object[size()];
    Iterator<E> it = iterator();
    for (int i = 0; i < r.length; i++) {
        if (! it.hasNext()) // fewer elements than expected
            return Arrays.copyOf(r, i);
        r[i] = it.next();
    }
    return it.hasNext() ? finishToArray(r, it) : r;
}

private static <T> T[] finishToArray(T[] r, Iterator<?> it) {
    int i = r.length;
    while (it.hasNext()) {
        int cap = r.length;
        if (i == cap) {
            int newCap = cap + (cap >> 1) + 1;
            // overflow-conscious code
            if (newCap - MAX_ARRAY_SIZE > 0)
                newCap = hugeCapacity(cap + 1);
            r = Arrays.copyOf(r, newCap);
        }
        r[i++] = (T)it.next();
    }
    // trim if overallocated
    return (i == r.length) ? r : Arrays.copyOf(r, i);
}

如您所见，实现并不那么容易理解，我的问题是:

1. 当集合的元素在迭代过程中发生变化(大小不变)时，我会得到什么？我猜迭代器可能是某种快照。
   
2. 当集合的大小改变时我会得到什么？我想知道它是否可以正常工作。

Answer 1

As you see,the implementation is not so easy to understand, my question is :

1. What will I get when the collection's elements change (size not changed) during iteration? I guess the iterator may be some kind of snapshot.
2. What will I get when the collection's size is changed? I wonder if it can work correctly.

实现之所以如此，是因为它旨在处理迭代器返回的元素数量与 size() 不同的情况。如果集合的大小在迭代过程中发生变化，就会发生这种情况。目标数组是根据 size() 分配的，在大小不变的乐观情况下，它非常简单。代码的复杂性在于迭代器返回的实际元素数与 size() 返回的初始值不同。如果元素的实际数量较少，则将元素复制到大小合适的较小数组中。如果实际数字更大，则将元素复制到更大的数组中，然后迭代更多元素。如果数组已满，则会反复重新分配更大的数组，直到迭代完成。

对于您的第一个问题，迭代器不一定对元素进行快照。这取决于实际的集合实现。某些集合(例如 CopyOnWriteArrayList)确实具有快照语义，因此如果集合被修改，修改将对迭代器不可见。在这种情况下，迭代器报告的元素数量将匹配 size()，因此不需要重新分配数组。

其他集合实现对于在迭代期间修改集合时会发生什么有不同的策略。有些是快速失败，这意味着它们会抛出 ConcurrentModificationException。其他的是弱一致性，这意味着迭代器可能会或可能不会看到修改。

这适用于您的第二个问题。如果集合大小在迭代过程中发生变化，并且该集合的迭代器支持这一点(即，它不是快速失败的)，则此处的代码将处理迭代器中出现的元素数量与 size( )。

ConcurrentSkipListSet 可能会发生这种情况。该类的迭代器是弱一致性的，它继承了AbstractCollection的toArray()方法。因此，当 toArray() 迭代集合以将元素收集到目标数组中时，另一个线程修改集合(可能更改其大小)是完全合法的。这显然会导致迭代器报告与 size() 返回的初始值不同的元素数，这将导致 toArray() 中的数组重新分配代码是执行。