LRU 算法的 O(1) 实现
上一篇我们用单链表实现了 LRU，但判断结点是否存在和删除尾结点都是 O(n) 操作。对于页面置换算法，速度通常是第一指标，我们想到散列表可在 O(1) 时间内找到结点，而双向链表删除尾结点的操作也为 O(1)，如果采用两者组合的数据结构，便可将 LRU 的性能提升到 O(1)。与此同时，从单链表到双向链表加上额外引入的散列结构，存储密度降低为 1/3，或者说空间复杂度是 O(n)，是典型的以空间换时间行为，实际上内存的作用本就如此。在 Java 中，HashMap 是散列表的典型实现，为了突显链表操作，我们直接使用它，仅实现一个简单双链表。
package com.logi.algorithm;
import java.util.HashMap;
/**
* @author LOGI
* @version 1.0
* @date 2019/7/10 16:02
*/
public class LRUWithHashMapAndDoublyLinkedList {
DoublyLinkedListNode head;
DoublyLinkedListNode tail;
HashMap<Integer, DoublyLinkedListNode> map;
int capacity;
int size;
public LRUWithHashMapAndDoublyLinkedList(int capacity) {
this.head = new DoublyLinkedListNode();
this.tail = this.head;
this.map = new HashMap<>();
this.capacity = capacity;
}
public static void main(String[] args) {
LRUWithHashMapAndDoublyLinkedList lru = new LRUWithHashMapAndDoublyLinkedList(2);
lru.put(1, 1);
System.out.println(lru + ", after put(1,1)");
lru.put(2, 2);
System.out.println(lru + ", after put(2,2)");
lru.get(1);
System.out.println(lru + ", after get(1)");
lru.put(3, 3);
System.out.println(lru + ", after put(3,3)");
lru.get(2);
System.out.println(lru + ", after get(2)");
lru.put(4, 4);
System.out.println(lru + ", after put(4,4)");
lru.get(1);
System.out.println(lru + ", after get(1)");
lru.get(3);
System.out.println(lru + ", after get(3)");
lru.get(4);
System.out.println(lru + ", after get(4)");
}
public int get(int key) {
DoublyLinkedListNode current = this.map.get(key);
if (current == null) {
return -1;
} else {
DoublyLinkedListNode save = current;
this.delete(current);
this.insert(save);
return save.value;
}
}
public void put(int key, int value) {
DoublyLinkedListNode current = this.map.get(key);
if (current == null) {
current = new DoublyLinkedListNode(key, value);
if (this.size == this.capacity) {
// map.remove 必须在前，因为如果先删除，tail 就改变了
this.map.remove(this.tail.key);
this.delete(this.tail);
}
this.insert(current);
this.map.put(key, current);
}
}
@Override
public String toString() {
StringBuilder list = new StringBuilder();
DoublyLinkedListNode current = this.head.next;
while (current != null) {
list.append(current.value);
if (current != this.tail) {
list.append("->");
}
current = current.next;
}
return list.toString();
}
/**
* 删除节点
*
* @param current
*/
public void delete(DoublyLinkedListNode current) {
current.prev.next = current.next;
if (current.next != null) {
current.next.prev = current.prev;
} else {
this.tail = current.prev;
this.tail.next = null;
}
this.size--;
}
/**
* 插入到表头
*
* @param current
*/
public void insert(DoublyLinkedListNode current) {
current.prev = this.head;
current.next = this.head.next;
if (this.head.next == null) {
this.tail = current;
this.tail.next = null;
} else {
this.head.next.prev = current;
}
this.head.next = current;
this.size++;
}
}
class DoublyLinkedListNode {
DoublyLinkedListNode prev;
DoublyLinkedListNode next;
int key;
int value;
public DoublyLinkedListNode() {
}
public DoublyLinkedListNode(int key, int value) {
this.key = key;
this.value = value;
}
}LinkedHashMap
对 Java 集合比较熟悉的同学应该知道，LinkedHashMap 本就是 HashMap 加 DoublyLinkedList 的实现，所以我们可以直接使用封装好的数据结构简洁地实现以上操作。
package com.logi.algorithm;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
/**
* @author LOGI
* @version 1.0
* @date 2019/7/10 17:53
*/
public class LRUWithLinkedHashMap {
Map<Integer, Integer> cache;
int capacity;
public LRUWithLinkedHashMap(int capacity) {
this.capacity = capacity;
// 0.75 是数组扩容的触发条件，true 表示将结点以访问顺序排序，默认是插入顺序
this.cache = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true) {
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
// 设置删除年长结点的触发条件为缓存满
return size() > capacity;
}
};
}
public static void main(String[] args) {
// 与之前我们自行实现时的设定不同，在 LinkedHashMap 中，年长结点位于链表头
LRUWithLinkedHashMap lru = new LRUWithLinkedHashMap(2);
lru.put(1, 1);
System.out.println(lru + ", after put(1,1)");
lru.put(2, 2);
System.out.println(lru + ", after put(2,2)");
lru.get(1);
System.out.println(lru + ", after get(1)");
lru.put(3, 3);
System.out.println(lru + ", after put(3,3)");
lru.get(2);
System.out.println(lru + ", after get(2)");
lru.put(4, 4);
System.out.println(lru + ", after put(4,4)");
lru.get(1);
System.out.println(lru + ", after get(1)");
lru.get(3);
System.out.println(lru + ", after get(3)");
lru.get(4);
System.out.println(lru + ", after get(4)");
}
@Override
public String toString() {
StringBuilder list = new StringBuilder();
Iterator<Integer> iterator = this.cache.values().iterator();
while (iterator.hasNext()) {
list.append(iterator.next()).append("->");
}
return list.substring(0, list.length() - 2);
}
public int get(int key) {
// 自动调整顺序，不存在返回 -1
return map.getOrDefault(key, -1);
}
public void put(int key, int value) {
// 自动插入，自动判满删除
cache.put(key, value);
}
}Redis 中的 LRU
Redis 是一个高速缓存数据库，通过将所有数据加载于内存中获得最高读写性能，广泛应用于各种热点业务，如新浪热搜中。
当把 Redis 做 Cache 使用时，由于内存容量限制，需要配置最大内存使用量，如果使用量超过了 maxmemory，就通过 LRU 等策略剔除数据。以下是 Redis 中 LRU 的基本思想。
- 用一个全局时钟作参照
- 对每个 object 初始化和操作时都更新它各自的 lru 时钟
- 随机挑选几个 key，根据 lru 时钟计算 idle 的时间，排序后放入 EvictionPool 中，最终挑选 idle 时间最长的 free。至于为什么随机和只选择 5 个，是出于性能考虑，因为全局排序非常消耗 CPU，而实际应用中没有必要如此精确。
可见，Redis 实现的 LRU 与理论的区别主要在于第 3 点，即内存满时，随机选择 n 个排序，由此也可窥见工业领域中 LRU 的最佳实践。