目标 LFU 算法是通过存储每个缓存使用的频率，在缓存容量满了之后，删除使用频率最少的缓存来给新的缓存留出空间。
如果多个缓存节点都拥有最少使用频率，则删除最久未使用的节点。
思路 我们会使用到两个 HashMap 以及一个HashLinkedList。
【LFU （最不经常使用算法）缓存】链表中的 Node 需要存储 key, value, frequency。一个 HashMap （frequencyTable）存储键值 frequency -> 链表, 另一个（cacheTable）存储键值 key -> Node。
定义一个 minFrequency 记录最少使用的频率。
具体操作 对于 get 操作，我们首先使用 key 来获取 cacheTable 中对应的 node:
1， 如果 key 不存在，则直接返回 null。
2， 如果 key 存在，我们直接从 node 所在的链表中移除该节点，从 node 中获取当前的 frequency 值并加1， 把该 node 插入到 frequency+1 对应的链表头部，判断是否需要更新minFrequency。
对于 put 操作，我们首先使用 key 来获取 cacheTable 中对应的 node:
1. 如果 key 不存在， 如果没有的话，相当于是新加入的缓存，如果缓存已经到达容量，通过 minFrequency 找到并删除最近最少使用的缓存，再进行插入。
2. 如果 key 存在，其实操作等价于 get(key) 操作，唯一的区别就是我们需要将当前的缓存里的值更新为 value。
实现 如果需要线程安全，只需在 get 和 put方法加上 synchronized 修饰符。
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.Map;
public class LFUCache {class CacheNode {
K key;
V value;
int frequency;
CacheNode(K key, V value, int frequency) {
this.key = key;
this.value = https://www.it610.com/article/value;
this.frequency = frequency;
}
}private Map> frequencyTable = new HashMap<>();
private Map cacheTable = new HashMap<>();
private int minFrequency;
private int capacity;
public LFUCache(int capacity) {
this.capacity = capacity;
this.minFrequency = 0;
}public void put(K key, V value) {
if (capacity <= 0) {
return;
}
CacheNode node = cacheTable.get(key);
if (node != null) {
node.value = https://www.it610.com/article/value;
increaseFrequency(node);
} else {
if (cacheTable.size() == capacity) {
removeMinFrequencyNode();
}
addNewCacheNode(key, value);
}
}public V get(K key) {
if (capacity <= 0) {
return null;
}
CacheNode node = cacheTable.get(key);
if (node != null) {
increaseFrequency(node);
return node.value;
}
return null;
}private void addNewCacheNode(K key, V value) {
CacheNode newCacheNode = new CacheNode(key, value, 1);
LinkedHashSet set = frequencyTable.computeIfAbsent(1, k -> new LinkedHashSet<>());
set.add(newCacheNode);
cacheTable.put(key, newCacheNode);
minFrequency = 1;
}private void removeMinFrequencyNode() {
LinkedHashSet minFrequencySet = frequencyTable.get(minFrequency);
CacheNode minFrequencyNode = minFrequencySet.iterator().next();
cacheTable.remove(minFrequencyNode.key);
minFrequencySet.remove(minFrequencyNode);
if (minFrequencySet.size() == 0) {
frequencyTable.remove(minFrequency);
}
}private void increaseFrequency(CacheNode node) {
int of = node.frequency;
LinkedHashSet set = frequencyTable.get(node.frequency);
set.remove(node);
if (set.isEmpty()) {
frequencyTable.remove(of);
if (of == minFrequency) {
minFrequency++;
}
}
int nf = node.frequency + 1;
node.frequency++;
LinkedHashSet newSet = frequencyTable.computeIfAbsent(nf, k -> new LinkedHashSet<>());
newSet.add(node);
}} 推荐阅读
- python|蓝桥杯每日一题（29）成绩统计（python）
- 欧拉定理与费马小定理
- 深度学习|正则化方法笔记
- kmeans|【ML31】Advanced K-means clustering algorithm
- 概率论|#统计学相关,Z分布,推断性统计
- yxc|AcWing 寒假每日一题 2021-01-19 找硬币
- 面试|面经自己汇总（三维视觉算法&机器学习&深度学习）——持续更新
- 数学建模与Matlab|层次分析法及matlab代码
- #|Python剑指offer打卡-4