map.remove() 在遵循 LRU 实现的 get 方法中有什么用？

Question

我正在研究 LRU 并使用下面的代码片段来理解它的实现。请让我知道 get(int key) 中 map.remove(key) 方法调用的用途。我们不能只使用 map.put(key,value)，这将更新映射中的条目的键。
我在代码下面重新引用。

class LRUMap<K, V> extends LinkedHashMap<K, V>{
    private final int MAX_NUM;
    public LRUMap(int capacity) {
        super(capacity);
        MAX_NUM = capacity;
    }
    protected boolean removeEldestEntry(Map.Entry eldest) {
       return /*true*/ size() > MAX_NUM;
    }
}
public class LRU {
    LRUMap<Integer, Integer> map;
    public LRU(int capacity) {
        map = new LRUMap<Integer, Integer>(capacity);
    }
    public int get(int key) {
        if (map == null || map.get(key) == null)
           return -1;
        int value = map.get(key);
        map.remove(key);
        map.put(key, value);
        return value;
    }
    public void set(int key, int value) {
        if (map == null) return;
        get(key);
        map.put(key, value);
    }
}

Answer 1

这个 LRUMap 扩展了 LinkedHashMap，它按照插入键的顺序维护 Map 条目的链表（第一个键是添加到的第一个键） Map).

当您实现最近最少使用的数据结构时，您想知道哪个元素是最近最少使用的。这是当您从 space.

中运行时首先要删除的元素

现在，如果我们查看 LinkedHashMap Javadoc：

This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order). Note that insertion order is not affected if a key is re-inserted into the map. (A key k is reinserted into a map m if m.put(k, v) is invoked when m.containsKey(k) would return true immediately prior to the invocation.)

我们看到为 Map 中已经存在的键调用 put(k,v) 不会影响插入顺序。

因此，当你访问Map的一个key时，你必须先从LinkedHashMap中删除它，然后重新添加它，从而将它移动到链表的末尾, 并有效地将其标记为最近使用的密钥（这是最后插入的密钥）。

请注意，set() 方法还调用了 get()，这意味着如果键已经在 Map 中，它还会将键移动到链表的末尾。

Answer 2

LRU = 最少最近使用缓存。

当您使用 Key 时，它应该成为最近使用的。简单地更新它不会使它成为最近使用最多的，因为它不会更改基础 LinkedList.
中的索引因此 remove 并把它放回去。这样它就变成了最新的。

map.remove() 在遵循 LRU 实现的 get 方法中有什么用？

What is use of map.remove() in get method of following LRU implementation?

java

lru