LRU 算法详解与多语言实现（Java/Python/C++）

1. 什么是 LRU 算法？

LRU（Least Recently Used，最近最少使用）算法是一种常用的缓存淘汰策略。当缓存空间已满，需要添加新的数据时，LRU 算法会选择最近最少使用的数据进行淘汰，为新数据腾出空间。

核心思想： 最近被访问过的数据，在未来更有可能被再次访问。因此，维护一个访问顺序，淘汰最久未被访问的数据。

应用场景： LRU 算法广泛应用于各种缓存系统，例如：

• CPU 缓存
• 数据库缓存
• Web 服务器缓存
• 浏览器缓存
• 操作系统页面置换

2. LRU 算法的实现思路

LRU 算法通常使用两种数据结构来实现：

1. 哈希表（Hash Table/Dictionary）： 用于快速查找缓存中的数据（O(1) 时间复杂度）。键（key）是数据的标识，值（value）是指向双向链表节点的指针（或引用）。

2. 双向链表（Doubly Linked List）： 用于维护数据的访问顺序。最近访问的数据放在链表头部，最久未访问的数据放在链表尾部。

基本操作：

• get(key)：

  • 如果 key 存在于哈希表中：
    • 将对应的链表节点移动到链表头部（表示最近访问）。
    • 返回节点的值。
  • 如果 key 不存在于哈希表中：
    • 返回 -1 (或其他表示未找到的值)。

• put(key, value)：

  • 如果 key 已经存在于哈希表中：
    • 更新节点的值。
    • 将对应的链表节点移动到链表头部。
  • 如果 key 不存在于哈希表中：
    • 如果缓存已满：
      • 移除链表尾部的节点（最久未访问）。
      • 从哈希表中删除对应的键。
    • 创建一个新的节点，包含 key 和 value。
    • 将新节点添加到链表头部。
    • 将 key 和指向新节点的指针（或引用）添加到哈希表中。

3. 多语言实现 (Java/Python/C++)

下面分别用 Java、Python 和 C++ 实现 LRU 算法。

3.1. Java 实现

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

class LRUCache {

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

