以下是针对大厂笔试/面试的LRU缓存淘汰算法全方位解析，涵盖核心原理、多语言实现（Python/Java/C++）、复杂度优化及高频考点，助你系统掌握解题技巧。

---

一、LRU核心原理与适用场景

1. 算法思想

• LRU（Least Recently Used）：优先淘汰最久未使用的数据，基于“时间局部性原理”（最近访问的数据可能被再次访问）。
  ● 最近最少使用原则：当缓存满时，优先淘汰最久未被访问的数据。
  ● 时间局部性假设：最近被访问的数据未来更可能被再次使用。
• 核心操作：
  • get(key)：若存在则返回并提升为“最近使用”。
  • put(key, value)：若存在则更新值并提升；若不存在则插入，容量满时淘汰尾部数据。

2. 适用场景

• 操作系统页面置换、数据库缓存、浏览器缓存、分布式缓存（如Redis）。

---

二、O(1)时间复杂度实现：哈希表+双向链表

数据结构设计

组件	作用	时间复杂度
哈希表（HashMap）	存储键到链表节点的映射，实现O(1)查找	O(1)
双向链表	维护访问顺序：头部为最近访问，尾部为最久未访问，支持O(1)插入/删除节点	O(1)

关键操作流程

1. get(key)：
   • 哈希表查节点 → 存在则移动节点到链表头部 → 返回值。
2. put(key, value)：
   • Key存在：更新值 → 移动节点到头部。
   • Key不存在：创建节点 → 插入链表头部 → 若容量满则删除尾部节点并移除哈希表对应项。

为什么用双向链表？

• 删除任意节点需前驱指针，双向链表支持O(1)删除（单向链表需遍历）。

1. 核心考察点
   ● 数据结构选择：为何用双向链表而非单向？
   → 单向链表删除节点需遍历找前驱（O(n)），双向链表直接操作指针（O(1)）。
   ● 时间复杂度证明：哈希表查找O(1) + 链表插入/删除O(1) = 整体O(1)。
   ● 边界处理：缓存满时删除尾节点需同步更新哈希表（易漏考点）。
2. 性能优化进阶
   优化策略 解决痛点 应用场景
   LRU-K 避免偶发访问污染缓存 数据库查询优化
   分段LRU 减少高并发锁竞争 Redis缓存系统
   预读区隔离 防止预读数据挤占热点数据 MySQL InnoDB
3. 面试常见问题

---

三、多语言代码实现

1. Python实现（使用OrderedDict简化）

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.cache = OrderedDict()
        self.capacity = capacity

    def get(self, key: int) -> int:
        if key not in self.cache: return -1
        self.cache.move_to_end(key)  # 移动到尾部（最近使用）
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)  # 删除头部（最久未使用）

说明：OrderedDict内部维护双向链表，move_to_end和popitem均为O(1)。

2. Java实现（手写双向链表）

class LRUCache {
    class Node {
        int key, value;
        Node prev, next;
        Node(int k, int v) { key = k; value = v; }
    }
    
    private Map<Integer, Node> map = new HashMap<>();
    private Node head = new Node(0, 0), tail = new Node(0, 0);
    private int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        Node node = map.get(key);
        remove(node);
        insert(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) remove(map.get(key));
        if (map.size() == capacity) remove(tail.prev);
        insert(new Node(key, value));
    }

    private void insert(Node node) {
        map.put(node.key, node);
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    private void remove(Node node) {
        map.remove(node.key);
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
}

注意：使用虚拟头节点（head）和尾节点（tail）简化边界处理。

3. C++实现（STL list + unordered_map）

#include <list>
#include <unordered_map>
using namespace std;

class LRUCache {
private:
    int capacity;
    list<pair<int, int>> cache;  // 双向链表：(key, value)
    unordered_map<int, list<pair<int, int>>::iterator> map;  // key -> 链表迭代器

public:
    LRUCache(int cap) : capacity(cap) {}

    int get(int key) {
        if (map.find(key) == map.end()) return -1;
        cache.splice(cache.begin(), cache, map[key]);  // 移动到头部
        return map[key]->second;
    }

    void put(int key, int value) {
        if (get(key) != -1) {  // 利用get移动节点
            map[key]->second = value;
            return;
        }
        if (cache.size() == capacity) {
            map.erase(cache.back().first);  // 删除尾部key
            cache.pop_back();
        }
        cache.push_front({key, value});
        map[key] = cache.begin();
    }
};

优化点：splice直接移动节点指针，避免拷贝开销。

---

四、复杂度分析与高频考点

1. 复杂度

操作	时间复杂度	空间复杂度
get()	O(1)	O(capacity)
put()	O(1)	O(capacity)

2. 面试高频问题

1. 为什么不用单链表？
   → 删除节点需遍历前驱节点，单链表无法O(1)删除。
2. 如何优化高并发场景？
   → 分段锁（如ConcurrentHashMap）或读写锁（ReadWriteLock），牺牲部分一致性提升吞吐。
3. LRU vs LFU（最不常用）
   → LRU基于时间局部性，LFU基于访问频率；LRU更易实现，LFU需维护频率计数器。
4. 缓存污染问题：
   → 偶发批量操作可能挤出热点数据，可改进为LRU-K（考虑历史访问次数）。

3. 手撕代码常见坑点

• 边界条件：容量为0、重复put相同key、删除尾部节点时更新哈希表。
• 指针操作：双向链表的节点移动需同步修改前驱/后继指针（C++/Java易错）。

---

五、优化与扩展方向

1. 时间复杂度优化：
   • 链表中使用跳跃表（SkipList）替代哈希表，减少内存碎片（适用于C++高性能场景）。
2. 空间优化：
   • 预分配节点池：避免频繁内存分配（如C++的allocator）。
3. 分布式LRU：
   • 一致性哈希：将数据分片到多个节点，每节点独立维护LRU（如Redis集群）。

提示：大厂面试常要求解释设计取舍（如时间 vs 空间），务必结合场景分析！LRU算法需紧扣哈希表+双向链表的核心结构，面试时优先写对基础版本，再讨论优化（如线程安全、LRU-K）。代码实现需特别注意虚拟头尾节点的指针操作，此为手撕代码的常见失分点。