英文:
Remove and Insert into a LinkedHashMap using iterator?
问题
我知道在迭代HashMap或LinkedHashMap时，如果在迭代过程中编辑其内容，会抛出ConcurrentModificationException异常，这是不可行的。然而，我有一个情况需要应用这个操作。我正在使用Second Chance算法的Clock实现来编写虚拟内存模拟。注意：RAM是一个LinkedHashMap，因此迭代顺序遵循插入顺序。
以下是我当前的方法（其中tmp、hand和entry是在主循环逻辑之外声明的变量）：
PTE tmp; // 用于在RAM和Page Table之间移动PTE的临时PageTableEntry引用
Iterator<Entry<Integer, PTE>> hand; // 表示时钟手的迭代器
Map.Entry<Integer, PTE> entry = null; // 用于存储手的迭代器返回值的临时Map Entry引用
hand = RAM.entrySet().iterator(); // 将时钟手设置为RAM中最旧的PTE
entry = hand.next(); // 将迭代器前进到第一个RAM条目
tmp = entry.getValue(); // 获取时钟手指向的PTE
while (tmp.ref && hand.hasNext()) { // 通过RAM推进时钟手，直到找到未引用的PTE
debugPrint(String.format("while:The hand is pointing at page # %d, ref == %b\n", tmp.baseAddr, tmp.ref), 1);
tmp.ref = false; // 将引用位设置为false，以给予PTE第二次机会
entry = hand.next(); // 选择RAM中的下一个PTE
tmp = entry.getValue();
}
if (tmp.ref && !hand.hasNext()) { // 特殊情况：时钟手发现RAM中的所有PTE都被引用，必须遵循FIFO
debugPrint(String.format("!HasNext:The hand is pointing at page # %d, ref == %b\n", tmp.baseAddr, tmp.ref), 1);
tmp.ref = false; // 标记为驱逐，必须设置为未引用
hand = RAM.entrySet().iterator(); // 将时钟手重置为指向第一个插入的PTE。
entry = hand.next();
tmp = entry.getValue();
}
这产生了几乎正确的输出，但我的问题是迭代器不应在每次使用算法时都被重新创建。我需要一种方法来存储迭代器将要指向的下一个元素，以便我可以从LinkedHashMap中删除tmp，并用新的PageTableEntry替换它，这样下一次迭代器运行时就可以从上次离开的地方继续，直到它到达末尾并必须回到起点。
英文:
I know its not possible to edit a HashMap or LinkedHashMap content during iteration without throwing a ConcurrentModificationException. However, I have a situation where I need to apply that. I am writing a virtual memory simulation using the Clock implementation of the Second Chance algorithm. Note: RAM is a LinkedHashMap so that the iteration order follows insertion order.
This is my current approach (where tmp, hand, and entry are variables declared outside the main loop logic:
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();
}
This produces nearly correct output, but my problem is that the iterator should not be recereated each time the algorithm is used. I need a way to store the next element the iterator would be pointing to so that I can remove tmp from the LinkedHashMap and replace it with the new PageTableEntry that goes there so that next time the iterator runs it resumes from where it left off, not seeing the newly added entry until it reaches the end and has to loop back around.
答案1
得分: 0
Iterator接口没有提供向其中添加元素并防止并发修改的API，这是其目标之一，所以恐怕除非您编写自己的LinkedHashMap实现，否则很难进行优化。
我看不到对映射键的任何用法，所以如果可以更改LinkedHashMap，那么您可能可以通过始终想要进行顺序处理时使用队列，或者如果您有一些查找操作，也可以使用优先级队列来避免这种复杂性。
英文:
Iterator interface does not have an API to add elements to it and prevent concurrent modifications was one of its objectives, so I'm afraid that optimisation is very difficult unless you write your own implementation of LinkedHashMap.
I can't see any usage of the key of the map, so If LinkedHashMap could be changed, then may be your can avoid such complexity by using a queue is you always wanted sequential processing or a priority queue also could be used if you have some lookups
专注分享java语言的经验与见解，让所有开发者获益！
评论