[数据结构与算法]七、LRU和LFU

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中不存在，返回-1
        if (!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 对应的 freq
        return 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 肯定是 1
        freqToKey.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 对应的列表空了，移除这个 freq
        if (freqToKey.get(oldValue).isEmpty()) {
            freqToKey.remove(oldValue);
            // 如果这个 freq 恰好是 minFreq，更新 minFreq
            if (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 就是该被淘汰的 key
        Integer oldKey = list.iterator().next();
        /* 更新 FK 表 */
        list.remove(oldKey);
        if (list.isEmpty()) {
            freqToKey.remove(this.minFreq);
            // 问：这里需要更新 minFreq 的值吗？
        }
        keyToValue.remove(oldKey);        /* 更新 KV 表 */
        keyToFreq.remove(oldKey);       /* 更新 KF 表 */
    }
}