算法就像搭乐高：带你手撸 LFU 算法 :: labuladong的算法小抄

[labuladong]

文章链接点这里：算法就像搭乐高：带你手撸 LFU 算法

评论礼仪 见这里，违者直接拉黑。

[zhangshuiyong]

FK表，是否可以是哈希链表？LinkedHashMap也可以满足我们 3.3，3.4，3.5

[zhangshuiyong]

其他语言没有java的LinkedHashSet，参照LRU的LinkedHashMap的自定义实现可以自己实现

[zhongweiLeex]

这个是否可以 定义后面的 freq2Key的 数据结构 为 HashMap<Integer,int[]> 这样拿到 minFreq 也能迅速定位吧 不成熟的小想法

[labuladong]

@zhongweiLeex 有想法可以尝试写一下解法

[lan-dian]

看了东哥的LRU想着LFU也能手写出来，没想到花了一个多小时哈哈。 下面是我的代码，和东哥的思路不一样。

class LFUCache {

    LinedList list;

    public LFUCache(int capacity) {
        list = new LinedList(capacity);
    }

    public int get(int key) {
        return list.get(key);
    }

    public void put(int key, int value) {
        list.add(key, value);
    }
}

class LinedList {

    Map<Integer, Node> map = new HashMap<>();

    TreeMap<Integer, Node> fluentMap = new TreeMap<>();

    Node head;

    Node tail;//越靠近tail频率越高，如果频率一样的话，那么最近被访问的会更靠近

    int capacity;

    int size;

    public LinedList(int c) {
        head = new Node();
        tail = new Node();
        head.next = tail;
        head.fluent = 0;
        tail.prev = head;
        tail.fluent = Integer.MAX_VALUE;

        capacity = c;
        size = 0;

        // fluentMap.put(0, head);
    }

    public int get(int k) {
        if (!map.containsKey(k)) {
            return -1;
        }
        Node node = map.get(k);
        fluentAdjust(node);
        return node.value;
    }

    private void fluentAdjust(Node node) {
        //更新我以前的频率或者删除已经不在存在的频率
        if (node.next.fluent != node.fluent && node.prev.fluent != node.fluent) {//我是唯一一个这个频率的，现在我要走了，删除
            fluentMap.remove(node.fluent);
        } else if (node.next.fluent != node.fluent && node.prev.fluent == node.fluent) {//我是最后一个这个频率的
            fluentMap.put(node.fluent, node.prev);
        }
        node.fluent++;
        Node pre=head;
        Map.Entry<Integer, Node> nodeEntry = fluentMap.floorEntry(node.fluent);
        if(nodeEntry!=null){
            pre=nodeEntry.getValue();
        }
        //把以前的接上来
        remove(node);
        
        Node next = pre.next;
        pre.next=node;
        node.prev=pre;
        next.prev=node;
        node.next=next;
        fluentMap.put(node.fluent,node);
        // Node cur=node,pre=node.prev;
        // while(node.fluent<=cur.next.fluent){
        //     pre=cur;
        //     cur=cur.next;
        // }
        //删除node
        // node.prev.next = node.next;
        // node.next.prev = node.prev;
        //链接node到正确的位置
        // node.prev = pre;
        // node.next = cur;
        // pre.next = node;
        // cur.prev = node;
    }
    
    public void remove(Node node){
        Node pre = node.prev;
        Node next = node.next;
        pre.next=next;
        next.prev=pre;
    }

    public void add(int k, int v) {
        if(capacity==0){
            return;
        }
        if (map.containsKey(k)) {
            //更新节点
            Node node = map.get(k);
            node.value = v;
            fluentAdjust(node);
        } else {
            if (size >= capacity) {
                //移出最前面的
                if (head.next != tail) {
                    int key = head.next.key;
                    // map.remove(key);
                    Node node = map.remove(key);
                    if (node.fluent != node.next.fluent) {
                        fluentMap.remove(node.fluent);
                    }
                    head.next.next.prev = head;
                    head.next = head.next.next;
                }
            }
            Node node = new Node(k, v);
            Node cur = fluentMap.get(1);
            if(cur==null){
                cur=head;
            }
            Node next=cur.next;
            cur.next=node;
            node.prev=cur;
            node.next=next;
            next.prev=node;

            //因为新加入的频率是1
            // Node cur = head.next;
            // Node pre = head;
            // while (cur.fluent <= 1) {
            //     pre = cur;
            //     cur = cur.next;
            // }
            // pre.next = node;
            // node.prev = pre;
            // cur.prev = node;
            // node.next = cur;
            fluentMap.put(1,node);
            map.put(k,node);
            size++;
        }
    }


}

