Исключение создания TreeSet из одновременно модифицированного ConcurrentSkipListSet

Ответ 1

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

Вы можете обойти это, выполнив итерацию вручную и добавив элементы в TreeSet, но это приведет к сложности n log n, что может быть причиной того, что конструктор TreeSet не делает этого (его спецификация API гарантирует линейное время). Конечно, он все равно может вызвать hasNext(), поскольку он создает дерево, но затем после завершения строительства могут потребоваться дополнительные действия для ребалансировки дерева, что может привести к амортизации линейной сложности. Но красно-черные деревья - это беспорядок, какой они есть, и такой взлом сделает выполнение еще более грязным.

Тем не менее, я думаю, что это очень запутанно и, вероятно, должно быть документировано где-то в документах API, но я точно не знаю, где именно. Вероятно, в той части, где они объясняют, что такое слабые последовательные итераторы. В частности, следует отметить, что некоторые классы библиотек полагаются на возвращаемый размер и поэтому могут бросать NoSuchElementException. Упоминание конкретных классов также поможет.

Ответ 2

На самом деле я начинаю склоняться к тому, что это ошибка в TreeSet/TreeMap (обновление, оно). Проблема, как указывает Сергей, заключается в том, что TreeMap кэширует результат ConcurrentSkipListSet.size() перед чтением его элементов.

• TreeSet.addAll() вызывает
• TreeMap.addAllForTreeSet() и передает текущий текущий размер коллекции и потенциально параллельный Iterator на
• TreeMap.buildFromSorted(), который в итоге вызывает Iterator.next() size -times.

Иными словами, он предполагает, что переданный Collection не будет изменен во время построения, что является ошибочным предположением.

Обратите внимание, что даже если buildFromSorted() действительно вызывал Iterator.hasNext(), его единственным вариантом в этой точке было бы сбой, так как структура данных резервного копирования была модифицирована в середине построения.

Глядя на другие коллекции, которые потенциально могут иметь проблемы с копированием параллельных структур, включая ArrayList, LinkedList и CopyOnWriteArrayList (большинство других коллекций я просто посмотрел для каждого по элементам), явно скопируйте предоставленную коллекцию в массив, прежде чем выполнять какую-либо фактическую работу, чтобы избежать этой точной проблемы. Я думаю, что TreeSet и TreeMap должны делать то же самое.

На самом деле нам не нужно принимать O (n log n) производительность из-за этой ошибки, но это будет взлом. Мы не можем просто скопировать значения в массив или другую структуру данных, потому что тогда вставка в TreeSet не будет линейным временем. Но мы можем лгать TreeSet, утверждая, что копия является SortedSet.

public static class IterateOnlySortedSet<E>
    extends AbstractSet<E> implements SortedSet<E> {
  private final ArrayList<E> elements;
  private final Comparator<? super E> comparator;

  public IterateOnlySortedSet(SortedSet<E> source) {
    elements = new ArrayList<>(source);
    comparator = source.comparator();
  }

  @Override
  public Iterator<E> iterator() {
    return elements.iterator();
  }

  @Override
  public int size() {
    return elements.size();
  }

  @Override
  public Comparator<? super E> comparator() {
    return comparator;
  }

  // remaining methods simply throw UnsupportedOperationException
}

Изменение строительной линии TreeSet на:

TreeSet<Integer> sortedCopy = new TreeSet<>(new IterateOnlySortedSet<>(concurrentSet));

Теперь это удается.

Приятная находка:)