用java自己实现一个LRU
最新回答
风雪不归
2026-10-23 09:40:52
以下是一个基于哈希表和双向链表实现的Java LRU缓存，代码结构清晰，注释详细，便于理解：
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 Node<K, V> head; // 双向链表头节点（哨兵节点） private final Node<K, V> tail; // 双向链表尾节点（哨兵节点） // 双向链表节点定义 private static class Node<K, V> { K key; V value; Node<K, V> prev; Node<K, V> next; Node(K key, V value) { this.key = key; this.value = value; } } public LRUCache(int capacity) { if (capacity <= 0) { throw new IllegalArgumentException("Capacity must be positive"); } this.capacity = capacity; this.map = new HashMap<>(); this.head = new Node<>(null, null); // 哨兵头节点 this.tail = new Node<>(null, null); // 哨兵尾节点 head.next = tail; tail.prev = head; } public V get(K key) { Node<K, V> node = map.get(key); if (node == null) { return null; } // 访问后移动到链表头部（表示最近使用） moveToHead(node); return node.value; } public void put(K key, V value) { Node<K, V> node = map.get(key); if (node != null) { // 更新值并移动到头部 node.value = value; moveToHead(node); } else { // 如果容量已满，删除最久未使用的节点（尾部前一个节点） if (map.size() == capacity) { Node<K, V> tailNode = removeTail(); map.remove(tailNode.key); } // 创建新节点并添加到头部 Node<K, V> newNode = new Node<>(key, value); map.put(key, newNode); addToHead(newNode); } } // 删除尾部节点（最久未使用），返回被删除的节点 private Node<K, V> removeTail() { Node<K, V> node = tail.prev; removeNode(node); return node; } // 将节点移动到链表头部 private void moveToHead(Node<K, V> node) { removeNode(node); addToHead(node); } // 从链表中删除节点 private void removeNode(Node<K, V> node) { node.prev.next = node.next; node.next.prev = node.prev; } // 添加节点到链表头部 private void addToHead(Node<K, V> node) { node.prev = head; node.next = head.next; head.next.prev = node; head.next = node; }}关键点说明：数据结构选择：
哈希表：提供O(1)时间复杂度的查找能力。
双向链表：维护节点访问顺序，支持O(1)时间复杂度的插入和删除。
核心操作：
get操作：若存在则移动到链表头部（标记为最近使用）。
put操作：
若存在则更新值并移动到头部。
若不存在且容量已满，删除链表尾部节点（最久未使用）后再插入新节点。
哨兵节点：
使用head和tail哨兵节点简化边界条件处理，避免空指针异常。
时间复杂度：
所有操作（get/put）均为O(1)时间复杂度。
线程安全：
当前实现非线程安全，如需线程安全需添加同步机制（如ConcurrentHashMap或synchronized）。
此实现完整覆盖了LRU的核心逻辑，代码结构清晰，适合作为学习或基础使用的参考。
热门标签
