从Redis看淘汰算法
虽然「Redis」有自己的过期策略来删除过期的数据（惰性删除和抽样删除）。这其中具体的删除原理本章不做详细介绍。但是也会存在Redis删不过来导致内存占满的情况。所以「Redis」使用了一些淘汰算法来处理这些来不及删除的数据。
下面我们来说说「LRU」淘汰算法。
LRU算法
定义
「LRU」算法中，需要有一个链表来存放数据，当某个元素被访问时，这个元素会被移动到表头。当空间满了，会剔除掉链表末尾的元素。
其核心就是保留最近使用的元素。
代码实现
我们来看看代码实现：
代码语言：javascript复制public class LRULinkedHashMap<K, V> extends LinkedHashMap<K, V> {
private int capacity;
LRULinkedHashMap(int capacity) {
// 初始大小，0.75是装载因子，true是表示按照访问时间排序
super(capacity, 0.75f, true);
//传入指定的缓存最大容量
this.capacity = capacity;
}
/**
* 实现LRU的关键方法，如果map里面的元素个数大于了缓存最大容量，则删除链表的顶端元素
*/
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > capacity;
}
}
我们来写个单元测试测试下：
代码语言：javascript复制@org.junit.Test
public void test() {
LRULinkedHashMap<String, Integer> map = new LRULinkedHashMap<>(4);
map.put("A", 1);
map.put("B", 2);
map.put("C", 3);
System.out.println(map);
map.get("B");
System.out.println(map);
map.put("D",4);
map.put("E",5);
System.out.println(map);
}
测试结果：
代码语言：javascript复制{A=1, B=2, C=3}
{A=1, C=3, B=2}
{C=3, B=2, D=4, E=5}
利用LinkedHashMap的特性：访问的数据会排到最前面。
我们来图解上面代码：
❝（1）我们创建一个容量为「4」的
LinkedHashMap，并put初始值：A ->B -> C （2）查询值「key」为「B」的值，「B」会重新排列到最前面。顺序为：A ->C -> B （3）put新值「D」，顺序为：A ->C ->B ->D （4）put新值「E」，最末尾的值「A」被淘汰。顺序为：C ->B ->D ->E ❞
LFU算法
定义
在「Redis」 4.0中引入了一个新的淘汰算法LFU，可以说是LRU的进阶版。
LFU算法规定的是按最近访问的频率进行淘汰，与LRU算法相比，LFU更精准的表示了一个「key」被访问的热度。
为甚么Redis要引入LFU算法呢？
如果一个「key」长时间没有没访问，只是刚刚被用户偶尔访问了一下。在LRU算法下，这个「key」是不容易被淘汰的。但如果是LFU算法，会追踪最近一段时间的访问频率。就是说在LFU算法下，只是最近偶尔被访问一次是不足以说明这个「key」是热点数据。
算法示意图：
如图，算法将访问次数最高的放在最前面，容量满后会删除末尾的元素。
代码实现
代码语言：javascript复制public class LFUCache {
private Map<Integer, ListNode> map;
/**
* 访问次数哈希表，使用 ListNode[] 也可以，不过要占用很多空间
*/
private Map<Integer, DoubleLinkedList> frequentMap;
/**
* 外部传入的容量大小
*/
private Integer capacity;
/**
* 全局最高访问次数，删除最少使用访问次数的结点时会用到
*/
private Integer minFrequent = 1;
public LFUCache(int capacity) {
map = new HashMap<Integer, ListNode>(capacity);
frequentMap = new HashMap<Integer, DoubleLinkedList>();
this.capacity = capacity;
}
/**
* get 一次操作，访问次数就增加 1；
* 从原来的链表调整到访问次数更高的链表的表头
*
* @param key
* @return
*/
public int get(int key) {
// 测试测出来的，capacity 可能传 0
if (capacity == 0) {
return -1;
}
if (map.containsKey(key)) {
// 获得结点类
ListNode listNode = removeListNode(key);
// 挂接到新的访问次数的双向链表的头部
int frequent = listNode.frequent;
addListNode2Head(frequent, listNode);
return listNode.value;
} else {
return -1;
}
}
/**
* @param key
* @param value
*/
public void put(int key, int value) {
if (capacity == 0) {
return;
}
// 如果 key 存在，就更新访问次数 1，更新值
if (map.containsKey(key)) {
ListNode listNode = removeListNode(key);
// 更新 value
listNode.value = value;
int frequent = listNode.frequent;
addListNode2Head(frequent, listNode);
return;
}
// 如果 key 不存在
// 1、如果满了，先删除访问次数最小的的末尾结点，再删除 map 里对应的 key
if (map.size() == capacity) {
// 1、从双链表里删除结点
DoubleLinkedList doubleLinkedList = frequentMap.get(minFrequent);
ListNode removeNode = doubleLinkedList.removeTail();
// 2、删除 map 里对应的 key
map.remove(removeNode.key);
}
// 2、再创建新结点放在访问次数为 1 的双向链表的前面
ListNode newListNode = new ListNode(key, value);
addListNode2Head(1, newListNode);
map.put(key, newListNode);
// 【注意】因为这个结点是刚刚创建的，最少访问次数一定为 1
this.minFrequent = 1;
}
// 以下部分主要是结点类和双向链表的操作
/**
* 结点类，是双向链表的组成部分
*/
private class ListNode {
private int key;
private int value;
private int frequent = 1;
private ListNode pre;
private ListNode next;
public ListNode() {
}
public ListNode(int key, int value) {
this.key = key;
this.value = value;
}
}
/**
* 双向链表
*/
private class DoubleLinkedList {
/**
* 虚拟头结点，它无前驱结点
*/
private ListNode dummyHead;
/**
* 虚拟尾结点，它无后继结点
*/
private ListNode dummyTail;
/**
* 当前双向链表的有效结点数
*/
private int count;
public DoubleLinkedList() {
// 虚拟头尾结点赋值多少无所谓
this.dummyHead = new ListNode(-1, -1);
this.dummyTail = new ListNode(-2, -2);
dummyHead.next = dummyTail;
dummyTail.pre = dummyHead;
count = 0;
}
/**
* 把一个结点类添加到双向链表的开头（头部是最新使用数据）
*
* @param addNode
*/
public void addNode2Head(ListNode addNode) {
ListNode oldHead = dummyHead.next;
// 两侧结点指向它
dummyHead.next = addNode;
oldHead.pre = addNode;
// 它的前驱和后继指向两侧结点
addNode.pre = dummyHead;
addNode.next = oldHead;
count ;
}
/**
* 把双向链表的末尾结点删除（尾部是最旧的数据，在缓存满的时候淘汰）
*
* @return
*/
public ListNode removeTail() {
ListNode oldTail = dummyTail.pre;
ListNode newTail = oldTail.pre;
// 两侧结点建立连接
newTail.next = dummyTail;
dummyTail.pre = newTail;
// 它的两个属性切断连接
oldTail.pre = null;
oldTail.next = null;
// 重要：删除一个结点，当前双向链表的结点个数少 1
count--;
return oldTail;
}
}
/**
* 将原来访问次数的结点，从双向链表里脱离出来
*
* @param key
* @return
*/
private ListNode removeListNode(int key) {
// 获得结点类
ListNode deleteNode = map.get(key);
ListNode preNode = deleteNode.pre;
ListNode nextNode = deleteNode.next;
// 两侧结点建立连接
preNode.next = nextNode;
nextNode.pre = preNode;
// 删除去原来两侧结点的连接
deleteNode.pre = null;
deleteNode.next = null;
// 维护双链表结点数
frequentMap.get(deleteNode.frequent).count--;
// 【注意】维护 minFrequent
// 如果当前结点正好在最小访问次数的链表上，并且移除以后结点数为 0，最小访问次数需要加 1
if (deleteNode.frequent == minFrequent && frequentMap.get(deleteNode.frequent).count == 0) {
minFrequent ;
}
// 访问次数加 1
deleteNode.frequent ;
return deleteNode;
}
/**
* 把结点放在对应访问次数的双向链表的头部
*
* @param frequent
* @param addNode
*/
private void addListNode2Head(int frequent, ListNode addNode) {
DoubleLinkedList doubleLinkedList;
// 如果不存在，就初始化
if (frequentMap.containsKey(frequent)) {
doubleLinkedList = frequentMap.get(frequent);
} else {
doubleLinkedList = new DoubleLinkedList();
}
// 添加到 DoubleLinkedList 的表头
doubleLinkedList.addNode2Head(addNode);
frequentMap.put(frequent, doubleLinkedList);
}
}
测试代码：
代码语言：javascript复制@Test
public void test() {
LFUCache cache = new LFUCache(3);
//tail -> head
// ①[1,2,3]
cache.put(1, 1);
cache.put(2, 2);
cache.put(3, 3);
// ②[2,3,1]
int i = cache.get(1);
int i1 = cache.get(1);
// ③[3,2,1]
cache.get(2);
cache.put(4,4);
// ④[4,1,2]
System.out.println(cache.map.keySet());
}
运行结果：
我们来分析下：
❝（1）设容量为「3」，最开始
put值，「map」 （取的「key」）为[1，2，3]，初始每个元素访问计数为1； （2）get获取两次「1」，「1」的计数为1 2=3次，map为[2，3，1]； （3）get获取「2」一次，「2」的计数为1 1=2次，map为[3，2，1]； （4）put值4，由于map容量达到上限，访问次数最少的「1」被淘汰。由于「4」的计数为1次，「4」排到最末尾。map值为[4，1，2]。 ❞
总结
由上面可知。LRU算法和LFU算法有各自的特点，我们应该根据实际业务使用情况去使用。
