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

Сначала я займусь проблемой 3:

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

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

Проблема 1 и 2:

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

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

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

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
}

1) Итераторы не для этого.

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

_list.addFirst(value);

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

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

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

Время быстрого поиска == Хеш Что-то

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

Быстрая адресация последнего элемента == Somekinda List

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

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

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

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

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

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