Почему 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

Как видите, реализация не так проста для понимания, мой вопрос:

1. Что я получу, когда элементы коллекции изменятся (размер не изменится) во время итерации? Я думаю, что итератор может быть своего рода снимком.
2. Что я получу, когда размер коллекции изменится? Интересно, может ли это работать правильно.

Реализация такова, как она есть, потому что она предназначена для обработки случая, когда итератор возвращает другое количество элементов, чем size(), Это может произойти, если размер коллекции изменяется во время итерации. Массив назначения распределяется на основе size()и в оптимистическом случае, когда размер не меняется, это довольно просто. Сложность кода заключается в том, что фактическое количество элементов, возвращаемых итератором, отличается от исходного значения, возвращаемого size(), Если фактическое количество элементов меньше, элементы копируются в меньший массив правильного размера. Если фактическое число больше, элементы копируются в больший массив, а затем выполняется повторение большего количества элементов. Массив многократно перераспределяется больше, если он заполняется, пока итерация не завершится.

На ваш первый вопрос, итератор не обязательно делает снимок элементов. Это зависит от фактической реализации коллекции. Некоторые коллекции (такие как CopyOnWriteArrayList) имеют семантику моментальных снимков, поэтому, если коллекция будет изменена, модификация не будет видна итератору. В этом случае число элементов, сообщаемых итератором, будет совпадать size(), поэтому перераспределение массива не требуется.

Другие реализации коллекций имеют разные политики для того, что происходит, если коллекция изменяется во время итерации. Некоторые отказоустойчивы, что означает, что они бросят ConcurrentModificationException, Другие слабо согласованы, что означает, что изменения могут быть или не быть видимыми для итератора.

Это относится к вашему второму вопросу. Если размер коллекций изменяется во время итерации, и если итератор этой коллекции поддерживает это (т. Е. Он не является отказоустойчивым), то здесь код будет обрабатывать другое количество элементов, выходящих из итератора, чем первоначально сообщалось size(),

Пример, где это может произойти, с ConcurrentSkipListSet, Итератор этого класса слабо согласован, и он наследует toArray() метод из AbstractCollection, Таким образом, в то время как toArray() выполняет итерацию набора для того, чтобы собрать элементы в целевой массив, для другого потока вполне законно изменить набор, возможно, изменив его размер. Это может привести к тому, что итератор сообщит о количестве элементов, отличном от исходного значения, возвращаемого size(), который вызовет код перераспределения массива в toArray() быть выполненным.

Answer 2

Вы можете быть только уверены, что результат итерации не определен (если только вы не знаете точную реализацию используемой коллекции). Обычно ConcurrentModificationException будет брошен, но вы не можете полагаться на это предположение.

Если Collection модифицируется во время итерации, в большинстве реализаций ConcurrentModificationException брошен Iterators это называется быстродействующими итераторами.

Но это зависит от каждой реализации, хотя все реализации общего назначения, предоставленные JRE, делают это, но не все Iterators быстро проваливаются. Кроме того, обратите внимание, что отказоустойчивое поведение не может быть гарантировано, так как, вообще говоря, невозможно сделать какие-либо жесткие гарантии при наличии несинхронизированной параллельной модификации.

Почему toArray реализован так в Java?

Поскольку эта реализация предполагает, что размер коллекции может измениться в любое время, поскольку итератор не может выдавать никаких исключений. Следовательно, этот метод проверяет, что итератор может предоставить больше или меньше элементов, чем первоначальный оценочный размер.

Answer 3

Что я получу, когда размер коллекции изменился?

• Если размер коллекции меньше ожидаемого, массив "уменьшается" return Arrays.copyOf(r, i) в toArray() метод, как в комментарии, указывает.
• Если размер коллекции больше, чем ожидалось, it.hasNext() ? finishToArray(r, it) : r вызов обрабатывает дело. finishToArray метод продолжает добавлять элементы в массив и "расширять" его размер при необходимости: вычисляется новая емкость (newCap = cap + (cap >> 1) + 1) и массив "расширен" (r = Arrays.copyOf(r, newCap)).

Answer 4

Я не думаю, что все реализации Collection являются поточно-ориентированными, вместо того, чтобы беспокоиться, вы можете синхронизировать свою Collection с помощью:

Collections.synchronizedCollection(myCollection);

или вы можете посмотреть:

https://docs.oracle.com/javase/tutorial/essential/concurrency/collections.html

Изменить: здесь я нашел хорошее объяснение