《LRU 缓存淘汰算法》

LRU（Least Recently Used，最近最少使用）是一种缓存淘汰策略：当缓存容量满时，优先淘汰最久未被访问的数据。它基于「如果数据最近被访问过，那么将来被访问的概率也更高」的局部性原理。

1 核心思想与数据结构

LRU 的理想实现需要满足：

查询快：get(key) 是 O(1)；
淘汰快：能在 O(1) 内找到并移除最久未使用的数据；
更新快：访问一个已存在的 key 后，要把它标记为「最新使用」。

常用的组合是 哈希表 + 双向链表：

哈希表（key -> 链表结点） 保证 O(1) 定位；
双向链表（按访问时间排序） 保证 O(1) 插入头部、删除尾部（需要 prev 指针才能在 O(1) 内摘除中间结点，因此用双向链表而不是单向链表）。

操作流程：

get(key)：哈希表查到结点后，将其移动到链表头部，返回 value；
add(key, value)：
1. 若 key 已存在，更新 value 并移动到头部；
2. 若容量未满，直接在头部插入新结点；
3. 若容量已满，先删除链表尾部（最久未使用）结点，再在头部插入新结点。

2 复杂度分析

时间：get / add 均为 O(1)；
空间：O(capacity)。

3 实现（Python）

3.1 基于双向链表 + 哈希表

        
      
class Node(object):
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.previous = None
        self.next = None


class LRUCache(object):
    def __init__(self, capacity):
        self.head = None      # 链表头部，表示最近使用
        self.tail = None      # 链表尾部，表示最久未使用
        self.cache = {}       # key -> Node
        self.capacity = capacity
        self.size = 0

    def _remove_node(self, node):
        if node.previous:
            node.previous.next = node.next
        else:
            self.head = node.next
        if node.next:
            node.next.previous = node.previous
        else:
            self.tail = node.previous
        node.previous = None
        node.next = None

    def _add_to_head(self, node):
        node.next = self.head
        node.previous = None
        if self.head:
            self.head.previous = node
        self.head = node
        if self.tail is None:
            self.tail = node

    def _move_to_head(self, node):
        self._remove_node(node)
        self._add_to_head(node)

    def get(self, key):
        node = self.cache.get(key)
        if not node:
            return -1
        self._move_to_head(node)
        return node.value

    def put(self, key, value):
        node = self.cache.get(key)
        if node:
            node.value = value
            self._move_to_head(node)
            return

        new_node = Node(key, value)
        self.cache[key] = new_node
        self._add_to_head(new_node)
        self.size += 1

        if self.size > self.capacity:
            # 淘汰最久未使用的尾部结点
            del self.cache[self.tail.key]
            self._remove_node(self.tail)
            self.size -= 1

3.2 使用 OrderedDict（Python 3 简化版）

        
      
from collections import OrderedDict


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

    def get(self, key):
        if key not in self.cache:
            return -1
        # 访问过的 key 移到末尾，表示最近使用
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key, value):
        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)  # 淘汰最久未使用的

注意：手写版本需要注意双向链表插删时的指针边界（头/尾结点处理容易出 bug）；OrderedDict 版本适合面试快速作答，但其底层同样是哈希表 + 双向链表。

4 实现（C）

使用哈希表（存放指向队列结点的指针）+ 双向链表实现：

        
      
#include <stdio.h>
#include <stdlib.h>

// 双向链表结点，QNode* 表示缓存中的一页
typedef struct QNode {
    struct QNode *prev, *next;
    unsigned pageNumber;
} QNode;

// 队列（由双向链表组成，front 最近使用，rear 最久未使用）
typedef struct Queue {
    unsigned count;
    unsigned numberOfFrames;
    QNode *front, *rear;
} Queue;

// 哈希表（存指向队列结点的指针）
typedef struct Hash {
    int capacity;
    QNode** array;
} Hash;

QNode* newQNode(unsigned pageNumber) {
    QNode* temp = (QNode*)malloc(sizeof(QNode));
    temp->pageNumber = pageNumber;
    temp->prev = temp->next = NULL;
    return temp;
}