class Node {

    int key;

    int value;

    int fluent;

    Node next;

    Node prev;


    public Node() {

    }

    public Node(int k, int v) {
        key = k;
        value = v;
        fluent = 1;
    }

}

[lhcezx]

贴一个C++版本，用了两个哈希链表，感觉比较容易理解和记住

struct Node {
    int key;
    int val;    
    int freq;
    Node(int _key, int _val, int _freq): key(_key), val(_val), freq(_freq) {}
};

class LFUCache {
    unordered_map<int, list<Node>::iterator> key_table;           //  每个键key保存着对应的链表节点的地址，注意这里必须保存地址，否则对链表节点的修改需要手动更新哈希表
    unordered_map<int, list<Node>> freq_table;                    //  每个freq对应一个链表，表头是最新的元素，表尾是最旧的元素
    int capacity;
    int min_freq = 0;
public:
    LFUCache(int capacity) {
        this->capacity = capacity;
        key_table.clear();
        freq_table.clear();
    }
    
    //  用于超出容量时，删除最小使用频率的最不常用的节点，也就是其链表的尾节点
    void removeLast(int freq) {
        Node last = freq_table[freq].back();        //  找到这个freq对应的链表list_node中的表尾元素
        key_table.erase(last.key);                  //  将其从key_table中删除
        freq_table[freq].pop_back();                //  将其从list_node删除
        if (freq_table[freq].size() == 0) {         //  如果这条链表为空了，则直接删除这个键表对，并更新min_freq
            freq_table.erase(freq);
            if (min_freq == freq) min_freq++;
        }
    }

    //  用于当调用get或put当键存在时，将其从freq的链表中删除然后放到freq + 1的链表表头, 此函数中除了freq对应的链表节点全部被删除的情况外，min_freq不需要更新，因为freq只增加不减少
    void moveToHead(int key) {                     
        //  首先将节点从freq的链表中删除
        list<Node>::iterator iter = key_table[key];
        int val = iter->val;
        int freq = iter->freq;
        freq_table[freq].erase(iter);
        if (freq_table[freq].size() == 0) {         //  如果这条链表为空了，则直接删除这个键表对，并更新min_freq
            freq_table.erase(freq);
            if (min_freq == freq) min_freq++;
        }
        //  然后将该节点加入到freq + 1的链表头部
        //  由于freq_table[freq].erase(iter)会直接将iter指针从链表中删除，需要创建一个新的节点放到freq+1链表表头，并更新key_table中的key对应的节点地址
        freq_table[freq + 1].push_front(Node(key, val, freq + 1));
        key_table[key] = freq_table[freq + 1].begin();
    }

    int get(int key) {
        if (!key_table.count(key) || capacity == 0) return -1;
        moveToHead(key);
        return key_table[key]->val;
    }
    
    void put(int key, int value) {
        if (capacity == 0) return;
        //  如果这个键值对存在，则直接修改并更新freq
        if (key_table.count(key)) {
            auto iter = key_table[key];
            iter->val = value;
            moveToHead(key);
            return;
        }

        //  如果键不存在
        if (key_table.size() == capacity) {
            removeLast(min_freq);
        }
        freq_table[1].push_front(Node(key, value, 1));
        key_table[key] = freq_table[1].begin();
        min_freq = 1;
    }
};

[Lock0nStratos]

照着写了个Python版本，用OrderedDict替代LinkedHashSet

from collections import OrderedDict


