LRU缓存[线性表 -＞ 链表 -＞ hash定位 -＞ 双向链表]

前言

对于LRU缓存，记忆根在hash + 双向链表，而分析的逻辑为线性表 -> 链表 -> hash定位 -> 双向链表。

一、LRU缓存

二、从线性表到hash + 双向链表

package everyday.medium;

import java.util.HashMap;
import java.util.Map;

// LRU缓存
public class LRUCache {
    
    /* 存在固定容量的Entry线性表，put/get时 -> 当容量足时，则寻找Entry将其删除，再在线性表后加入Entry。 当容量不足时，寻找Entry将其删掉，如果没有应该删第一个Entry，由此可见线性表物理结构应该采用链表。 注意到要寻找Entry，可采用hash来快速定位Entry。 注意到要删除hash定位到的节点，而不是遍历的方式，这需要双向链表来获取前驱后继。 review: idea：从线性表 -> 链表 -> hash -> 双向链表 core:链表操作，防止断链，核心：不要把当前节点的prev/next先断掉就行，比较需要靠它把前驱后继联系起来。 辅助：hash提速。 回忆逻辑根：双向链表 + hash定位。 */
    int capacity;
    Node dummyHead, dummyTail;
    Map<Integer, Node> fx;
    int len;

    public LRUCache(int capacity) {
    
        this.capacity = capacity;

        dummyHead = new Node(-1, -1);
        dummyTail = new Node(-1, -1);
        dummyHead.next = dummyTail;
        dummyTail.prev = dummyHead;

        fx = new HashMap<>();
    }

    public int get(int key) {
    
        Node n = fx.get(key);

        if (n == null) return -1;
        // step1:访问过，应该将节点移到末尾。
        n.prev.next = n.next;
        n.next.prev = n.prev;
        // 很明显，这个可以复用，整成函数。
        dummyTail.prev.next = n;
        n.prev = dummyTail.prev;
        dummyTail.prev = n;
        n.next = dummyTail;

        return n.value;
    }

    public void put(int key, int value) {
    
        if (fx.containsKey(key)) {
    
            // 移除指定节点即可。
            Node n = fx.get(key);

            n.prev.next = n.next;
            n.next.prev = n.prev;

            --len;
        }
        if (len >= capacity) {
    
            // step1:链表移除头节点；
            Node old = dummyHead.next;

            dummyHead.next = dummyHead.next.next;
            dummyHead.next.prev = dummyHead;
            // step2:map移除旧节点。
            fx.remove(old.key);

            --len;
        }
        Node n = new Node(key, value);
        // step1：插入新节点到链表最后。
        dummyTail.prev.next = n;
        n.prev = dummyTail.prev;
        n.next = dummyTail;
        dummyTail.prev = n;
        // step2：插入新节点到map
        fx.put(key, n);

        ++len;
    }

    static class Node {
    
        int key, value;

        Node prev, next;

        Node(int k, int v) {
    
            key = k;
            value = v;
        }
    }
}

总结

1）总结一个知识点的逻辑根，辅助自己将来碰到同样的题进行快速分析。如LRU回忆逻辑根hash+双向链表，再写时可从线性表分析到双向链表。
2）线性表 -> 链表 -> hash定位 -> 双向链表，缺什么数据结构拿什么数据结构，无法将idea转码，就面向循环分支进行抽象，以达到问题转换。

参考文献

[1] LeetCode LRU缓存