Удалить и вставить в LinkedHashMap с помощью итератора?

Я знаю, что невозможно редактировать содержимое HashMap или LinkedHashMap во время итерации, не вызывая исключение ConcurrentModificationException. Однако у меня есть ситуация, когда мне нужно применить это. Я пишу симуляцию виртуальной памяти, используя реализацию Clock алгоритма Second Chance. Примечание. RAM — это LinkedHashMap, поэтому порядок итерации соответствует порядку вставки. Это мой текущий подход (где tmp, hand и entry являются переменными, объявленными вне логики основного цикла:

PTE tmp; // A tmp PageTableEntry reference used for shuffling PTEs across RAM and the Page Table
Iterator<Entry<Integer, PTE>> hand; // Iterator that represents the clock hand
Map.Entry<Integer, PTE> entry = null; // A tmp Map Entry ref that is used to store the return of the hand Iterator


hand = RAM.entrySet().iterator(); // Set the Clock hand to the oldest PTE in RAM
entry = hand.next(); // Advance the iterator to the first RAM entry
tmp = entry.getValue(); // Get the PTE the Clock hand is pointing at

while (tmp.ref && hand.hasNext()) { // Advance the clock hand through RAM until finding an unreferenced PTE
    debugPrint(String.format("while:The hand is pointing at page # %d, ref == %b\n", tmp.baseAddr, tmp.ref), 1);
    tmp.ref = false; // Set the ref bit to false to give the PTE a second chance
    entry = hand.next(); // Select next PTE in RAM
    tmp = entry.getValue();

}

if (tmp.ref && !hand.hasNext()) { // Corner Case: The clock hand has found all PTEs in RAM to be referenced, must follow FIFO
    debugPrint(String.format("!HasNext:The hand is pointing at page # %d, ref == %b\n", tmp.baseAddr, tmp.ref), 1);

    tmp.ref = false; // Marked for eviction, must be set to unreferenced
    hand = RAM.entrySet().iterator(); // Reset the clock hand to point back to the first PTE inserted.
    entry = hand.next();
    tmp = entry.getValue();

}

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


person Steven Montalbano    schedule 09.04.2020    source источник


Ответы (1)


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

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

person Nithin    schedule 09.04.2020