class LFUCache:
    def __init__(self, capacity):
        self.key2val = {}  # key 到 val 的映射，我们后文称为 KV 表
        self.key2freq = {}  # key 到 freq 的映射，我们后文称为 KF 表
        self.freq2key = {}  # freq 到 key 列表的映射，我们后文称为 FK 表
        self.min_freq = 0  # 记录最小的频次
        self.capacity = capacity  # 记录 LFU 缓存的最大容量

    def get(self, key: int) -> int:
        if key not in self.key2val.keys():
            return -1
        # 增加 key 对应的 freq
        self.increase_freq(key)
        return self.key2val[key]

    def put(self, key: int, val: int):
        if self.capacity <= 0:
            return
        # 若 key 已存在，修改对应的 val 即可
        if key in self.key2val.keys():
            self.key2val[key] = val
            self.increase_freq(key)
            return
        # key不存在，需要插入,容量已满的话需要淘汰一个freq最小的key
        if self.capacity <= self.key2val.__len__():
            self.remove_minfreqkey(key)
        # 插入 key 和 val，对应的 freq 为 1
        self.key2val[key] = val
        self.key2freq[key] = 1
        if 1 not in self.freq2key.keys():
            self.freq2key[1] = OrderedDict()
        self.freq2key[1][key] = None
        # 插入新 key 后最小的 freq 肯定是 1
        self.min_freq = 1

    def increase_freq(self, key):
        freq = self.key2freq[key]
        self.key2freq[key] += 1
        # 将 key 从 freq 对应的列表中删除
        self.freq2key[freq].pop(key)
        # 如果 freq 对应的列表空了，移除这个 freq
        if freq + 1 not in self.freq2key.keys():
            self.freq2key[freq + 1] = OrderedDict()
        self.freq2key[freq + 1][key] = None
        # 如果 freq 对应的列表空了，移除这个 freq
        if len(self.freq2key[freq]) == 0:
            self.freq2key.pop(freq)
            # 如果这个 freq 恰好是 minFreq，更新 minFreq
            if self.min_freq == freq:
                self.min_freq += 1

    def remove_minfreqkey(self, key):
        # req 最小的 key 列表
        key_dict = self.freq2key[self.min_freq]
        # 其中最先被插入的那个 key 就是该被淘汰的 key
        delete_key, _ = key_dict.popitem(last=False)  # last=True:LIFO;last=False:FIFO
        if len(key_dict) == 0:
            self.freq2key.pop(self.min_freq)
            # 问：这里需要更新 minFreq 的值吗？
        self.key2val.pop(delete_key)
        self.key2freq.pop(delete_key)

[lambdaxing]

C++ copy ，通过 map 、list 和迭代器实现哈希链表：

class LFUCache {
public:

    unordered_map<int, int> keyToVal;                       // 存储 key-value
    unordered_map<int, int> keyToFreq;                      // 存储 key-freq(计数值)
    unordered_map<int, list<int>> freqToKeys;               // 存储 freq-keys(list) 一对多的关系，一个计数值对应多个 key
    unordered_map<int, list<int>::iterator> keyToFKNode;    // 存储 key -  key 在 FK 中的位置，keys(list) 的迭代器，表示 FK[key] 这条链表上的一个节点位置

    int cap;
    int minFreq;

    LFUCache(int capacity) : cap(capacity), minFreq(0) { }
    
    int get(int key) {
        if(!keyToVal.count(key)) {
            return -1;
        }
        increaseFreq(key);
        return keyToVal[key];
    }
    
    void put(int key, int value) {
        if(cap <= 0) return;

        if(keyToVal.count(key)) {
            keyToVal[key] = value;
            increaseFreq(key);
            return;
        }

        if(cap <= keyToVal.size()) {
            removeMinFreqKey();
        }

        keyToVal[key] = value;
        keyToFreq[key] = 1;

        if(!freqToKeys.count(1)) {
            freqToKeys[1] = list<int>();
        }
        freqToKeys[1].push_back(key);
        keyToFKNode[key] = --freqToKeys[1].end();

        minFreq = 1;
    }

    void removeMinFreqKey() {
        int OldestKeyOfMinFreq = freqToKeys[minFreq].front();
        freqToKeys[minFreq].pop_front();
        keyToFKNode.erase(OldestKeyOfMinFreq);

        if(freqToKeys[minFreq].empty()) {
            freqToKeys.erase(minFreq);
        }

        keyToVal.erase(OldestKeyOfMinFreq);
        keyToFreq.erase(OldestKeyOfMinFreq);
    }

    void increaseFreq(int key) {
        // 获取 key 对应的 freq
        int freq = keyToFreq[key];
        // 更新 KF
        keyToFreq[key] = freq + 1;
        // 更新 FKS，删除旧的 freq
        freqToKeys[freq].erase(keyToFKNode[key]);
        if(freqToKeys[freq].empty()) {
            freqToKeys.erase(freq);
            // freq 对应的 keys 空了
            if(freq == minFreq) {
                minFreq++;  // 如果 minFreq == freq，增加 minFreq （不用担心增加后的 minFreq 不存在，因为它至少会有一个当前这个 key 对应）
            }
        }
        // 更新 FKS，添加新的 freq
        if(!freqToKeys.count(freq + 1)) {
            freqToKeys[freq + 1] = list<int>();
        }
        freqToKeys[freq + 1].push_back(key);
        keyToFKNode[key] = --freqToKeys[freq + 1].end();
    }
};