深入理解 LRU 与 LFU 缓存算法实现

在系统设计和面试中，缓存淘汰策略是高频考点。LRU（最近最少使用）和 LFU（最不经常使用）代表了两种不同的淘汰逻辑，掌握它们的底层实现原理，对于应对高并发架构挑战至关重要。

一、LRU 缓存算法

1. 哈希表 + 双向链表

以 LeetCode 的 LRU Cache 题目为例，核心需求是在 O(1) 时间复杂度内完成 get 和 put 操作。

LRU 题目描述

设计思路

单纯用哈希表无法维护访问顺序，单纯用链表查找效率太低。因此我们采用组合方案：

双向链表：维护节点的访问顺序。最近使用的节点放在头部，最少使用的节点放在尾部。淘汰时直接删除尾部节点。
哈希表：存储 key 到链表节点的映射，实现 O(1) 快速查找。
哑头/哑尾节点：简化边界处理，无需判断链表是否为空或节点是否为头尾。

代码实现

class LRUCache {
    // 1. 双向链表节点类：封装缓存的 key、value，以及前后指针
    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;

        // 无参构造：用于创建哑头/哑尾节点
        public DLinkedNode() {}

        // 有参构造：用于创建真实的缓存节点
        public DLinkedNode(int _key, int _value) {
            this.key = _key;
            this.value = _value;
        }
    }

    // 2. LRUCache 核心成员变量
    private Map<Integer, DLinkedNode> cache = new HashMap<>();
    private int size;       // 当前缓存中的节点数量
    private  capacity;   
     DLinkedNode head; 
     DLinkedNode tail; 

    
      {
        .size = ;
        .capacity = capacity;
        head =  ();
        tail =  ();
        head.next = tail;
        tail.prev = head;
    }

    
       {
           cache.get(key);
         (node == ) {
             -;
        }
        
        moveToHead(node);
         node.value;
    }

    
       {
           cache.get(key);

         (node == ) {
            
                (key, value);
            cache.put(key, newNode);
            addToHead(newNode);
            size++;

            
             (size > capacity) {
                   removeTail();
                cache.remove(tailNode.key);
                size--;
            }
        }  {
            
            node.value = value;
            moveToHead(node);
        }
    }

    
       {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    
       {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    
       {
        removeNode(node);
        addToHead(node);
    }

    
     DLinkedNode  {
           tail.prev;
        removeNode(res);
         res;
    }
}

class LFUCache { // 缓存节点类：实现 Comparable 用于 TreeSet 排序 class Node implements Comparable<Node> { int cnt; // 访问频率 int time; // 时间戳 int key; int value; public Node(int cnt, int time, int key, int value) { this.cnt = cnt; this.time = time; this.key = key; this.value = value; } @Override public boolean equals(Object anObject) { if (this == anObject) return true; if (anObject instanceof Node) { Node rhs = (Node) anObject; return this.cnt == rhs.cnt && this.time == rhs.time; } return false; } @Override public int compareTo(Node rhs) { return cnt == rhs.cnt ? time - rhs.time : cnt - rhs.cnt; } @Override public int hashCode() { return cnt * 1000000007 + time; } } private int capacity; private int time; private Map<Integer, Node> key_table; private TreeSet<Node> S; public LFUCache(int capacity) { this.capacity = capacity; this.time = 0; key_table = new HashMap<>(); S = new TreeSet<>(); } public int get(int key) { if (capacity == 0 || !key_table.containsKey(key)) { return -1; } Node cache = key_table.get(key); S.remove(cache); // 移除旧节点，因为属性要更新 cache.cnt++; cache.time = ++time; S.add(cache); // 重新加入 return cache.value; } public void put(int key, int value) { if (capacity == 0) return; if (!key_table.containsKey(key)) { if (key_table.size() == capacity) { // 淘汰频率最低、最早访问的节点 Node toRemove = S.first(); key_table.remove(toRemove.key); S.remove(toRemove); } Node cache = new Node(1, time++, key, value); key_table.put(key, cache); S.add(cache); } else { Node cache = key_table.get(key); S.remove(cache); cache.cnt++; cache.time = ++time; cache.value = value; S.add(cache); } } }

class LFUCache { private int minfreq; private int capacity; private Map<Integer, Node> keyTable; private Map<Integer, DoublyLinkedList> freqTable; public LFUCache(int capacity) { this.minfreq = 0; this.capacity = capacity; keyTable = new HashMap<>(); freqTable = new HashMap<>(); } public int get(int key) { if (capacity == 0 || !keyTable.containsKey(key)) { return -1; } Node node = keyTable.get(key); int val = node.val; int freq = node.freq; // 从原频率链表移除 freqTable.get(freq).remove(node); // 如果原频率链表为空，删除该频率映射，并更新 minfreq if (freqTable.get(freq).size == 0) { freqTable.remove(freq); if (minfreq == freq) { minfreq += 1; } } // 加入新频率链表 DoublyLinkedList list = freqTable.getOrDefault(freq + 1, new DoublyLinkedList()); list.addFirst(new Node(key, val, freq + 1)); freqTable.put(freq + 1, list); keyTable.put(key, freqTable.get(freq + 1).getHead()); return val; } public void put(int key, int value) { if (capacity == 0) return; if (!keyTable.containsKey(key)) { if (keyTable.size() == capacity) { // 淘汰 minfreq 对应链表的尾节点 Node node = freqTable.get(minfreq).getTail(); keyTable.remove(node.key); freqTable.get(minfreq).remove(node); if (freqTable.get(minfreq).size == 0) { freqTable.remove(minfreq); } } DoublyLinkedList list = freqTable.getOrDefault(1, new DoublyLinkedList()); list.addFirst(new Node(key, value, 1)); freqTable.put(1, list); keyTable.put(key, freqTable.get(1).getHead()); minfreq = 1; } else { // 逻辑同 get，只是更新 value Node node = keyTable.get(key); int freq = node.freq; freqTable.get(freq).remove(node); if (freqTable.get(freq).size == 0) { freqTable.remove(freq); if (minfreq == freq) { minfreq += 1; } } DoublyLinkedList list = freqTable.getOrDefault(freq + 1, new DoublyLinkedList()); list.addFirst(new Node(key, value, freq + 1)); freqTable.put(freq + 1, list); keyTable.put(key, freqTable.get(freq + 1).getHead()); } } class Node { int key, val, freq; Node prev, next; public Node() { this(-1, -1, 0); } public Node(int key, int val, int freq) { this.key = key; this.val = val; this.freq = freq; } } class DoublyLinkedList { Node dummyHead, dummyTail; int size; public DoublyLinkedList() { dummyHead = new Node(); dummyTail = new Node(); dummyHead.next = dummyTail; dummyTail.prev = dummyHead; size = 0; } public void addFirst(Node node) { Node prevHead = dummyHead.next; node.prev = dummyHead; dummyHead.next = node; node.next = prevHead; prevHead.prev = node; size++; } public void remove(Node node) { node.prev.next = node.next; node.next.prev = node.prev; size--; } public Node getHead() { return dummyHead.next; } public Node getTail() { return dummyTail.prev; } } }

深入理解 LRU 与 LFU 缓存算法实现