Queue* createQueue(int numberOfFrames) {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->count = 0;
    queue->front = queue->rear = NULL;
    queue->numberOfFrames = numberOfFrames;
    return queue;
}

Hash* createHash(int capacity) {
    Hash* hash = (Hash*)malloc(sizeof(Hash));
    hash->capacity = capacity;
    hash->array = (QNode**)malloc(hash->capacity * sizeof(QNode*));
    int i;
    for (i = 0; i < hash->capacity; ++i)
        hash->array[i] = NULL;
    return hash;
}

int areAllFramesFull(Queue* queue) {
    return queue->count == queue->numberOfFrames;
}

int isQueueEmpty(Queue* queue) {
    return queue->rear == NULL;
}

// 从队尾删除（淘汰最久未使用）
void deQueue(Queue* queue) {
    if (isQueueEmpty(queue))
        return;
    if (queue->front == queue->rear)
        queue->front = NULL;
    QNode* temp = queue->rear;
    queue->rear = queue->rear->prev;
    if (queue->rear)
        queue->rear->next = NULL;
    free(temp);
    queue->count--;
}

// 加入新页：队列满则先淘汰 rear，新结点插入 front
void enqueue(Queue* queue, Hash* hash, unsigned pageNumber) {
    if (areAllFramesFull(queue)) {
        hash->array[queue->rear->pageNumber] = NULL;
        deQueue(queue);
    }

    QNode* temp = newQNode(pageNumber);
    temp->next = queue->front;
    if (isQueueEmpty(queue))
        queue->rear = queue->front = temp;
    else {
        queue->front->prev = temp;
        queue->front = temp;
    }
    hash->array[pageNumber] = temp;
    queue->count++;
}

// 访问一页：不在缓存则入队；在缓存且不在队首则移动到队首
void referencePage(Queue* queue, Hash* hash, unsigned pageNumber) {
    QNode* reqPage = hash->array[pageNumber];
    if (reqPage == NULL) {
        enqueue(queue, hash, pageNumber);
    } else if (reqPage != queue->front) {
        // 从原位置摘除
        reqPage->prev->next = reqPage->next;
        if (reqPage->next)
            reqPage->next->prev = reqPage->prev;
        if (reqPage == queue->rear) {
            queue->rear = reqPage->prev;
            queue->rear->next = NULL;
        }
        // 移到队首
        reqPage->next = queue->front;
        reqPage->prev = NULL;
        reqPage->next->prev = reqPage;
        queue->front = reqPage;
    }
}

int main() {
    Queue* q = createQueue(4);    // 缓存容量 4
    Hash* hash = createHash(10);  // 页面编号 0~9

    referencePage(q, hash, 1);
    referencePage(q, hash, 2);
    referencePage(q, hash, 3);
    referencePage(q, hash, 1);
    referencePage(q, hash, 4);
    referencePage(q, hash, 5);

    QNode* cur = q->front;
    while (cur) {
        printf("%d ", cur->pageNumber);
        cur = cur->next;
    }
    printf("\n");
    return 0;
}

5 典型应用

操作系统：内存页面的页面置换算法（LRU 近似算法、Clock 算法是其变体）；
Redis：maxmemory-policy 支持 volatile-lru / allkeys-lru；
MySQL Buffer Pool：innodb_buffer_pool 链表（LRU + 冷热分区优化）；
浏览器 / HTTP 缓存：HTTP 缓存淘汰。

6 延伸考点

LRU vs LFU：LFU 按访问频次淘汰（Redis 4.0 提供 allkeys-lfu）；LFU 能避免「冷数据被偶尔访问一次后霸占缓存」的问题，但实现更复杂（增加频次维护）；
LRU 的缺点：偶发的大批量数据访问会把缓存「污染」，可结合多段 LRU / Clock / TinyLFU 缓解；
LeetCode 例题：146. LRU 缓存。

阅读 — · 全站 —