LRU算法实现：Java/Python/C++代码示例（根据文章内容选择对应语言）

2025-3-22

LRU 缓存机制详解与多语言实现（Java/Python/C++）

在计算机科学中，缓存是一种广泛应用的技术，用于提高数据访问速度。其基本思想是将经常访问的数据存储在更快的存储介质（如内存）中，以便后续访问时能够快速获取。然而，缓存的容量通常是有限的，当缓存空间被占满时，就需要一种策略来决定哪些数据应该被移除，以便为新的数据腾出空间。

最近最少使用（Least Recently Used，LRU）算法就是一种常用的缓存淘汰策略。LRU算法的核心思想是：如果一个数据最近被访问过，那么它将来被访问的可能性也更高。因此，当缓存满时，LRU算法会选择最近最少被访问的数据进行淘汰。

本文将深入探讨LRU算法的原理、实现细节，并提供Java、Python和C++三种编程语言的代码示例。

1. LRU算法原理

LRU算法基于以下假设：

最近被访问的数据在不久的将来更有可能被再次访问。
长时间未被访问的数据在不久的将来被访问的可能性较低。

根据这个假设，LRU算法维护一个数据访问顺序的记录。每当访问一个数据时：

如果数据已存在于缓存中，则将该数据移动到访问顺序的头部（表示最近被访问）。
如果数据不在缓存中，则将该数据添加到访问顺序的头部，并检查缓存是否已满。
- 如果缓存未满，则直接添加。
- 如果缓存已满，则移除访问顺序尾部的数据（表示最近最少被访问）。

2. LRU算法的数据结构选择

实现LRU算法的关键在于如何高效地维护数据访问顺序，并支持快速查找、插入和删除操作。常用的数据结构组合是：

哈希表（Hash Table/Dictionary）：用于快速查找数据是否存在于缓存中。哈希表的键（Key）通常是数据的标识（如文件名、URL等），值（Value）是数据本身或指向数据在链表中位置的指针/引用。
双向链表（Doubly Linked List）：用于维护数据的访问顺序。链表的头部表示最近被访问的数据，尾部表示最近最少被访问的数据。双向链表的优点是可以在O(1)时间内完成节点的插入和删除操作。

3. LRU算法的实现步骤

下面是LRU算法的典型实现步骤：

初始化：创建一个哈希表和一个双向链表。设置缓存的最大容量。
get(key) 操作：
- 在哈希表中查找key。
- 如果key存在：
  - 从双向链表中将对应的节点移动到链表头部。
  - 返回key对应的值。
- 如果key不存在：
  - 返回null或一个特定的值（表示未命中）。
put(key, value) 操作：
- 在哈希表中查找key。
- 如果key存在：
  - 更新key对应的值。
  - 从双向链表中将对应的节点移动到链表头部。
- 如果key不存在：
  - 创建一个新的节点，包含key和value。
  - 将新节点插入到双向链表的头部。
  - 将key和新节点的引用添加到哈希表中。
  - 如果缓存已满（当前节点数超过最大容量）：
    - 移除双向链表的尾部节点。
    - 从哈希表中删除尾部节点对应的key。

4. 代码示例

下面分别用Java、Python和C++实现LRU缓存。

4.1 Java实现

