LRU（Least Recently Used，最近最少使用）是一种经典的缓存替换算法，用于在缓存满时决定哪一个缓存项应该被替换。LRU算法基于这样的假设：最近使用过的数据在未来也更有可能被再次使用，而很久没有使用的数据在未来被使用的可能性较小。
一、基本原理
LRU算法的核心思想是：每次数据被访问时，将其标记为最近使用的。当缓存满时，替换掉最近最少使用的数据。具体来说，LRU算法维护一个数据结构，用于记录数据的使用顺序，并在每次访问时更新这个顺序。
二、实现方法
实现LRU算法通常有以下几种方法：
-
链表（Linked List）：
- 使用双向链表来维护缓存数据的顺序。
- 每次访问数据时，将该数据移动到链表头部。
- 当缓存满时，移除链表尾部的数据。
-
哈希表+双向链表（HashMap + Doubly Linked List）：
- 使用哈希表来快速查找数据。
- 使用双向链表来维护数据的使用顺序。
- 每次访问数据时，将该数据移动到链表头部。
- 当缓存满时，移除链表尾部的数据。
三、代码实现
1.使用链表实现LRU
使用链表实现LRU的基本思路是维护一个双向链表，其中每个节点表示一个缓存项。链表头部表示最近使用的缓存项，链表尾部表示最久未使用的缓存项。当缓存满时，移除链表尾部的节点。
java">import java.util.LinkedList;class LRUCache {private final int capacity;private final LinkedList<Integer> cache;public LRUCache(int capacity) {this.capacity = capacity;this.cache = new LinkedList<>();}public int get(int key) {if (!cache.contains(key)) {return -1;}cache.remove((Integer) key);cache.addFirst(key);return key;}public void put(int key) {if (cache.contains(key)) {cache.remove((Integer) key);} else if (cache.size() >= capacity) {cache.removeLast();}cache.addFirst(key);}public static void main(String[] args) {LRUCache cache = new LRUCache(2);cache.put(1);cache.put(2);System.out.println(cache.get(1)); // 返回 1cache.put(3); // 该操作会使得关键字 2 作废System.out.println(cache.get(2)); // 返回 -1 (未找到)cache.put(4); // 该操作会使得关键字 1 作废System.out.println(cache.get(1)); // 返回 -1 (未找到)System.out.println(cache.get(3)); // 返回 3System.out.println(cache.get(4)); // 返回 4}
}2. 使用哈希表和双向链表实现LRU
使用哈希表和双向链表的组合实现LRU，可以在O(1)时间复杂度内完成查找、插入和删除操作。哈希表用于快速查找缓存项，双向链表用于维护缓存项的使用顺序。
java">import java.util.HashMap;class LRUCache {private final int capacity;private final HashMap<Integer, Node> map;private final DoublyLinkedList cache;public LRUCache(int capacity) {this.capacity = capacity;this.map = new HashMap<>();this.cache = new DoublyLinkedList();}public int get(int key) {if (!map.containsKey(key)) {return -1;}Node node = map.get(key);cache.moveToHead(node);return node.value;}public void put(int key, int value) {if (map.containsKey(key)) {Node node = map.get(key);node.value = value;cache.moveToHead(node);} else {if (map.size() >= capacity) {Node tail = cache.removeTail();map.remove(tail.key);}Node newNode = new Node(key, value);cache.addToHead(newNode);map.put(key, newNode);}}private static class Node {int key;int value;Node prev;Node next;Node(int key, int value) {this.key = key;this.value = value;}}private static class DoublyLinkedList {private final Node head;private final Node tail;DoublyLinkedList() {head = new Node(0, 0);tail = new Node(0, 0);head.next = tail;tail.prev = head;}void addToHead(Node node) {node.next = head.next;node.prev = head;head.next.prev = node;head.next = node;}void removeNode(Node node) {node.prev.next = node.next;node.next.prev = node.prev;}void moveToHead(Node node) {removeNode(node);addToHead(node);}Node removeTail() {Node res = tail.prev;removeNode(res);return res;}}public static void main(String[] args) {LRUCache cache = new LRUCache(2);cache.put(1, 1);cache.put(2, 2);System.out.println(cache.get(1)); // 返回 1cache.put(3, 3); // 该操作会使得关键字 2 作废System.out.println(cache.get(2)); // 返回 -1 (未找到)cache.put(4, 4); // 该操作会使得关键字 1 作废System.out.println(cache.get(1)); // 返回 -1 (未找到)System.out.println(cache.get(3)); // 返回 3System.out.println(cache.get(4)); // 返回 4}
}四、优缺点
优点：
缺点：
- 空间开销：需要额外的空间来维护哈希表和双向链表。
- 不适用于所有场景：LRU算法假设最近使用的数据在未来也更有可能被使用，但在某些场景下，这一假设可能不成立。
五、应用场景
LRU算法广泛应用于各种需要缓存机制的场景，包括但不限于：
- 操作系统的页面置换：操作系统在内存管理中使用LRU算法来决定哪一页应该被换出。
- 数据库缓存：数据库系统使用LRU算法来管理缓存，以提高查询性能。
- Web缓存：Web服务器和浏览器使用LRU算法来缓存网页和资源，以提高访问速度。
六、总结
LRU（Least Recently Used）是一种经典的缓存替换算法，通过维护数据的使用顺序，在缓存满时替换掉最近最少使用的数据。常见的实现方法包括使用哈希表和双向链表的组合。LRU算法具有高效的缓存替换能力和简单易实现的特点，但也存在一定的空间开销。通过合理地选择和实现LRU算法，可以有效地提高系统的缓存命中率和性能。
