Избавляемся от ConcurrentModificationException

Как известно, ConcurrentModificationException к многопоточности никакого отношения не имеет. Возникает эта гадость, когда мы пытаемся модифицировать коллекцию во время итерирования по ней. Как обычно, это имеет исторические корни: коллекции и итераторы появились в Java 1.2, в те времена избежать явного использования итератора при обходе коллекции было никак нельзя, так что предложение менять коллекцию посредством методов итератора не выглядело совсем ужасным:

Iterator iterator = collection.iterator();

while (iterator.hasNext()) {
    Object element = iterator.next();
    if (iDontLikeThisElement(element)) {
         iterator.remove();
    }
}

Не, всё же выглядело. Но никаких других вариантов не было. Позже в пятой джаве появляется цикл foreach, и использование итераторов становится преимущественно неявным:

for (E element : collection) {
   if (iDonLikeThisElement(element)) {
       collection.remove(element); // облом! ConcurrentModificationException! 
   }
}

«Ишь чего захотели! Юзайте явные итераторы, дорогие кастомеры, и не выделывайтесь» — наверное что-то такое думали разработчики джава платформы работая над пятеркой.

В шестой джаве появляется пакет конкаренси. Теперь можно cделать так:

Set<String> set = Collections.newSetFromMap(new ConcurrentHashMap<>());

и получить set который не кидается ConcurrentModificationException-ами. Но опять же счастье не совсем полное:

1. Oбычно многопоточность нам вовсе не нужна
2. Не подерживаются null ни в качестве элементов, ни ключей, ни значений. Да и ладно, честно сказать.
3. Порядок элементов не определён и может меняться — вот это гораздо хуже. Т.е. если мы бежим по элементам и ведём некий подсчёт с потерей точности, то нас могут поджидать неприятные сюрпризы и разные результаты на одних и тех же наборах данных, что, скажем, не всегда хорошо. Так же бывают задачи, где желательно сохранить именно изначальный порядок данных. Ну и вот такие штуки тоже имеют место быть:

set.add("aaa");
set.add("bbb");
        
for (String s : set) {
    set.add("ddd");
    System.out.println(s);
}

set.add("aaa");
set.add("bbb");
        
for (String s : set) {
    set.add("ccc");
    System.out.println(s);
}

Поэтому сейчас мы сделаем свою собственную коллекцию с чётким порядком. И так, что мы хотим получить:

1. В рамках одного треда можно добавлять и удалять элементы в любой момент без всяких эксепшенов. И конечно же за константное время.
2. Можно хранить null-ы, если вдруг хочется.
3. Элементы обходятся в том порядке в котором были добавлены.

Всё это с легкостью достигается с помощью слегка доработанного двунаправленного списка:

1. Удаляя элемент мы не будем обнулять ссылку на следующий, т. е. eсли итератор стоит на данном элементе, то он сможет пройти дальше.
2. В конце списка поместим фэйковый элемент, который превращается в настоящий когда в список что-нибудь добавляют. Т.е. даже добравшись до конца списка итератор не упирается в null и может продолжить работу если в коллекции появляется новый элемент. Далее в коде этот фейковый элемент называется placeholder.

Посмотрим на картинку.

1. В начале у нас есть элементы A, B, C, D.
2. Затем элементы C и D удаляются.
3. Добавляется новый элемент E.

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

Ну и для константного времени доступа нам, очевидно, нужен хэшмап:

import java.util.AbstractSet;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;

public class LinkedSet<E> extends AbstractSet<E> {
    
    private static class LinkedElement<E> {
        E value;
        
        boolean exists;
        
        LinkedElement<E> prev; 
        LinkedElement<E> next;
    }
    
    private Map<E, LinkedElement<E>> map = new HashMap<>();

    private LinkedElement<E> placeholder = new LinkedElement<>(); 
    private LinkedElement<E> head = placeholder;

    @Override
    public boolean isEmpty() { return head == placeholder; }

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

    @Override
    public boolean contains(Object o) { return map.containsKey(o); }

    // здесь будут методы для добавления, удаления, итерирования
}

Добавление элемента:

    @Override
    public boolean add(E e) {
        LinkedElement<E> element = map.putIfAbsent(e, placeholder);

        if (element != null) {
            return false;
        }
        
        element = placeholder;
        element.exists = true;
        element.value = e;

        placeholder = new LinkedElement<>();
        placeholder.prev = element;
        
        element.next = placeholder;
        
        return true;
    }

Удаление:

    @Override
    public boolean remove(Object o) {
        LinkedElement<E> removedElement = map.remove(o);
        
        if (removedElement == null) {
            return false;
        }
        
        removeElementFromLinkedList(removedElement);
        
        return true;
    }
    
    private void removeElementFromLinkedList(LinkedElement<E> element) {
        element.exists = false;
        element.value = null;

        element.next.prev = element.prev;
        
        if (element.prev != null) {
            element.prev.next = element.next;
            element.prev = null;
        } else {
            head = element.next;
        }
    }

Итератор:

    @Override
    public Iterator<E> iterator() {
        return new ElementIterator();
    }

    private class ElementIterator implements Iterator<E> {
        LinkedElement<E> next = head;
        LinkedElement<E> current = null;
        
        LinkedElement<E> findNext() {
            LinkedElement<E> n = next;
            
            while (!n.exists && n.next != null) {
                next = n = n.next;
            }
            
            return n;
        }
        
        @Override
        public boolean hasNext() {
            return findNext().exists;
        }

        @Override
        public E next() {
            LinkedElement<E> n = findNext();
            
            if (!n.exists) {
                throw new NoSuchElementException();
            }
            
            current = n;
            next = n.next;
            
            return n.value;
        }

        @Override
        public void remove() {
            if (current == null) {
                throw new IllegalStateException();
            }
            
            if (map.remove(current.value, current)) {
                removeElementFromLinkedList(current);
            } else {
                throw new NoSuchElementException();
            }
        }
    }

Теперь можно делать так:

Set<Integer> set = new LinkedSet<>();
// ... put some numbers
set.stream().filter(v -> v % 2 == 0).forEach(set::remove);

Понятно, что аналогично можно сконструировать и LinkedMap. Вот в общем-то и всё, ещё один велосипед готов. Почему подобным образом не доработали библиотечные LinkedHashMap и LinkedHashSet? Кто знает, возможно чтобы джависты завидовали джаваскриптистам.

Автор: yannmar

Источник ^[1]