面试重要程度：⭐⭐⭐⭐⭐

常见提问方式： "设计LRU缓存" "实现LFU算法" "缓存淘汰策略对比"

预计阅读时间：40分钟

🎯 LRU缓存实现

LRU基本概念

LRU (Least Recently Used) 最近最少使用算法，是一种常用的缓存淘汰策略。

核心思想： 当缓存满时，优先淘汰最久未被访问的数据。

LRU算法实现

/**
 * LRU缓存实现
 * LeetCode 146: LRU Cache
 */
public class LRUCache {
    
    /**
     * 双向链表节点
     */
    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
        
        public DLinkedNode() {}
        
        public DLinkedNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    
    private Map<Integer, DLinkedNode> cache = new HashMap<>();
    private int size;
    private int capacity;
    private DLinkedNode head, tail;
    
    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        
        // 使用伪头部和伪尾部节点
        head = new DLinkedNode();
        tail = new DLinkedNode();
        
        head.next = tail;
        tail.prev = head;
    }
    
    /**
     * 获取缓存值
     * 时间复杂度：O(1)
     */
    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            return -1;
        }
        
        // 如果key存在，先通过哈希表定位，再移到头部
        moveToHead(node);
        
        return node.value;
    }
    
    /**
     * 添加缓存值
     * 时间复杂度：O(1)
     */
    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);
        
        if (node == null) {
            DLinkedNode newNode = new DLinkedNode(key, value);
            
            // 添加进哈希表
            cache.put(key, newNode);
            // 添加至双向链表的头部
            addToHead(newNode);
            
            ++size;
            
            if (size > capacity) {
                // 如果超出容量，删除双向链表的尾部节点
                DLinkedNode tail = removeTail();
                // 删除哈希表中对应的项
                cache.remove(tail.key);
                --size;
            }
        } else {
            // 如果key存在，先通过哈希表定位，再修改value，并移到头部
            node.value = value;
            moveToHead(node);
        }
    }
    
    /**
     * 添加节点到头部
     */
    private void addToHead(DLinkedNode node) {
        node.prev = head;
        node.next = head.next;
        
        head.next.prev = node;
        head.next = node;
    }
    
    /**
     * 删除节点
     */
    private void removeNode(DLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    
    /**
     * 移动节点到头部
     */
    private void moveToHead(DLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }
    
    /**
     * 删除尾部节点
     */
    private DLinkedNode removeTail() {
        DLinkedNode lastNode = tail.prev;
        removeNode(lastNode);
        return lastNode;
    }
}

基于LinkedHashMap的简化实现

/**
 * 基于LinkedHashMap的LRU实现
 */
public class LRUCacheSimple extends LinkedHashMap<Integer, Integer> {
    private int capacity;
    
    public LRUCacheSimple(int capacity) {
        super(capacity, 0.75F, true);
        this.capacity = capacity;
    }
    
    public int get(int key) {
        return super.getOrDefault(key, -1);
    }
    
    public void put(int key, int value) {
        super.put(key, value);
    }
    
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;
    }
}

🔄 LFU缓存实现

LFU基本概念

LFU (Least Frequently Used) 最不经常使用算法，根据数据的历史访问频率来淘汰数据。

核心思想： 当缓存满时，优先淘汰访问频率最低的数据。

LFU算法实现

/**
 * LFU缓存实现
 * LeetCode 460: LFU Cache
 */
public class LFUCache {
    
    /**
     * 缓存节点
     */
    class Node {
        int key, val, freq;
        Node prev, next;
        
        public Node(int key, int val) {
            this.key = key;
            this.val = val;
            this.freq = 1;
        }
    }
    
    /**
     * 双向链表
     */
    class DoublyLinkedList {
        Node head, tail;
        
        public DoublyLinkedList() {
            head = new Node(0, 0);
            tail = new Node(0, 0);
            head.next = tail;
            tail.prev = head;
        }
        
        public void addFirst(Node node) {
            Node next = head.next;
            node.next = next;
            next.prev = node;
            node.prev = head;
            head.next = node;
        }
        
        public void remove(Node node) {
            Node prev = node.prev;
            Node next = node.next;
            prev.next = next;
            next.prev = prev;
        }
        
        public Node removeLast() {
            if (head.next == tail) {
                return null;
            }
            Node last = tail.prev;
            remove(last);
            return last;
        }
        
        public boolean isEmpty() {
            return head.next == tail;
        }
    }
    
    private int capacity;
    private int minFreq;
    private Map<Integer, Node> keyToNode;
    private Map<Integer, DoublyLinkedList> freqToList;
    
    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.minFreq = 0;
        this.keyToNode = new HashMap<>();
        this.freqToList = new HashMap<>();
    }
    
    public int get(int key) {
        Node node = keyToNode.get(key);
        if (node == null) {
            return -1;
        }
        
        // 增加频率
        increaseFreq(node);
        return node.val;
    }
    
    public void put(int key, int value) {
        if (capacity <= 0) return;
        
        Node node = keyToNode.get(key);
        if (node != null) {
            // 更新已存在的key
            node.val = value;
            increaseFreq(node);
            return;
        }
        
        // 添加新key
        if (keyToNode.size() >= capacity) {
            // 删除最少使用的节点
            removeMinFreqNode();
        }
        
        // 插入新节点
        Node newNode = new Node(key, value);
        keyToNode.put(key, newNode);
        freqToList.computeIfAbsent(1, k -> new DoublyLinkedList()).addFirst(newNode);
        minFreq = 1;
    }
    
    private void increaseFreq(Node node) {
        int freq = node.freq;
        
        // 从原频率链表中删除
        freqToList.get(freq).remove(node);
        
        // 如果原频率链表为空且是最小频率，更新最小频率
        if (freqToList.get(freq).isEmpty() && freq == minFreq) {
            minFreq++;
        }
        
        // 增加频率并添加到新频率链表
        node.freq++;
        freqToList.computeIfAbsent(node.freq, k -> new DoublyLinkedList()).addFirst(node);
    }
    
    private void removeMinFreqNode() {
        DoublyLinkedList list = freqToList.get(minFreq);
        Node node = list.removeLast();
        keyToNode.remove(node.key);