1、LFU算法是什么？
LFU（Least Frequently Used）最近最少使用算法。它是基于“如果一个数据在最近一段时间内使用次数很少，那么在将来一段时间内被使用的可能性也很小”的思路。
LFU和LRU算法的不同之处，LRU的淘汰规则是基于访问时间，而LFU是基于访问次数的。
从实现难度上来说，LFU 算法的难度大于 LRU 算法，因为 LRU 算法相当于把数据按照时间排序，这个需求借助链表很自然就能实现，你一直从链表头部加入元素的话，越靠近头部的元素就是新的数据，越靠近尾部的元素就是旧的数据，我们进行缓存淘汰的时候只要简单地将尾部的元素淘汰掉就行了。
而 LFU 算法相当于是淘汰访问频次最低的数据，如果访问频次最低的数据有多条，需要淘汰最旧的数据。把数据按照访问频次进行排序，而且频次还会不断变化，这可不容易实现。
2、实现LFU算法
LFU常见的实现方式有以下三种：
（1）利用一个数组存储数据项，用hashmap存储每个数据项在数组中对应的位置，然后为每个数据项设计一个访问频次，当数据项被命中时，访问频次自增，在淘汰的时候淘汰访问频次最少的数据。这样一来的话，在插入数据和访问数据的时候都能达到O(1)的时间复杂度，在淘汰数据的时候，通过选择算法得到应该淘汰的数据项在数组中的索引，并将该索引位置的内容替换为新来的数据内容即可，这样的话，淘汰数据的操作时间复杂度为O(n)。
（2）利用小顶堆+哈希表，小顶堆插入、删除操作都能达到O(logn)时间复杂度，因此效率相比第一种实现方法更加高效。
（3）使用三个HashMap，一个Map维护Key-Value的关系，一个Map维护Key-Freq的关系，前两个Map可以保证查找和插入是O(1)的时间复杂度，不能保证删除也是O(1)的时间复杂度，因此还需要使用一个类似LinkList的数据结构维护插入的时间顺序，并且还需要肯定是需要freq到key的映射，用来找到freq最小的key，因此可以维护一个Map<Integer，LinkedHashSet>类型的Map，这是个一对多的关系，一方就是频率，多方就是key，因为具有某个频率的key可能有多个，并且在使用一个变量minFreq维护系统当前访问频次最低的次数，当表满了的时候直接删除minFreq对应的LinkedHashSet中的第一个key就好了,这样就可以实现O(1)的删除时间复杂度
接下来我们针对第三个方案，来实现一下LFU，首先我们分析一下算法的实现思路
思路分析
先从最简单的开始，根据 LFU 算法的逻辑，我们先列举出算法执行过程中的几个显而易见的事实：
1、调用get(key)方法时，要返回该key对应的val。对于这个需求，我们可以使用一个Map来保存Key-Value的映射关系，可以使get()方法是O(1)的时间复杂度。
2、只要用get或者put方法访问某个key一次，该key的freq就要加1。对于这个需求，还是可以使用一个Map来保存Key-Freq的映射关系
3、如果在容量满了的时候进行插入，则需要将freq最小的key删除，如果最小的freq对应多个key，则删除其中最旧（加入时间最长）的那一个数据。这种情况比较复杂，也是实现LFU的核心，我们分开说：
- 3.1 为了通过freq找到需要删除的key，我们首先需要一个Map来维护freq到key的映射关系；
- 3.2 将
freq最小的key删除，那你就得快速得到当前所有key最小的freq是多少。想要时间复杂度 O(1) 的话，肯定不能遍历一遍去找，那就用一个变量minFreq来记录当前最小的freq吧。 - 3.3 可能有多个
key拥有相同的freq，所以freq对key是一对多的关系，即一个freq对应一个key的列表。 - 3.4 希望
freq对应的key的列表是存在时序的，便于快速查找并删除最旧的key。 - 3.5 希望能够快速删除
key列表中的任何一个key，因为如果频次为freq的某个key被访问，那么它的频次就会变成freq+1，就应该从freq对应的key列表中删除，加到freq+1对应的key的列表中。
综合各种情况，我们可以使用Map<Integer,LinkedHashSet>来解决问题，LinkedHashSet顾名思义，是链表和哈希集合的结合体。链表不能快速访问链表节点，但是插入元素具有时序；哈希集合中的元素无序，但是可以对元素进行快速的访问和删除。那么，它俩结合起来就兼具了哈希集合和链表的特性，既可以在 O(1) 时间内访问或删除其中的元素，又可以保持插入的时序。
综上，我们可以大致写一下LRU算法大致算法框架：
public class LFUCache<K, V> implements Cache<K, V> {
/***缓存容量*/
private int capacity;
//key-value映射
private HashMap<K, V> keyToVal;
//key-freq映射
private HashMap<K, Integer> keyToFreq;
//freq-key映射
private HashMap<Integer, LinkedHashSet<K>> freqToKeys;
//key的最低频次
private int minFreq;
public LFUCache(int capacity) {
this.capacity = capacity;
keyToVal = new HashMap<>(capacity);
keyToFreq = new HashMap<>(capacity);
freqToKeys = new HashMap<>(capacity);
}
//获取缓存数据
@Override
public V get(K key) {
}
//添加缓存数据
@Override
public void put(K key,V val){
}
}
接下来就是实现get和put两个核心功能，get方法的执行逻辑非常简单，就是直接从K-V哈希表中获取键位key的元素即可，如果有就返回Value并同时更新对应key的访问频次即可；否则返回null，结束。
public V get(K key) {
if (keyToVal.containsKey(key)) {
V val = keyToVal.get(key);
//更新key
updateFreq(key);
return val;
}
return null;
}
//更新key
private void updateFreq(K key) {
//更新kF表
Integer freq = keyToFreq.get(key);
keyToFreq.put(key, freq + 1);
//更新Fk表
freqToKeys.get(freq).remove(key);
freqToKeys.putIfAbsent(freq + 1, new LinkedHashSet<>());
freqToKeys.get(freq + 1).add(key);
if (freqToKeys.get(key).isEmpty()) {
freqToKeys.remove(key);
if (freq == minFreq) {
minFreq++;
}
}
}
updateFreq方法更新某个key的freq肯定会涉及FK表和KF表，我们分别更新这两个表就行了。
和之前类似，当FK表中freq对应的列表被删空后，需要删除FK表中freq这个映射。如果这个freq恰好是minFreq，说明minFreq变量需要更新。
能不能快速找到当前的minFreq呢？这里是可以的，因为我们刚才把key的freq加了 1 嘛，所以minFreq也加 1 就行了。
下面来实现put(key, val)方法，逻辑略微复杂，我们直接画个图来看：
public void put(K key, V val) {
if (keyToVal.containsKey(key)) {
//更新value
keyToVal.put(key, val);
//更新freq
updateFreq(key);
return;
}
if (keyToVal.size() >= this.capacity) {
removeMinFreqKey();
}
//添加新的元素
keyToVal.put(key, val);
keyToFreq.put(key, 1);
freqToKeys.putIfAbsent(1, new LinkedHashSet<>());
freqToKeys.get(1).add(key);
//插入新值后，最小的频次肯定是1
this.minFreq = 1;
}
/**
* 核心实现：移除频次最低并且时间最老的key
*/
private void removeMinFreqKey() {
LinkedHashSet<K> keys = freqToKeys.get(minFreq);
K expireKey = keys.iterator().next();
//更新FK
keys.remove(expireKey);
//如果keys
if (keys.isEmpty()) {
freqToKeys.remove(minFreq);
}
//更新KF
keyToFreq.remove(expireKey);
//更新KV
keyToVal.remove(expireKey);
}
removeMinFreqKey方法中删除某个键key肯定是要同时修改三个映射表的，借助minFreq参数可以从FK表中找到freq最小的keyList，根据时序，其中第一个元素就是要被淘汰的deletedKey，操作三个映射表删除这个key即可。
但是有个细节问题，如果keyList中只有一个元素，那么删除之后minFreq对应的key列表就为空了，也就是minFreq变量需要被更新。如何计算当前的minFreq是多少呢？
实际上没办法快速计算minFreq，只能线性遍历FK表或者KF表来计算，这样肯定不能保证 O(1) 的时间复杂度。
但是，其实这里没必要更新minFreq变量，因为你想想removeMinFreqKey这个函数是在什么时候调用？在put方法中插入新key时可能调用。而你回头看put的代码，插入新key时一定会把minFreq更新成 1，所以说即便这里minFreq变了，我们也不需要管它。
3、总结
终于总结完了，其实，感觉思想搞明白了，代码实现起来就相对容易一些。但是，还是需要多写，多实践。过段时间再来回顾一下下面将源码贴出来：
-
github：https://github.com/LoverITer/leetcode/blob/master/lru/src/main/java/cache/lfu/LFUCache.java
-
完整代码：
package cache.lfu;
import cache.Cache;
import java.util.HashMap;
import java.util.LinkedHashSet;
/**
* LFU（Least Frequently Used）最近最少使用算法。它是基于“如果一个数据在最近一段时间内使用次数很少，
* 那么在将来一段时间内被使用的可能性也很小”的思路
* 注意LFU和LRU算法的不同之处，LRU的淘汰规则是基于访问时间，而LFU是基于访问次数的。
*
* @author ：huangxin
* @modified ：
* @since ：2020/09/01 08:19
*/
public class LFUCache<K, V> implements Cache<K, V> {
/***缓存容量*/
private int capacity;
//key-value映射
private HashMap<K, V> keyToVal;
//key-freq映射
private HashMap<K, Integer> keyToFreq;
//freq-key映射
private HashMap<Integer, LinkedHashSet<K>> freqToKeys;
//key的最低频次
private int minFreq;
public LFUCache(int capacity) {
this.capacity = capacity;
keyToVal = new HashMap<>(capacity);
keyToFreq = new HashMap<>(capacity);
freqToKeys = new HashMap<>(capacity);
}
@Override
public V get(K key) {
if (keyToVal.containsKey(key)) {
V val = keyToVal.get(key);
//更新key
updateFreq(key);
return val;
}
return null;
}
private void updateFreq(K key) {
//更新kF表
Integer freq = keyToFreq.get(key);
keyToFreq.put(key, freq + 1);
//更新Fk表
freqToKeys.get(freq).remove(key);
freqToKeys.putIfAbsent(freq + 1, new LinkedHashSet<>());
freqToKeys.get(freq + 1).add(key);
if (freqToKeys.get(key).isEmpty()) {
freqToKeys.remove(key);
if (freq == minFreq) {
minFreq++;
}
}
}
@Override
public void put(K key, V val) {
if (keyToVal.containsKey(key)) {
//更新value
keyToVal.put(key, val);
//更新freq
updateFreq(key);
return;
}
if (keyToVal.size() >= this.capacity) {
removeMinFreqKey();
}
//添加新的元素
keyToVal.put(key, val);
keyToFreq.put(key, 1);
freqToKeys.putIfAbsent(1, new LinkedHashSet<>());
freqToKeys.get(1).add(key);
//插入新值后，最小的频次肯定是1
this.minFreq = 1;
}
/**
* 核心实现：移除频次最低并且时间最老的key
*/
private void removeMinFreqKey() {
LinkedHashSet<K> keys = freqToKeys.get(minFreq);
K expireKey = keys.iterator().next();
//更新FK
keys.remove(expireKey);
//如果keys
if (keys.isEmpty()) {
freqToKeys.remove(minFreq);
}
//更新KF
keyToFreq.remove(expireKey);
//更新KV
keyToVal.remove(expireKey);
}
@Override
public String toString() {
return "LFUCache{" +
"capacity=" + capacity +
", keyToVal=" + keyToVal.toString() +
", keyToFreq=" + keyToFreq.toString() +
", freqToKeys=" + freqToKeys.toString() +
", minFreq=" + minFreq +
'}';
}
public static void main(String[] args) {
// 构造一个容量为 3 的 LFU 缓存
LFUCache cache = new LFUCache(3);
// 插入两对 (key, val)，对应的 freq 为 1
cache.put(1, 10);
cache.put(2, 20);
cache.put(5, 50);
System.out.println(cache);
// 查询 key 为 1 对应的 val
// 返回 10，同时键 1 对应的 freq 变为 2
System.out.println(cache.get(1));
System.out.println(cache);
// 容量已满，淘汰 freq 最小的并且最老键 2
// 插入键值对 (3, 30)，对应的 freq 为 1
cache.put(3, 30);
System.out.println(cache);
// 键 2 已经被淘汰删除，返回 -1
System.out.println(cache.get(2));
System.out.println(cache);
}
}