```java
import java.util.HashMap;

class LRUCache {

private final int capacity;
private final HashMap<K, Node<K, V>> map;
private final DoublyLinkedList<K, V> list;

public LRUCache(int capacity) {
    this.capacity = capacity;
    this.map = new HashMap<>();
    this.list = new DoublyLinkedList<>();
}

public V get(K key) {
    if (map.containsKey(key)) {
        Node<K, V> node = map.get(key);
        list.moveToHead(node);
        return node.value;
    }
    return null; // Or throw an exception, depending on the desired behavior
}

public void put(K key, V value) {
    if (map.containsKey(key)) {
        Node<K, V> node = map.get(key);
        node.value = value;
        list.moveToHead(node);
    } else {
        Node<K, V> newNode = new Node<>(key, value);
        map.put(key, newNode);
        list.addFirst(newNode);

        if (map.size() > capacity) {
            Node<K, V> tail = list.removeLast();
            map.remove(tail.key);
        }
    }
}

// 内部类：双向链表节点
private static class Node<K, V> {
    K key;
    V value;
    Node<K, V> prev;
    Node<K, V> next;

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

// 内部类：双向链表
private static class DoublyLinkedList<K, V> {
    private Node<K, V> head;
    private Node<K, V> tail;

    public DoublyLinkedList() {
        head = new Node<>(null, null); // Dummy head
        tail = new Node<>(null, null); // Dummy tail
        head.next = tail;
        tail.prev = head;
    }

    public void addFirst(Node<K, V> node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    public void moveToHead(Node<K, V> node) {
        removeNode(node);
        addFirst(node);
    }

    public void removeNode(Node<K,V> node){
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    public Node<K, V> removeLast() {
        if (head.next == tail) {
            return null; // Empty list
        }
        Node<K, V> lastNode = tail.prev;
        removeNode(lastNode);
        return lastNode;
    }
}

  public static void main(String[] args) {
    LRUCache<Integer, String> cache = new LRUCache<>(3);

    cache.put(1, "one");
    cache.put(2, "two");
    cache.put(3, "three");
    System.out.println(cache.get(1)); // Output: one
    cache.put(4, "four"); // Evicts key 2
    System.out.println(cache.get(2)); // Output: null
    System.out.println(cache.get(3)); // Output: three
    System.out.println(cache.get(4)); // Output: four
}

}
```

4.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 mappings
self.head = Node(None, None) # Dummy head
self.tail = Node(None, None) # 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._move_to_head(node)
        return node.value
    return -1  # Or raise KeyError, depending on desired behavior

def put(self, key, value):
    if key in self.cache:
        node = self.cache[key]
        node.value = value
        self._move_to_head(node)
    else:
        new_node = Node(key, value)
        self.cache[key] = new_node
        self._add_to_head(new_node)

        if len(self.cache) > self.capacity:
            tail_node = self._remove_tail()
            del self.cache[tail_node.key]

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

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

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

def _remove_tail(self):
  if self.head.next == self.tail:
    return None
  tail_node = self.tail.prev
  self._remove_node(tail_node)
  return tail_node

if name == 'main':
cache = LRUCache(3)
cache.put(1, "one")
cache.put(2, "two")
cache.put(3, "three")
print(cache.get(1)) # Output: one
cache.put(4, "four") # Evicts key 2
print(cache.get(2)) # Output: -1
print(cache.get(3)) # Output: three
print(cache.get(4)) # Output: four
```

4.3 C++实现

```c++

include

template
class LRUCache {
private:
int capacity;
std::unordered_map>::iterator> cache;
std::list> lru_list;

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

V get(K key) {
    auto it = cache.find(key);
    if (it != cache.end()) {
        // Move the accessed element to the front of the list
        lru_list.splice(lru_list.begin(), lru_list, it->second);
        return it->second->second;
    }
    return V{}; // Or throw an exception, or use std::optional (C++17)
}

void put(K key, V 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 {
        // Add the new element to the front of the list and the cache
        lru_list.emplace_front(key, value);
        cache[key] = lru_list.begin();

        // If capacity is exceeded, remove the least recently used element
        if (cache.size() > capacity) {
            cache.erase(lru_list.back().first);
            lru_list.pop_back();
        }
    }
}

};

int main() {
LRUCache cache(3);

cache.put(1, "one");
cache.put(2, "two");
cache.put(3, "three");
std::cout << cache.get(1) << std::endl; // Output: one
cache.put(4, "four"); // Evicts key 2
std::cout << cache.get(2) << std::endl; // Output:  (empty string, default-constructed V)
std::cout << cache.get(3) << std::endl; // Output: three
std::cout << cache.get(4) << std::endl; // Output: four

return 0;

}

