面试题：缓存设计：LRU缓存替换策略的基本原理及实现

LRU缓存替换策略基本原理

LRU（Least Recently Used）缓存替换策略的基本原理是：当缓存满时，优先淘汰最久未使用的数据。在缓存的使用过程中，每次访问（读或写）一个数据项，就将该数据项标记为最近使用，这样当缓存空间不足需要淘汰数据时，最久未被访问的数据项就会被替换出去。

Python实现LRU缓存

from collections import OrderedDict


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

    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)

使用示例

# 初始化缓存容量为2
cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1))  # 返回 1
cache.put(3, 3)  # 缓存已满，淘汰掉最久未使用的键 2
print(cache.get(2))  # 返回 -1，因为 2 已被淘汰
cache.put(4, 4)  # 缓存已满，淘汰掉最久未使用的键 1
print(cache.get(1))  # 返回 -1，因为 1 已被淘汰
print(cache.get(3))  # 返回 3
print(cache.get(4))  # 返回 4

Java实现LRU缓存

import java.util.HashMap;
import java.util.Map;

class DLinkedNode {
    int key;
    int value;
    DLinkedNode prev;
    DLinkedNode next;

    public DLinkedNode() {
    }

    public DLinkedNode(int _key, int _value) {
        key = _key;
        value = _value;
    }
}

class LRUCache {
    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;
    }

    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            return -1;
        }
        // 将节点移到双向链表头部
        moveToHead(node);
        return node.value;
    }

    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 removed = removeTail();
                cache.remove(removed.key);
                --size;
            }
        } else {
            // 更新节点的值，并移到双向链表头部
            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 node = tail.prev;
        removeNode(node);
        return node;
    }
}

使用示例

// 初始化缓存容量为2
LRUCache cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
System.out.println(cache.get(1)); // 返回 1
cache.put(3, 3); // 缓存已满，淘汰掉最久未使用的键 2
System.out.println(cache.get(2)); // 返回 -1，因为 2 已被淘汰
cache.put(4, 4); // 缓存已满，淘汰掉最久未使用的键 1
System.out.println(cache.get(1)); // 返回 -1，因为 1 已被淘汰
System.out.println(cache.get(3)); // 返回 3
System.out.println(cache.get(4)); // 返回 4

星途面试题库

面试题：缓存设计：LRU缓存替换策略的基本原理及实现

知识考点

面试题答案

LRU缓存替换策略基本原理

Python实现LRU缓存

使用示例

Java实现LRU缓存

使用示例