LRU

根据题意，使用过的数据放在链表的尾部，容量满了就删除链表的头，使用的数据结构是LinkedHashMap。
在这里插入图片描述

146. LRU 缓存(中等)

class LRUCache {private int cap;private LinkedHashMap<Integer, Integer> list;public LRUCache(int capacity) {this.list = new LinkedHashMap<>();this.cap = capacity;}public int get(int key) {//cache中不存在，返回-1if (!list.containsKey(key)) {return -1;}//存在，key变为使用过-放到哈希表末尾makeRencentlyUsed(key);// 将 key 变为最近使⽤return list.get(key);}/* 添加最近使⽤的元素 */public void put(int key, int value) {//存在就更新if (list.containsKey(key)) {list.put(key, value);makeRencentlyUsed(key);//put和get存在的话都要将key提升到最近使用的位置，即链表末尾return;}//判断容量if (this.cap <= list.size()) {int oldKey = list.keySet().iterator().next();list.remove(oldKey);//不满足删除最久没有使用过的数据，即链表头节点}list.put(key, value);}/* 将某个 key 提升为最近使⽤的 */private void makeRencentlyUsed(int key) {int oldValue = list.get(key);list.remove(key);        // 先从链表中删除这个节点list.put(key, oldValue);// 重新插到队尾}
}

LFU

460. LFU 缓存(困难)

class LFUCache {private HashMap<Integer, Integer> keyToValue;private HashMap<Integer, Integer> keyToFreq;private HashMap<Integer, LinkedHashSet<Integer>> freqToKey;private int cap;private int minFreq;public LFUCache(int capacity) {this.keyToValue = new HashMap<>();this.keyToFreq = new HashMap<>();this.freqToKey = new HashMap<>();this.cap = capacity;this.minFreq = 0;}public int get(int key) {if (!keyToValue.containsKey(key)) {return -1;}increaseFreq(key);// 增加 key 对应的 freqreturn keyToValue.get(key);}public void put(int key, int value) {if (this.cap <= 0) return;/* 若 key 已存在，修改对应的 val 即可 */if (keyToValue.containsKey(key)) {keyToValue.put(key, value);// key 对应的 freq 加一increaseFreq(key);return;}/* key 不存在，需要插入 *//* 容量已满的话需要淘汰一个 freq 最小的 key */if (this.cap <= keyToValue.size()) {removeMinFreq(key);}/* 插入 key 和 val，对应的 freq 为 1 */// 插入 KV 表keyToValue.put(key, value);// 插入 KF 表keyToFreq.put(key, 1);// 插入 FK 表freqToKey.putIfAbsent(1, new LinkedHashSet<>());// 插入新 key 后最小的 freq 肯定是 1freqToKey.get(1).add(key);this.minFreq = 1;return;}private void increaseFreq(int key) {int oldValue = keyToFreq.get(key);keyToFreq.put(key, oldValue + 1);        /* 更新 KF 表 *//* 更新 FK 表 */freqToKey.get(oldValue).remove(key);// 将 key 从 freq 对应的列表中删除// 如果 freq 对应的列表空了，移除这个 freqif (freqToKey.get(oldValue).isEmpty()) {freqToKey.remove(oldValue);// 如果这个 freq 恰好是 minFreq，更新 minFreqif (minFreq == oldValue) {minFreq++;}}freqToKey.putIfAbsent(oldValue + 1, new LinkedHashSet<>());// 将 key 加入 freq + 1 对应的列表中freqToKey.get(oldValue + 1).add(key);}private void removeMinFreq(int key) {// freq 最小的 key 列表LinkedHashSet<Integer> list = freqToKey.get(this.minFreq);// 其中最先被插入的那个 key 就是该被淘汰的 keyInteger oldKey = list.iterator().next();/* 更新 FK 表 */list.remove(oldKey);if (list.isEmpty()) {freqToKey.remove(this.minFreq);// 问：这里需要更新 minFreq 的值吗？}keyToValue.remove(oldKey);        /* 更新 KV 表 */keyToFreq.remove(oldKey);       /* 更新 KF 表 */}
}