ConcurrentModificationException при обновлении хранимого Iterator (для реализации кэша LRU)

Ответ 1

Сначала я рассмотрю проблему 3:

Как вы указываете в своем вопросе, LinkedList (как и все хорошо разработанные общие коллекции) скрывает детали реализации, такие как узлы, содержащие ссылки. В вашем случае вам нужна ваша хэш-карта, чтобы ссылаться на эти ссылки непосредственно как значения карты. В противном случае (например, с косвенным отношением через третий класс) можно было бы победить цель кеша LRU, чтобы позволить очень низкие накладные расходы на доступ к значениям. Но это невозможно в стандартных сборниках Java - они не обеспечивают (и не должны) обеспечить прямой доступ к внутренним структурам.

Итак, логичным завершением этого является то, что да, вам нужно реализовать свой собственный способ хранения порядка, в котором были использованы элементы в кеше. Это не обязательно должен быть двойной список. Те, которые традиционно использовались для кэшей LRU, потому что наиболее распространенной операцией является перемещение node в начало списка, когда к нему обращаются. Это невероятно дешевая операция в двусвязном списке, требующая только четырех узлов, которые могут быть перенаправлены без выделения памяти или бесплатно.

Задача 1 и 2:

По сути, основная причина здесь заключается в том, что вы пытаетесь использовать итераторы в качестве курсора. Они предназначены для создания, для выполнения определенной операции и последующей утилизации. Даже если вы справитесь с проблемами, которые у вас возникают, я ожидаю, что за ними последуют дополнительные проблемы. Вы помещаете квадратную привязку в круглое отверстие.

Итак, я пришел к выводу, что вам нужно реализовать свой собственный способ хранения значений в классе, который отслеживает порядок доступа. Однако это может быть невероятно просто: требуется только три операции: создать, получить значение и удалить из хвоста. Как создать, так и получить значение, нужно переместить node в начало списка. Вставка или удаление из середины списка. Не удалять голову. Нет поиска. Честно говоря, мертвый просто.

Надеюсь, вам это поможет: -)

public class <K,V> LRU_Map implements Map<K,V> {
    private class Node {
        private final V value;
        private Node previous = null;
        private Node next = null;

        public Node(V value) {
            this.value = value;
            touch();
            if (tail == null)
                tail = this;
        }

        public V getValue() {
            touch();
            return value;
        }

        private void touch() {
            if (head != this) {
                unlink();
                moveToHead();
            }
        }

        private void unlink() {
            if (tail == this)
                tail = prev;
            if (prev != null)
                prev.next = next;
            if (next != null)
                next.prev = prev;
        }

        private void moveToHead() {
            prev = null;
            next = head;
            head = this;
        }

        public void remove() {
            assert this == tail;
            assert this != head;
            assert next == null;
            if (prev != null)
                prev.next = null;
            tail = prev;
        }
    }

    private final Map<K,Node> map = new HashMap<>();
    private Node head = null;
    private Node tail = null;

    public void put(K key, V value) {
        if (map.size() >= MAX_SIZE) {
            assert tail != null;
            tail.remove();
        }
        map.put(key, new Node(value));
    }

    public V get(K key) {
        if (map.containsKey(key))
            return map.get(key).getValue();
        else
            return null;
    }

    // and so on for other Map methods
}

Ответ 2

1) На самом деле это не те итераторы.

По контракту, если вы изменяете список без использования итератора - как вы здесь делаете

_list.addFirst(value);

тогда ВСЕ ОТКРЫТЫЕ ИТЕРАТОРЫ в этом списке должны бросить ConcurrentModificationException. Они были открыты для версии списка, которая больше не существует.

2) LinkedList не является, точно, связанным списком узлов. Это java.util.List, чья поддержка является двусвязным списком узлов. Контракт этого списка - это то, почему он не предоставляет ссылки на реализацию резервного копирования, поэтому такие операции, как "удалить этот node, как node и переместить его в голову", не являются хорошими. Эта инкапсуляция предназначена для вашей собственной защиты (так же, как и для исключения одновременного мода) - это позволяет вашему коду полагаться на семантику списка LinkedList (например, итерабельность), не беспокоясь, что какой-то джокер два кубика провалился в его внутренностях и разорвал контракт.

3) Что вам действительно нужно, это НЕ LinkedList. Вам нужен стек, который позволяет вам перемещать любую произвольную запись в голову и выгружать хвост. Вы подразумеваете, что хотите быстро найти время для произвольной записи, а также быстро удалить и быстро добавить, И вы хотите, чтобы иметь возможность найти хвост в любой момент, если вам нужно удалить его.

Быстрое время поиска == HashSomething

Быстрое добавление/удаление произвольных элементов == LinkedSomething

Быстрая адресация конечного элемента == SomekindaList

4) Вам нужно будет создать собственную структуру ссылок... или использовать LinkedHashMap.

PS LinkedHashSet обманывает, он реализован с помощью LinkedHashMap.

Ответ 3

Другим способом скина этой кошки было бы реализовать очень простой класс, который расширяет LinkedList, но выполняет любые изменения в списке (например, добавление, удаление и т.д.) внутри "синхронизированного" блока. Вам нужно будет запускать ваш псевдо-указатель HashMap через get() каждый раз, но он должен работать нормально. например.

...
private Object lock = new Object(); //semaphore

//override LinkedList implementations...
@Override
public <T> remove(int index) { synchronized(lock) { return super.remove(index); } }
...

Если у вас есть Eclipse или IntelliJ IDEA, вы должны иметь возможность автоматически генерировать нужный вам метод почти мгновенно, и вы можете оценить, какие из них нужно заблокировать.