```

5. 复杂度分析

get(key)：
- 哈希表查找：O(1) 平均时间复杂度。
- 双向链表移动节点：O(1) 时间复杂度。
- 总时间复杂度：O(1)。
put(key, value)：
- 哈希表查找：O(1) 平均时间复杂度。
- 双向链表插入/移动节点：O(1) 时间复杂度。
- 可能需要移除尾部节点：O(1) 时间复杂度。
- 总时间复杂度：O(1)。
空间复杂度：O(capacity)，因为哈希表和双向链表最多存储capacity个元素。

6. LRU算法的优缺点

优点：

实现相对简单。
对于具有局部性原理的应用场景，缓存命中率较高。
时间复杂度较低，get和put操作均为O(1)。

缺点：

对于循环访问模式（例如，依次访问A、B、C、A、B、C...），LRU算法的性能会退化，因为最近最少使用的元素可能很快会被再次访问。
需要额外的空间来维护双向链表和哈希表。
多线程环境下需要考虑线程安全问题（上述代码示例均未考虑线程安全，实际应用中需要加锁或其他同步机制）。

7. LRU算法的变种和应用

7.1 LRU-K

LRU-K算法是LRU算法的一种改进，它考虑了数据的访问历史，而不仅仅是最近一次访问。LRU-K算法维护一个队列，记录每个数据最近K次访问的时间。当需要淘汰数据时，LRU-K算法会选择最近K次访问时间最早的数据。

7.2 2Q

2Q（Two Queues）算法是另一种LRU算法的变种。它使用两个队列：一个FIFO队列和一个LRU队列。当一个数据第一次被访问时，它会被放入FIFO队列。当FIFO队列中的数据被再次访问时，它会被移到LRU队列。当需要淘汰数据时，2Q算法会优先淘汰FIFO队列中的数据，如果FIFO队列为空，则淘汰LRU队列中的数据。

7.3 应用场景

LRU算法及其变种广泛应用于各种需要缓存的场景：

CPU缓存：用于缓存内存中的数据，提高CPU访问速度。
数据库缓存：用于缓存查询结果，减少数据库访问次数。
Web服务器缓存：用于缓存静态资源（如图片、CSS、JavaScript文件），减轻服务器负载。
CDN（内容分发网络）：用于缓存网站内容，加速用户访问速度。
操作系统页面置换：用于管理内存中的页面，当内存不足时，选择最近最少使用的页面进行置换。
应用程序缓存：例如，图像编辑软件可以缓存最近使用的图像，以便用户快速切换。

8. 总结

LRU算法是一种经典的缓存淘汰策略，它通过维护数据访问顺序来选择最近最少使用的数据进行淘汰。本文详细介绍了LRU算法的原理、实现步骤，并提供了Java、Python和C++三种编程语言的代码示例。

在实际应用中，需要根据具体的场景选择合适的缓存算法。如果数据的访问模式符合局部性原理，LRU算法通常是一个不错的选择。如果数据的访问模式比较复杂，可以考虑使用LRU-K、2Q等变种算法，或者结合其他指标（如访问频率）来设计更复杂的缓存策略。此外，在多线程环境中，还需要考虑缓存的线程安全性，避免并发访问导致的数据不一致问题。

作者：admin

链接：https://hostlocvps.com/2025/03/22/lru%e7%ae%97%e6%b3%95%e5%ae%9e%e7%8e%b0%ef%bc%9ajava-python-c%e4%bb%a3%e7%a0%81%e7%a4%ba%e4%be%8b-%ef%bc%88%e6%a0%b9%e6%8d%ae%e6%96%87%e7%ab%a0%e5%86%85%e5%ae%b9%e9%80%89%e6%8b%a9%e5%af%b9%e5%ba%94/

文章版权归作者所有，未经允许请勿转载。

THE END

Z-Library中文介绍：全球最大电子图书馆（含使用方法）

<<上一篇

Cloudflare WARP常见问题解答：安装、使用、故障排除

下一篇>>

LRU算法实现：Java/Python/C++代码示例 （根据文章内容选择对应语言）

LRU 缓存机制详解与多语言实现（Java/Python/C++）

1. LRU算法原理

2. LRU算法的数据结构选择

3. LRU算法的实现步骤

4. 代码示例

4.1 Java实现

4.2 Python实现

4.3 C++实现

include

include

include

5. 复杂度分析

6. LRU算法的优缺点

7. LRU算法的变种和应用

7.1 LRU-K

7.2 2Q

7.3 应用场景

8. 总结

LRU算法实现：Java/Python/C++代码示例（根据文章内容选择对应语言）