LRU缓存实现中get方法里map.remove()的作用及替代疑问

嘿，我来帮你拆解这个LRU实现里的疑问～首先得先搞清楚你用的LinkedHashMap的核心特性，再分析这段代码的逻辑。

先说说为啥要先删再加 #

你现在的LRUMap继承了LinkedHashMap，但默认是按插入顺序维护键值对的（因为你构造父类的时候没传第三个参数）。这时候，当你调用get(key)拿到值之后，执行map.remove(key)再map.put(key, value)，本质是把这个刚被访问的键值对挪到链表的最后面，相当于给它打个“最近刚用过”的标记。这样等缓存容量超了的时候，removeEldestEntry就会删掉链表最前面那个最久没被碰过的条目，刚好符合LRU（最近最少使用）的规则。

要是你直接用map.put(key, value)更新会咋样？

• 当key已经存在时，LinkedHashMap的put只会更新对应的值，但不会动它在链表中的位置（毕竟默认是插入顺序，只认第一次插入的位置）。那这个刚被访问的条目就还待在原来的地方，不会被标记成“最近使用”，等缓存满了的时候，说不定会被误当成“最久没用”的删掉，直接违背了LRU的初衷。

那有没有办法不用删了再加？ #

当然有！但前提是你得把LinkedHashMap改成访问顺序模式。修改你的LRUMap构造函数就行：

public LRUMap(int capacity) {
    // 第三个参数传true，开启访问顺序模式
    super(capacity, 0.75f, true);
    MAX_NUM = capacity;
}

开启这个模式后，LinkedHashMap的get方法会自动把被访问的条目移到链表末尾，自动标记成“最近使用”。这时候你的get方法就能简化成这样：

public int get(int key) {
    if (map == null || !map.containsKey(key)) return -1;
    return map.get(key);
}

完全不用手动删了再加，get操作自己就把顺序更新好了～

顺便提个你的代码小疏漏 #

你当前的LRUMap构造只传了capacity给父类，默认是插入顺序，其实这根本没法正确实现LRU——插入顺序只记录第一次插入的先后，不会管你后来有没有访问过。所以开启访问顺序才是实现LRU的关键一步哦。

另外你的set方法里先调用了get(key)，要是开启了访问顺序，put方法在更新已存在的键时，也会自动把条目移到末尾，所以set方法其实不用先调用get，直接put就行啦。

内容的提问来源于stack exchange，提问作者viki s