    public Node(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

private int capacity;
private Map<Integer, Node> map = new HashMap<>();
private Node head = new Node(-1, -1); // Dummy head
private Node tail = new Node(-1, -1); // Dummy tail

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

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

public void put(int key, int value) {
    if (map.containsKey(key)) {
        Node node = map.get(key);
        node.value = value;
        removeNode(node);
        addToHead(node);
    } else {
        if (map.size() == capacity) {
            Node tailPrev = tail.prev;
            removeNode(tailPrev);
            map.remove(tailPrev.key);
        }
        Node newNode = new Node(key, value);
        map.put(key, newNode);
        addToHead(newNode);
    }
}

private void removeNode(Node node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
}

private void addToHead(Node node) {
    node.next = head.next;
    node.next.prev = node;
    node.prev = head;
    head.next = node;
}
public static void main(String[] args) {
    LRUCache lruCache = new LRUCache(2);
    lruCache.put(1, 1);
    lruCache.put(2, 2);
    System.out.println(lruCache.get(1));       // 返回 1
    lruCache.put(3, 3);    // 该操作会使得密钥 2 作废
    System.out.println(lruCache.get(2));       // 返回 -1 (未找到)
    lruCache.put(4, 4);    // 该操作会使得密钥 1 作废
    System.out.println(lruCache.get(1));       // 返回 -1 (未找到)
    System.out.println(lruCache.get(3));       // 返回 3
    System.out.println(lruCache.get(4));       // 返回 4
}

}
```

3.2. Python 实现

```python
class Node:
def init(self, key, value):
self.key = key
self.value = value
self.prev = None
self.next = None

class LRUCache:
def init(self, capacity):
self.capacity = capacity
self.cache = {} # Dictionary to store key-node mapping
self.head = Node(-1, -1) # Dummy head
self.tail = Node(-1, -1) # Dummy tail
self.head.next = self.tail
self.tail.prev = self.head

def get(self, key):
    if key in self.cache:
        node = self.cache[key]
        self._remove_node(node)
        self._add_to_head(node)
        return node.value
    return -1

def put(self, key, value):
    if key in self.cache:
        node = self.cache[key]
        node.value = value
        self._remove_node(node)
        self._add_to_head(node)
    else:
        if len(self.cache) == self.capacity:
            tail_prev = self.tail.prev
            self._remove_node(tail_prev)
            del self.cache[tail_prev.key]
        new_node = Node(key, value)
        self.cache[key] = new_node
        self._add_to_head(new_node)

def _remove_node(self, node):
    node.prev.next = node.next
    node.next.prev = node.prev

def _add_to_head(self, node):
    node.next = self.head.next
    node.next.prev = node
    node.prev = self.head
    self.head.next = node

Example usage (same as Java example):

lru_cache = LRUCache(2)
lru_cache.put(1, 1)
lru_cache.put(2, 2)
print(lru_cache.get(1)) # Output: 1
lru_cache.put(3, 3)
print(lru_cache.get(2)) # Output: -1
lru_cache.put(4, 4)
print(lru_cache.get(1)) # Output: -1
print(lru_cache.get(3)) # Output: 3
print(lru_cache.get(4)) # Output: 4
```

3.3. C++ 实现

```c++

include

include

include

class LRUCache {
private:
int capacity;
std::unordered_map>::iterator> cache;
std::list> lru_list; // {key, value}

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

int get(int key) {
    auto it = cache.find(key);
    if (it == cache.end()) {
        return -1;
    }
    // Move the accessed element to the front of the list
    lru_list.splice(lru_list.begin(), lru_list, it->second);
    return it->second->second;
}

void put(int key, int value) {
    auto it = cache.find(key);
    if (it != cache.end()) {
        // Update the value and move the element to the front
        it->second->second = value;
        lru_list.splice(lru_list.begin(), lru_list, it->second);
    } else {
        if (cache.size() == capacity) {
            // Remove the least recently used element
            int lru_key = lru_list.back().first;
            cache.erase(lru_key);
            lru_list.pop_back();
        }
        // Add the new element to the front
        lru_list.push_front({key, value});
        cache[key] = lru_list.begin();
    }
}
// 主函数，用于测试
int main() {
LRUCache lruCache(2);
lruCache.put(1, 1);
lruCache.put(2, 2);
std::cout << lruCache.get(1) << std::endl;       // 返回 1
lruCache.put(3, 3);    // 该操作会使得密钥 2 作废
std::cout << lruCache.get(2) << std::endl;       // 返回 -1 (未找到)
lruCache.put(4, 4);    // 该操作会使得密钥 1 作废
std::cout << lruCache.get(1) << std::endl;       // 返回 -1 (未找到)
std::cout << lruCache.get(3) << std::endl;       // 返回 3
std::cout << lruCache.get(4) << std::endl;       // 返回 4
return 0;
}

};
```
代码解释（C++）：

• std::unordered_map: 用于实现哈希表，提供 O(1) 的查找。
• std::list: 用于实现双向链表，提供 O(1) 的插入和删除。 splice() 函数用于在链表中移动元素，效率很高。
• lru_list 存储的是pair, 包含key和value.
• cache的值是 lru_list的iterator, 可以用O(1)的时间复杂度定位到lru_list中的元素.

4. 总结

LRU 算法是一种高效的缓存淘汰策略，通过哈希表和双向链表的结合，实现了快速查找和维护访问顺序的功能。 在实际应用中，可以根据具体需求选择合适的语言和数据结构来实现 LRU 算法。

关键点回顾：

• 哈希表用于快速查找。
• 双向链表用于维护访问顺序。
• get 操作需要将访问的节点移动到链表头部。
• put 操作可能需要淘汰最久未访问的节点（链表尾部）。

希望这篇文章能帮助你深入理解 LRU 算法及其实现！