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

[labuladong]

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

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

[zhangshuiyong]

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

[zhangshuiyong]

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

[daiyanze]

我之前也以为3哈希表的解法只能Java了，不过还好 JS/TS 有Set，一样可以O(1)

[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)

[yonggui-yan]

谢谢

小细节真多！

[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();
    }
};

[dongmy54]

手动实现LinkHashMap 贴一个ruby版本

class Node
  attr_accessor :key, :val, :prev, :next

  def initialize(key,val)
    @key = key
    @val = val
  end
end

# 双向链表
class DoubleList
  attr_accessor :head, :tail, :size

  def initialize
    @head = Node.new(nil, nil)
    @tail = Node.new(nil, nil)
    @head.next = @tail
    @tail.prev  = @head
    @size = 0
  end

  # 添加-加到尾部
  def add(node)
    # node自己指针
    node.prev = self.tail.prev
    node.next = self.tail
    # node前结点指针
    node.prev.next = node
    # 尾部指针
    self.tail.prev = node
    @size += 1
  end

  # 删除
  def remove(node)
    node.prev.next = node.next
    node.next.prev = node.prev
    @size -= 1
  end
end

# 链表hash
class LinkListHashMap
  attr_accessor :map, :list

  def initialize
    @map = {}  # key -> node
    @list = DoubleList.new
  end

  # 添加
  def add(key, val=nil)
    node = Node.new(key, val)
    @list.add(node)
    @map[key] = node
  end

  # 更新
  def update(key,val=nil)
    node = @map[key]
    node.val = val
  end

  # 删除
  def remove(key)
    node = @map[key]
    @list.remove(node)
    @map.delete(key).val
  end

  # 获取
  def get(key)
    @map[key].val
  end

  # 删除第一个
  def remove_first
    first = @list.head.next
    remove(first.key) if first != @list.tail
  end

  # 第一个key(便于LFU使用)
  def first_key
    first = @list.head.next
    first.key
  end

  # 是否存在
  def exists?(key)
    @map.keys.include?(key)
  end

  def size
    @list.size
  end
end


class LFUCache
  attr_accessor :key_to_val, :key_to_freq, :freq_to_keys, :capacity, :min_freq

  def initialize(capacity)
    @key_to_val   = {} # key -> val
    @key_to_freq  = {} # key -> freq 频率
    @freq_to_keys = {} # 频率 -> keys列表（这里用LinkListHashMap实现)
    @capacity     = capacity # 容量
    @min_freq     = 0 # 当前最小频率
  end

  def get(key)
    if key_exists?(key)
      increase_freq(key)
      @key_to_val[key]
    else
      -1
    end
  end

  def put(key, val)
    if key_exists?(key)
      # 更新KV
      @key_to_val[key] = val
      increase_freq(key)
    else
      if self.capacity <= size
        remove_min_freq_key
      end

      # 更新kV
      @key_to_val[key] = val
      # 更新KF
      @key_to_freq[key] = 1
      # 更新FK
      add_or_update_fk(1,key)
      # 更新min_freq
      self.min_freq = 1
    end
  end

  private
  # key是否存在
  def key_exists?(key)
    @key_to_val.keys.include?(key)
  end
  
  # 增加某个key使用频次
  def increase_freq(key)
    freq = @key_to_freq[key]
    # 更新KF频次
    @key_to_freq[key] = freq + 1    
    # 更新FK
    key_list = @freq_to_keys[freq]  # 频率键列表
    key_list.remove(key)            # 删除旧频率对应list中key
    if key_list.size == 0 # 如果删除key后，list为空
      @freq_to_keys.delete(freq) # 删除旧频率

      if freq == @min_freq # 刚好等于最低频率（只有当为key_list为空时需要做此判断，不空没影响）
        @min_freq += 1 
      end
    end
    # 添加新的频率(freq+1)到FK
    add_or_update_fk(freq+1,key)
  end

  # 添加or更新fk
  def add_or_update_fk(freq,key)
    if @freq_to_keys.keys.include?(freq)
      key_list = @freq_to_keys[freq]
      key_list.add(key)
    else
      list = LinkListHashMap.new
      list.add(key)
      @freq_to_keys[freq] = list
    end
  end

  # 移除最小频率key
  def remove_min_freq_key
    key_list = @freq_to_keys[self.min_freq]
    delete_key = key_list.first_key
    # 更新kV
    self.key_to_val.delete(delete_key)
    # 更新kF
    self.key_to_freq.delete(delete_key)
    # 更新FK
    key_list.remove(delete_key)
    if key_list.size == 0 # 删除key后空了
      @freq_to_keys.delete(self.min_freq)
      # 需要更新min_freq?
      # PS: 由于只有在新增的时候才会触发remove_min_freq_key,而新增key,min_freq 为1，
      # 所以没必要更新，即使更新那么只能遍历，时间复杂度也就上去了
    end
  end

  # 当前容量
  def size
    @key_to_val.keys.size
  end

