LFU 算法原理：
LFU算法的淘汰策略是Least Frequently Used，也就是每次淘汰那些使用次数最少的数据（最早最少使用）。
LRU算法的核心数据结构是使用哈希链表LinkedHashMap，首先借助链表的有序性使得链表元素维持插入顺序，同时借助哈希映射的快速访问能力使得我们可以在O(1)时间访问链表的任意元素。（使用HashMap + LinkedList）
LFU 算法相当于是把数据按照访问频次进行排序，而且还有一种情况，如果多个数据拥有相同的访问频次，我们就得删除最早插入的那个数据。也就是说 LFU 算法是淘汰访问频次最低的数据，如果访问频次最低的数据有多条，需要淘汰最旧的数据。
LFU 算法实现：
定义Node节点：
Node主要包含了key和value，因为LFU的主要实现思想是比较访问的次数，如果在次数相同的情况下需要比较节点的时间，越早放入的越快被淘汰，因此我们需要在Node节点上加入time和count的属性，分别用来记录节点的访问的时间和访问次数。
其他的版本实现方式里有新加个内部类来记录 key的count和time，但是我觉得不够方便，还得单独维护一个map，成本有点大。
还有一点注意的是这里实现了comparable接口，覆写了compare方法，这里 的主要作用就是在排序的时候需要用到，在compare方法里面我们首先比较节点的访问次数，在访问次数相同的情况下比较节点的访问时间，这里是为了 在排序方法里面通过比较key来选择淘汰的key
@Data static class Node implements Comparable<Node> { // 键： private Object key; // 值： private Object value; // 访问时间： private long time; // 访问次数： private int count; // 实现Comparable接口，重写compareTo方法： // 调用者 < 参数元素 返回 -1 // 调用者 = 参数元素 返回 0 // 调用者 > 参数元素 返回 1 // 总结：如果返回负数，第一个参数放前面 @Override public int compareTo(Node o) { // compare方法： // 第一个参数 < 第二个参数 返回 -1 // 第二个参数 = 第二个参数 返回 0 // 第三个参数 > 第二个参数 返回 1 int compare = Integer.compare(this.count, o.count); // 在数目相同的情况下，比较访问时间： if (0 == compare) { return Long.compare(this.time, o.time); } return compare; } }
为了实现算法的相对简单，这里使用了int类型作为value值，使用frequency记录访问的频次：
// Node节点，主要维护了Key，value，frequency 三个关键信息 static class Node { // 键： private int key; // 值： private int value; // 访问频率： private int frequency; private Node pre; private Node next; public Node() { this(-1, -1, 0); } public Node(int key, int value, int frequency) { this.key = key; this.value = value; this.frequency = frequency; } }
定义双向链表结构：
自动实现了双向链表，也可以使用JDK自带的LinkedList作为这个DoubleLinkedNode的实现替换。
// 带有头结点和尾节点的双向链表，方便头部插入和尾部获取 static class DoubleLinkedNode { private Node head; private Node tail; // 维护了双向链表的长度： private int size; public DoubleLinkedNode() { head = new Node(); tail = new Node(); head.next = tail; tail.pre = head; size = 0; } // 头插： public void insertHead(Node node) { node.pre = head; node.next = head.next; head.next.pre = node; head.next = node; size++; } // 移除节点： public void remove(Node node) { node.pre.next = node.next; node.next.pre = node.pre; size--; } // 获取链表中的第一个节点： public Node getHead() { return head.next; } // 获取链表中的最后一个节点： public Node getTail() { return tail.pre; } }
Map 结构：
在LFUCache中维护了两个HashMap结构，分别存放Node（keyMap），以及DoubleLinkedNode（freqMap）。
1.keyMap：
keyMap用于存放Node节点，通过keyMap进行查询节点，由于使用的是HashMap保证了查询的时间复杂度在O(1)的时间复杂度水平。
private HashMap<Integer, Node> keyMap = new HashMap<>();
2.freqMap：
freqMap用于存放DoubleLinkedNode链表，记录的是双向链表，维护了当前访问频次下的Node节点信息。
private HashMap<Integer, DoubleLinkedNode> freqMap = new HashMap<>();
其他属性：
// 缓存容量： private int capacity; // 最小频率： private int minFreq; // 构造方法： public LFUCache(int capacity) { this.capacity = capacity; this.minFreq = 0; }
接下来实现LFU中最核心的两个方法：put和get方法：
get方法的核心就在于访问了Key之后，被访问的Node节点的更新策略是如何实现的。
public int get(int key) { // 先尝试从索引Map中查要获取的Key： Node node = keyMap.get(key); if (node == null) { return -1; } // 获取成功之后，需要更新对应Node中的frequency信息 // 分别获取节点的原始frequency信息和所在的DoubleLinkedNode链表 int freq = node.frequency; DoubleLinkedNode oldFreq = freqMap.get(freq); // 从原始的DoubleLinkedNode链表中移除这个节点元素： oldFreq.remove(node); // 如果原始DoubleLinkedNode链表为空，就从链表Map中移除这个链表（节约内存空间） if (oldFreq.size == 0) { freqMap.remove(freq); // 如果被移除的DoubleLinkedNode链表维护的频率是最小的访问频率节点， // 则更新一下最小访问频率 if (minFreq == freq) { minFreq++; } } // 更新被访问节点的信息： node.frequency = freq + 1; // 获取更新后新的访问频次链表DoubleLinkedNode： DoubleLinkedNode newFreq = freqMap.getOrDefault(freq + 1, new DoubleLinkedNode()); // 插入到链表中： newFreq.insertHead(node); // 在频次Map中重新put回去： freqMap.put(freq + 1, newFreq); // 返回获取的缓存值： return node.value; }
put方法的核心就在于向Cache中放入了新数据，如何实现旧数据的一个淘汰。
public void put(int key, int value) { // 如果缓存容量小于等于0，表示无法缓存，直接结束（不进行缓存操作） if (0 >= capacity) { return; } // put向集合中添加元素前，先从索引Map中进行获取 Node node = keyMap.get(key); // 获取失败，索引Map中没有对应的Key： if (null == node) { // 判断当前缓存容量是否已满： if (capacity == keyMap.size()) { // 当容量满时，需要移除最小访问频率中最久为访问的那个Node元素 // 为什么时最后一个？ // 在新Node在插入队列时使用的头插法，最久且访问频率最低则是链表尾的最后一个元素 DoubleLinkedNode minFreqList = freqMap.get(minFreq); Node tail = minFreqList.getTail(); // 因此，移除访问频率最低的链表中最后一个（最久未被访问）Node元素： minFreqList.remove(tail); if (minFreqList.size == 0) { freqMap.remove(minFreq); } keyMap.remove(tail.key); } // 如果没有达到缓存最大容量，则直接访问缓存中，访问频率设置为1： node = new Node(key, value, 1); keyMap.put(key, node); DoubleLinkedNode newFreq = freqMap.getOrDefault(1, new DoubleLinkedNode()); newFreq.insertHead(node); freqMap.put(1, newFreq); minFreq = 1; } // 在新增Node元素时，已经在索引Map中存在一个相同的Key： else { node.value = value; int freq = node.frequency; DoubleLinkedNode oldFreq = freqMap.get(freq); oldFreq.remove(node); if (oldFreq.size == 0) { freqMap.remove(freq); if (minFreq == freq) { minFreq++; } } // 重复新增时，也要把该Key对应的Node的frequency增加： node.frequency = freq + 1; DoubleLinkedNode newFreq = freqMap.getOrDefault(freq + 1, new DoubleLinkedNode()); newFreq.insertHead(node); freqMap.put(freq + 1, newFreq); } }
OK，所有的汇总代码：
public class LFUCache { static class Node { private int key; private int value; private int frequency; private Node pre; private Node next; public Node() { this(-1, -1, 0); } public Node(int key, int value, int frequency) { this.key = key; this.value = value; this.frequency = frequency; } } static class DoubleLinkedNode { private Node head; private Node tail; private int size; public DoubleLinkedNode() { head = new Node(); tail = new Node(); head.next = tail; tail.pre = head; size = 0; } public void insertHead(Node node) { node.pre = head; node.next = head.next; head.next.pre = node; head.next = node; size++; } public void remove(Node node) { node.pre.next = node.next; node.next.pre = node.pre; size--; } public Node getHead() { return head.next; } public Node getTail() { return tail.pre; } } private HashMap<Integer, Node> keyMap = new HashMap<>(); private HashMap<Integer, DoubleLinkedNode> freqMap = new HashMap<>(); private int capacity; private int minFreq; public LFUCache(int capacity) { this.capacity = capacity; this.minFreq = 0; } public int get(int key) { Node node = keyMap.get(key); if (node == null) { return -1; } int freq = node.frequency; DoubleLinkedNode oldFreq = freqMap.get(freq); oldFreq.remove(node); if (oldFreq.size == 0) { freqMap.remove(freq); if (minFreq == freq) { minFreq++; } } node.frequency = freq + 1; DoubleLinkedNode newFreq = freqMap.getOrDefault(freq + 1, new DoubleLinkedNode()); newFreq.insertHead(node); freqMap.put(freq + 1, newFreq); return node.value; } public void put(int key, int value) { if (0 >= capacity) { return; } Node node = keyMap.get(key); if (null == node) { if (capacity == keyMap.size()) { DoubleLinkedNode minFreqList = freqMap.get(minFreq); Node tail = minFreqList.getTail(); minFreqList.remove(tail); if (minFreqList.size == 0) { freqMap.remove(minFreq); } keyMap.remove(tail.key); } node = new Node(key, value, 1); keyMap.put(key, node); DoubleLinkedNode newFreq = freqMap.getOrDefault(1, new DoubleLinkedNode()); newFreq.insertHead(node); freqMap.put(1, newFreq); minFreq = 1; } else { node.value = value; int freq = node.frequency; DoubleLinkedNode oldFreq = freqMap.get(freq); oldFreq.remove(node); if (oldFreq.size == 0) { freqMap.remove(freq); if (minFreq == freq) { minFreq++; } } node.frequency = freq + 1; DoubleLinkedNode newFreq = freqMap.getOrDefault(freq + 1, new DoubleLinkedNode()); newFreq.insertHead(node); freqMap.put(freq + 1, newFreq); } } }
