如何实现LRU缓存淘汰算法？

LRU(Least Recently Used)是一种缓存淘汰算法,最近最少使用的缓存项会被淘汰。

我们可以使用双向链表与哈希表实现 LRU 算法:

public class LRUCache {
    class ListNode {
        int key;
        int val;
        ListNode prev;
        ListNode next;
        ListNode(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    private int capacity;
    private HashMap<Integer, ListNode> map;
    private ListNode head;
    private ListNode tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
    }

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        ListNode node = map.get(key);
        remove(node);
        addToHead(node);
        return node.val;
    }

    public void put(int key, int val) {
        if (map.containsKey(key)) {
            ListNode node = map.get(key);
            node.val = val;
            remove(node);
            addToHead(node);
        } else {
            if (map.size() == capacity) {
                map.remove(tail.key);
                removeTail();
            }
            ListNode node = new ListNode(key, val);
            addToHead(node);
            map.put(key, node);
        }
    }

    private void remove(ListNode node) {
        ListNode prev = node.prev;
        ListNode next = node.next;
        prev.next = next;
        next.prev = prev;
    }

    private void addToHead(ListNode node) {
        node.next = head.next;
        node.prev = head; 
        head.next.prev = node;
        head.next = node;
    }

    private void removeTail() {
        ListNode prev = tail.prev;
        prev.next = null;
        tail = prev;
    }
}

所以,LRU 缓存淘汰算法的实现步骤为:

1. 使用双向链表存储缓存项,最近使用的项靠近头部。
2. 使用哈希表记录每个缓存项在链表中的位置。
3. get 操作:如果 key 存在,则返回对应值,并将该项移到链表头部。
4. put 操作:如果 key 存在,则更新值,并将该项移到链表头部。如果不存在,添加至链表头部。如果达到容量,则删除链表尾部项。
5. 删除链表尾部项时,同时需要从哈希表中移除。
6. 特殊情况:如果链表为空,添加的第一项既是头部又是尾部项。

LRU 算法可以有效地实现缓存淘汰,保证最近使用的缓存数据时刻可用。会使用代码实现 LRU 算法,可以让我们熟练掌握链表、哈希表等数据结构,这是算法与编程的重要基础。
LRU 缓存淘汰算法这一经典问题涉及到链表、哈希表、插入、删除等知识点与技能。深入理解和掌握这些基本工具,可以让我们具备解决算法与编程更高难度问题的能力。