end

[GoingMyWay]

C++的官方版本

class LFUCache {
    // key: frequency, value: list of original key-value pairs that have the same frequency.
    unordered_map<int, list<pair<int, int>>> frequencies;
    // key: original key, value: pair of frequency and the iterator corresponding key int the
    // frequencies map's list.
    unordered_map<int, pair<int, list<pair<int, int>>::iterator>> cache;
    int capacity;
    int minf;

    void insert(int key, int frequency, int value) {
        frequencies[frequency].push_back({key, value});
        cache[key] = {frequency, --frequencies[frequency].end()};
    }

public:
    LFUCache(int capacity) : capacity(capacity), minf(0) {}

    int get(int key) {
        const auto it = cache.find(key);
        if (it == cache.end()) {
            return -1;
        }
        const int f = it->second.first;
        const auto iter = it->second.second;
        const pair<int, int> kv = *iter;
        frequencies[f].erase(iter);
        if (frequencies[f].empty() && minf == f) {
            ++minf;
        }
        insert(key, f + 1, kv.second);
        return kv.second;
    }

    void put(int key, int value) {
        if (capacity <= 0) {
            return;
        }
        const auto it = cache.find(key);
        if (it != cache.end()) {
            it->second.second->second = value;
            get(key);
            return;
        }
        if (capacity == cache.size()) {
            cache.erase(frequencies[minf].front().first);
            frequencies[minf].pop_front();
        }
        minf = 1;
        insert(key, 1, value);
    }
};

[Jack-cin]

c++重新整理了一下思路

class LFUCache {
private:
//1) 关键：既要维护keytoFreq，也要维护freqToKeys(当freq相同时，维护相对时间顺序)
unordered_map<int, int> keyToFreq; //KF 频率
unordered_map<int, list> freqToKeys; //FKS 时间
//2）
unordered_map<int, pair<list::iterator,int>> cache;//指向 频率高(时间近)的node(含KV)
int cap;
int minFreq;

public:
LFUCache(int capacity){
this->cap=capacity;
this->minFreq=0;
}//或者写 LFUCache(int capacity):cap(capacity), minFreq(0) { }

int get(int key) {
     //1)无：返回-1
    if(!cache.count(key)) return -1;
    //2)有：返值，改"频率"
    //关键：修改 key 的频率
    increaseFreq(key);
    return cache[key].second;
}

void put(int key, int value) {
    //1）有：改值，改"频率"，return
    if(cache.count(key)) {
        cache[key].second = value;
        //关键：修改 key 的频率
        increaseFreq(key);
        return;//下面不用再执行了
    }
    //2) 无: a)满-“去除”（，“添加”） b)不满-直接“添加'
    if(cap == cache.size()) {
        removeMinFreqKey();
    }
    //关键：维护（ key的频率 ），（ 相同频率对应的key list(旧->新) ）,以及cache指向
    keyToFreq[key] = 1;
    if(!freqToKeys.count(1))freqToKeys[1] = list<int>();
    freqToKeys[1].push_back(key);

    cache[key] ={--freqToKeys[1].end(),value};
    minFreq = 1;
}

private:
//更新某个key的freq:
//肯定会涉及KF表和FKS表,并间接涉及cache指向（node(freq)->node(freq+1)）
//可能会涉及minFreq的更新
void increaseFreq(int key) {
//KF: 获取 key 对应旧的 freq, 并更新为freq+1
int freq = keyToFreq[key];
keyToFreq[key] = freq + 1;

    //FKS: 删除旧,添加新的
    freqToKeys[freq].erase(cache[key].first);
    if(!freqToKeys.count(freq + 1))freqToKeys[freq + 1] = list<int>();
    freqToKeys[freq + 1].push_back(key);
    //cache指向
    cache[key].first = --freqToKeys[freq + 1].end();

    if(freqToKeys[freq].empty()) {
        freqToKeys.erase(freq);
        // freq 对应的 keys 空了
        if(freq == minFreq) {
            this->minFreq++;  
        }
    }
    
}

//关键：寻(频率最小且最旧的key)
//肯定会涉及维护和此key有关的（FKS,KV,KF）
//可能会涉及minFreq的更新
void removeMinFreqKey() {
    int OldestKeyOfMinFreq = freqToKeys[minFreq].front();
    freqToKeys[minFreq].pop_front();//FKS
    cache.erase(OldestKeyOfMinFreq);//KV
    keyToFreq.erase(OldestKeyOfMinFreq);//KF

    if(freqToKeys[minFreq].empty()) {
        freqToKeys.erase(minFreq);//这里没必要更新minFreq变量:put()新元素时，直接设为1
    }
}

};