使用 LinkedList 实现一个高效的缓存系统
使用 LinkedList 实现一个高效的缓存系统通常涉及到实现一个最近最少使用（LRU, Least Recently Used）缓存淘汰算法。LRU 缓存是一种常用的缓存淘汰策略，它会在缓存满时淘汰最长时间未被使用的元素。
以下是使用 LinkedList 和 HashMap 实现 LRU 缓存的步骤：
- 使用
LinkedList存储缓存项的顺序：最近访问的项放在链表头部，最老访问的项放在链表尾部。 - 使用
HashMap存储键和对应节点的映射：这样可以快速地通过键访问到缓存项的节点。
实现步骤：
- 当访问一个缓存项时，如果它在缓存中：
- 将其移动到链表的头部，表示最近被访问。
- 如果缓存项不在缓存中：
- 从链表尾部移除最老的项（如果缓存已满）。
- 在链表头部添加新的缓存项。
- 在
HashMap中添加键和新节点的映射。
示例代码：
import java.util.HashMap;
import java.util.Map;public class LRUCache<K, V> {private final int capacity;private final Map<K, Node<K, V>> map;private final LinkedList<Node<K, V>> list;public LRUCache(int capacity) {this.capacity = capacity;this.map = new HashMap<>();this.list = new LinkedList<>();}public V get(K key) {Node<K, V> node = map.get(key);if (node == null) {return null;}// Move the accessed node to the head of the listlist.remove(node);list.addFirst(node);return node.value;}public void put(K key, V value) {Node<K, V> node = map.get(key);if (node != null) {// Update the value and move to headnode.value = value;list.remove(node);list.addFirst(node);} else {// Create a new node and add to headif (map.size() == capacity) {// Remove the least recently used itemK lastKey = list.getLast().key;map.remove(lastKey);list.removeLast();}Node<K, V> newNode = new Node<>(key, value);list.addFirst(newNode);map.put(key, newNode);}}private static class Node<K, V> {K key;V value;Node<K, V> prev, next;public Node(K key, V value) {this.key = key;this.value = value;}}
}
使用示例：
public class LRUCacheDemo {public static void main(String[] args) {LRUCache<Integer, String> cache = new LRUCache<>(2);cache.put(1, "one");cache.put(2, "two");System.out.println(cache.get(1)); // 输出 "one"cache.put(3, "three"); // 淘汰 "two"System.out.println(cache.get(2)); // 输出 null，因为 "two" 已被淘汰cache.put(4, "four"); // 淘汰 "one"System.out.println(cache.get(1)); // 输出 null}
}
这个 LRUCache 类实现了一个简单的 LRU 缓存系统，它使用 LinkedList 来维护元素的访问顺序，并使用 HashMap 来快速定位元素。当缓存达到容量上限时，它会淘汰掉最老的元素。