一、算法概述
在前面学习Caffine的源码中顺便又学习了下LRU淘汰策略与LFU淘汰策略，LRU与LFU这两种淘汰算法在平时的常工作中也经常的被使用，这里先介绍下LRU与LFU的概念：
- LRU：最近最少使用(最长时间)淘汰算法（Least Recently Used）。LRU是淘汰最长时间没有被使用的数据。
- LFU：最不经常使用(最少次)淘汰算法（Least Frequently Used）。LFU是淘汰一段时间内，使用次数最少的数据。
简单来看LRU关键针对于时间顺序，而LFU则是针对于使用频率。若LFU存储结构中频率最小的数据有多个，则淘汰最久未使用的一个。
二、代码实现
在网上看到很多种LRU和LFU的实现实现方式，本着通俗易懂这里选择了两种较为简单的方式来实现LRU和LFU
LRU
首先我们来分析一下LRU算法，通过概述我们知道LRU是最长时间没有被使用的元素被淘汰。因此我们就需要维护一个时间顺序，以区分最近使用的和久未使用的数据，当容量满了之后要删除最久未使用的那个元素腾位置。其次我们还需要让他的插入和获取时间复杂度是O(1)。
基于第一点需要有时间顺序我们可以采用一个双向链表的结构每次插入都向后插入，维护一个插入的时间顺序。并且采用双向链表的结构可以让我们删除头部节点也就是最早插入的元素并且也可以让元素插入到链表尾部使其成为热点数据，正符合了LRU的设计。基于第二点要让插入和获取的时间复杂度都趋近于O(1)哈希表是最好的选择。当然结合这两种结构java已经为我们提供了LinkedHashMap不过这里我们选择自己实现以下，以加深印象。
//LRU:最近最少使用 FIFO
public class LRUCache {
//使用哈希表让获取的时间复杂度变成O(1)
private HashMap<Integer, Node> cache;
//使用双向链表保证存储元素的顺序，从而保证时间顺序
private DoubleList doubleList;
//定义容量
int capacity;
public LRUCache(int capacity){
this.cache=new HashMap<>();
this.doubleList=new DoubleList();
this.capacity=capacity;
}
//设置当前key为热点key，那就需要让从双向链表删除，并重新加入双向链表
public void makeRecently(int key){
Node node = cache.get(key);
//先从链表中删除
doubleList.remove(node);
//然后插入链表尾部
doubleList.addLast(node);
}
//将当前的key 和value添加到链表尾
public void addRecently(int key,int value){
Node node=new Node(key,value);
//将其设置为热点key
doubleList.addLast(node);
//更新/添加map中的值,替换成新节点
cache.put(key,node);
}
public void removeKey(int key){
Node node = cache.get(key);
//从链表中把老的节点移除
doubleList.remove(node);
}
public int get(int key){
if (!cache.containsKey(key)){
return -1;
}
//访问了就将当前key设置为热点key
makeRecently(key);
return cache.get(key).value;
}
/* 删除最久未使用的元素 */
private void removeLeastRecently() {
// 链表头部的第一个元素就是最久未使用的
Node deletedNode = doubleList.removeFirst();
// 同时别忘了从 map 中删除它的 key
int deletedKey = deletedNode.key;
cache.remove(deletedKey);
}
public void put(int key,int value){
//当前这个key存在需要更新
if (cache.containsKey(key)){
//移除老的节点
removeKey(key);
//更新，让其成为热点key，并且更新值
addRecently(key,value);
return;
}
//容量满了移除最少使用的数据
if (capacity==cache.size()){
removeLeastRecently();
}
//添加成热点数据
addRecently(key,value);
}
public class Node{
private int key,value;
private Node pre;
private Node next;
public Node(int key,int value){
this.key=key;
this.value=value;
}
}
class DoubleList{
//定义头尾节点
private Node head,tail;
private int size;
public DoubleList(){
head=new Node(-1,-1);
tail=new Node(-1,-1);
head.next=tail;
tail.pre=head;
size=0;
}
//我们通过双向链表在尾部添加保持新鲜度
public void addLast(Node node){
node.pre = tail.pre;
node.next=tail;
tail.pre.next=node;
tail.pre=node;
size++;
}
public void remove(Node node){
node.pre.next=node.next;
node.next.pre=node.pre;
size--;
}
//每次在尾部添加，那么就证明头节点是最先添加的
public Node removeFirst(){
if (head.next==tail){
return null;
}
Node node=head.next;
remove(node);
return node;
}
public int getSize(){
return size;
}
}
}
LFU
通过LFU的概述我们得知LFU是淘汰是淘汰使用频率最小的元素，如果有多个使用频率相同的元素那么则淘汰插入时间最久的元素。我们来分析一下它。
第一点经过上面LRU的分析我们还可以采用一个哈希表的结构来存储key和value来保证O(1)时间复杂度的插入和获取顺序。
第二点因为LFU是针对频率的淘汰算法这里我们想要对key的频率进行计数因此还可以采用一个哈希表来存储key和频率的一个映射，以获取某个key的频率(freq)。
第三点接下来想一下我们要淘汰最小频率的key时要做什么？首先我们想要知道这个最小频率因此我们可以采用一个变量来维护最小频率，其次拿到最小频率怎么知道最小频率对应有哪些key呢？因此我们还需要维护一张freq对应key的哈希表，但是在这里可能某个频率对应不只一个key而且在概念种提到过当有多个key时要删除插入时间最久的一个元素，因此我们可以用链表的结构来存储freq-key这张表的值。但是实际上当进行更新频率时我们需要删除freq-key表中原频率的对应key链表下的某个key时链表不能快速的帮我们找到定位，因此我们最终选用LinkedHashSet结构来存储freq-key表的值。
//LFU:最小使用频率
public class LFUCache {
//用来存储key和对应的value
private HashMap<Integer, Integer> keyToVal;
//用来存储key到freq，从而快速的找到key到频率的映射,例如增加key的频率
private HashMap<Integer, Integer> keyToFreq;
//用来存储freq到key的映射，freq 1:N key
private HashMap<Integer, LinkedHashSet<Integer>> freqToKey;
//记录最小频率从而快速操作最小频率
private int minFreq;
// 记录 LFU 缓存的最大容量
int cap;
public LFUCache(int cap){
this.cap=cap;
this.keyToVal=new HashMap<>();
this.keyToFreq=new HashMap<>();
this.freqToKey=new HashMap<>();
this.minFreq=0;
}
int get(int key) {
if (!keyToVal.containsKey(key)){
return -1;
}
// 增加 key 对应的 freq
increaseFreq(key);
return keyToVal.get(key);
}
//增加key的频率
private void increaseFreq(int key) {
//先从key-freq表中获取freq
int freq = keyToFreq.get(key);
//更新key-freq表中freq值
keyToFreq.put(key, freq+1);
//从freq-key表中把key删除
LinkedHashSet<Integer> list = freqToKey.get(freq);
list.remove(key);
//如果某个频率对应的key表空了，那么也要删除对应的freq
if (list.isEmpty()){
freqToKey.remove(freq);
// 如果这个 freq 恰好是 minFreq，更新 minFreq
if (freq == this.minFreq) {
this.minFreq++;
}
}
//将这个key放到新freq中
freqToKey.putIfAbsent(freq+1,new LinkedHashSet<>());
freqToKey.get(freq+1).add(key);
}
void put(int key, int value) {
//校验
if (cap<=0){
return ;
}
//如果包含则需要更新值
if (keyToVal.containsKey(key)){
keyToVal.put(key,value);
//并将对应的key频率增加
increaseFreq(key);
return;
}
//如果不包含则需要新增
//先判断容量是否满了，满了则需要淘汰
if (keyToVal.size()>=cap){
removeMinFreqKey();
}
//淘汰后插入新值
keyToVal.put(key,value);
//将key-freq设置为1
keyToFreq.put(key,1);
//将freq-key添加进去
freqToKey.putIfAbsent(1,new LinkedHashSet<Integer>());
freqToKey.get(1).add(key);
System.out.println(freqToKey.get(1).size());
//将最小频率设置为1
minFreq=1;
}
//删除使用频率最小的key
private void removeMinFreqKey() {
//找到最小频率的key列表
LinkedHashSet<Integer> list = freqToKey.get(minFreq);
//从列表中删除最先插入的key
Integer key = list.iterator().next();
list.remove(key);
//如果某个频率对应的key表空了，那么也要删除对应的freq
if (list.isEmpty()){
freqToKey.remove(minFreq);
//这里无需判断调整频率，因为put方法最终都会将minFreq设置为1
}
//最终从key-value表删除key
keyToVal.remove(key);
//从key-freq表中删除key
keyToFreq.remove(key);
}
}