最近在做一些数据缓存方面的工作。研究了LRU算法和LFU算法。

• LRU有成熟的O(1)复杂度算法：参考：https://juejin.cn/post/7055600927671058469
• LFU最佳实现方法是O(log n)的。但项目中要求算法高效，所以学习了O(1)复杂度的算法实现：参考： https://tech.ipalfish.com/blog/2020/03/25/lfu/

算法本质上是维护一个如图的数据结构：

• 一个HashMap
• 一个双向链表（链表元素又是一个双向子链表，具有相同访问次数的数据会放在相同的链表中）。
  

此时聪明的你应该想到如何实现了！下面以一个例子说明其原理。为了画图方便。省略了两类指针：

1. HashMap指向子链表元素的指针
2. 双向子链表元素指向双向链表节点的指针

在本文的实现中，初始时只有一个频次为0的链表：

当加入值时，都默认放在这个频次为0的链表中。比如添加a, b, c后。

当获取值时，会把它的频次加1，以b为例，即会把b移动到一个新的链表。

当缓存不足时，将优先淘汰访问频次最小的。可以从head开始查找，将找到的第一个从链表中删除即可。即会把a删除，删除后如图。

无论是加入、获取、淘汰，操作的复杂度都是O(1)的。

package com.iscas.intervention.data.cache;import java.util.HashMap;/*** O(1) 的LFU实现* @author cloudea* @date 2023/03/17*/
public class LFU {/*** 保存数据的双向链表结点*/public  static class LFUListNode {public String key;public Object value;public LFUListNode last;public LFUListNode next;public LFUDoubleListNode master; // 指向所属的频次节点public LFUListNode(String key, Object value) {this.key = key;this.value = value;}}/*** 保存频次的双向链表节点*/public static class LFUDoubleListNode {public int count; // 频次public LFUListNode head ;public LFUListNode tail;public LFUDoubleListNode last;public LFUDoubleListNode next;public LFUDoubleListNode (int count){this.count = count;// 初始化哨兵this.head = new LFUListNode(null, null);this.tail = new LFUListNode(null, null);this.head.next = this.tail;this.tail.last = this.head;}}/*** 频次双向链表*/public static class LFUDoubleList {public LFUDoubleListNode head;public LFUDoubleListNode tail;public LFUDoubleList(){this.head = new LFUDoubleListNode(0);this.tail = new LFUDoubleListNode(0);this.head.next = this.tail;this.tail.last = this.head;}}private HashMap caches = new HashMap<>();private LFUDoubleList counts = new LFUDoubleList();public LFU(){// 初始化访问频次为0的结点LFUDoubleListNode lfuDoubleListNode = new LFUDoubleListNode(0);lfuDoubleListNode.last = counts.head;lfuDoubleListNode.next = counts.tail;counts.head.next = lfuDoubleListNode;counts.tail.last = lfuDoubleListNode;}public void set(String key, Object value){if(caches.containsKey(key)) {// 如果存在，则更新一下value即可caches.get(key).value = value;}else{// 否则，需要放入链表中(放入频率为0的链表)LFUListNode node = new LFUListNode(key, value);node.master = counts.head.next;node.last = node.master.tail.last;node.next = node.master.tail;node.last.next = node;node.next.last = node;caches.put(key, node);}}public Object get(String key){if(caches.containsKey(key)){// 如果存在，直接返回,然后更新频次 （频次加1）LFUListNode node = caches.get(key);LFUDoubleListNode nextMaster = node.master.next;if(nextMaster.count != node.master.count + 1) {// 新建一个master节点LFUDoubleListNode A = node.master;LFUDoubleListNode B = node.master.next;LFUDoubleListNode n = new LFUDoubleListNode(node.master.count + 1);n.last = A;n.next = B;A.next = n;B.last = n;nextMaster = n;}// 把结点从当前master删除node.last.next = node.next;node.next.last = node.last;// 把结点加入到下一个masternode.last = nextMaster.tail.last;node.next = nextMaster.tail;node.last.next = node;node.next.last = node;node.master = nextMaster;// 返回节点值return node.value;}return null;}/*** 删除频次最小的元素*/public Object remove(){if(size() != 0){for(var i = counts.head.next; i != counts.tail; i = i.next){for(var j = i.head.next; j != i.tail; j = j.next){// 删除当前元素j.last.next = j.next;j.next.last = j.last;// 删除当前master(如果没有结点的话)if(j.master.head.next == j.master.tail){if(j.master.count != 0){j.master.last.next = j.master.next;j.master.next.last = j.master.last;}}// 从hashmap中删除caches.remove(j.key);return j.value;}}}return null;}public int size(){return caches.size();}
}