本文详解JavaScript中LRU缓存的实现机制，核心结合哈希表与双向链表。通过哈希表实现O(1)查找，双向链表维护访问顺序。文章提供具体代码示例，展示如何设置最大容量、移动节点至头部及淘汰尾部节点，并介绍哨兵节点优化空链表处理。
LRU缓存淘汰算法的构建方式？
LRU（最近最少使用）缓存策略是一种主流机制，其原理在于剔除长期未访问的数据，从而确保缓存内容的高频热度。以下是构建LRU缓存的具体方案：
结合哈希表与双向链表
LRU算法的关键在于高效检索最近最少使用的数据，这依赖于哈希表与双向链表的协同工作。具体而言，利用哈希表记录键值对，借助双向链表追踪访问时序。每次数据被访问，对应节点即移至链表头部；若缓存溢出，则移除链表尾部的节点。
基于哈希表的LRU实现
以下示例展示了利用哈希表构建LRU缓存的过程，设定最大容量为3：
import java.util.HashMap;
import java.util.Map;
class LRUCache<K, V> {
private int capacity;
private Map<K, Node<K,V>> cache;
private Node<K,V> head;
private Node<K,V> tail;
public LRUCache(int capacity) {
this.capacity = capacity;
this.cache = new HashMap<>();
this.head = new Node<>(null, null);
this.tail = new Node<>(null, null);
this.head.next = this.tail;
this.tail.prev = this.head;
}
public V get(K key) {
if (!cache.containsKey(key)) {
return null;
}
Node<K,V> node = cache.get(key);
remove(node);
addFirst(node);
return node.value;
}
public void put(K key, V value) {
if (cache.containsKey(key)) {
Node<K,V> node = cache.get(key);
node.value = value;
remove(node);
addFirst(node);
} else {
if (cache.size() == capacity) {
Node<K,V> node = removeLast();
cache.remove(node.key);
}
Node<K,V> node = new Node<>(key, value);
cache.put(key, node);
addFirst(node);
}
}
private void remove(Node<K,V> node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void addFirst(Node<K,V> node) {
node.next = head.next;
node.prev = head;
head.next.prev = node;
head.next = node;
}
private Node<K,V> removeLast() {
Node<K,V> node = tail.prev;
remove(node);
return node;
}
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;
}
}
}本例中，哈希表cache用于保存键值对，双向链表head与tail分别标识链表头尾以维持访问次序。每次访问操作会将节点移至头部，缓存满载时则移除尾部节点。
为简化逻辑，链表头尾分别设置了哨兵节点head与tail，从而避免处理空链表边界情况。
以下示例展示了利用双向链表构建LRU缓存的过程，设定最大容量为3：
import java.util.HashMap;
import java.util.Map;
class LRUCache<K, V> {
private int capacity;
private Map<K, Node<K,V>> cache;
private Node<K,V> head;
private Node<K,V> tail;
public LRUCache(int capacity) {
this.capacity = capacity;
this.cache = new HashMap<>();
this.head = new Node<>(null, null);
this.tail = new Node<>(null, null);
this.head.next = this.tail;
this.tail.prev = this.head;
}
public V get(K key) {
if (!cache.containsKey(key)) {
return null;
}
Node<K,V> node = cache.get(key);
remove(node);
addFirst(node);
return node.value;
}
public void put(K key, V value) {
if (cache.containsKey(key)) {
Node<K,V> node = cache.get(key);
node.value = value;
remove(node);
addFirst(node);
} else {
if (cache.size() == capacity) {
Node<K,V> node = removeLast();
cache.remove(node.key);
}
Node<K,V> node = new Node<>(key, value);
cache.put(key, node);
addFirst(node);
}
}
private void remove(Node<K,V> node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void addFirst(Node<K,V> node) {
node.next = head.next;
node.prev = head;
head.next.prev = node;
head.next = node;
}
private Node<K,V> removeLast() {
Node<K,V> node = tail.prev;
remove(node);
return node;
}
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;
}
}
}本例中，哈希表cache用于保存键值对，双向链表head与tail分别标识链表头尾以维持访问次序。每次访问操作会将节点移至头部，缓存满载时则移除尾部节点。
为简化逻辑，链表头尾分别设置了哨兵节点head与tail，从而避免处理空链表边界情况。
至此，关于JavaScript实现LRU缓存淘汰算法的介绍结束。如需了解更多JavaScript LRU相关内容，请查阅本站往期文章或继续浏览后续文章，感谢支持！