如何做到LRU缓存文件取代优化算法?
LRU（Least Recently Used）缓存文件取代优化算法是一种常见的缓存文件取代对策，它核心内容是优先选择取代最近最少使用的缓存文件，以确保缓存文件中数据始终都是最受欢迎的。以下是一些关于如何做到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，那样就可以不用在编码中解决单链表为空的情况。