LFU缓存算法到底是怎么一回事?

1、LFU算法是什么?

LFU(Least Frequently Used)最近最少使用算法。它是基于“如果一个数据在最近一段时间内使用次数很少,那么在将来一段时间内被使用的可能性也很小”的思路。

LFU和LRU算法的不同之处,LRU的淘汰规则是基于访问时间,而LFU是基于访问次数的。

从实现难度上来说,LFU 算法的难度大于 LRU 算法,因为 LRU 算法相当于把数据按照时间排序,这个需求借助链表很自然就能实现,你一直从链表头部加入元素的话,越靠近头部的元素就是新的数据,越靠近尾部的元素就是旧的数据,我们进行缓存淘汰的时候只要简单地将尾部的元素淘汰掉就行了。

LFU 算法相当于是淘汰访问频次最低的数据,如果访问频次最低的数据有多条,需要淘汰最旧的数据。把数据按照访问频次进行排序,而且频次还会不断变化,这可不容易实现。

2、实现LFU算法

LFU常见的实现方式有以下三种:

(1)利用一个数组存储数据项,用hashmap存储每个数据项在数组中对应的位置,然后为每个数据项设计一个访问频次,当数据项被命中时,访问频次自增,在淘汰的时候淘汰访问频次最少的数据。这样一来的话,在插入数据和访问数据的时候都能达到O(1)的时间复杂度,在淘汰数据的时候,通过选择算法得到应该淘汰的数据项在数组中的索引,并将该索引位置的内容替换为新来的数据内容即可,这样的话,淘汰数据的操作时间复杂度为O(n)。

(2)利用小顶堆+哈希表,小顶堆插入、删除操作都能达到O(logn)时间复杂度,因此效率相比第一种实现方法更加高效。

(3)使用三个HashMap,一个Map维护Key-Value的关系,一个Map维护Key-Freq的关系,前两个Map可以保证查找和插入是O(1)的时间复杂度,不能保证删除也是O(1)的时间复杂度,因此还需要使用一个类似LinkList的数据结构维护插入的时间顺序,并且还需要肯定是需要freqkey的映射,用来找到freq最小的key,因此可以维护一个Map<Integer,LinkedHashSet>类型的Map,这是个一对多的关系,一方就是频率,多方就是key,因为具有某个频率的key可能有多个,并且在使用一个变量minFreq维护系统当前访问频次最低的次数,当表满了的时候直接删除minFreq对应的LinkedHashSet中的第一个key就好了,这样就可以实现O(1)的删除时间复杂度

接下来我们针对第三个方案,来实现一下LFU,首先我们分析一下算法的实现思路

思路分析

先从最简单的开始,根据 LFU 算法的逻辑,我们先列举出算法执行过程中的几个显而易见的事实:

1、调用get(key)方法时,要返回该key对应的val。对于这个需求,我们可以使用一个Map来保存Key-Value的映射关系,可以使get()方法是O(1)的时间复杂度。

2、只要用get或者put方法访问某个key一次,该key的freq就要加1。对于这个需求,还是可以使用一个Map来保存Key-Freq的映射关系

3、如果在容量满了的时候进行插入,则需要将freq最小的key删除,如果最小的freq对应多个key,则删除其中最旧(加入时间最长)的那一个数据。这种情况比较复杂,也是实现LFU的核心,我们分开说:

  • 3.1 为了通过freq找到需要删除的key,我们首先需要一个Map来维护freq到key的映射关系;
  • 3.2 将freq最小的key删除,那你就得快速得到当前所有key最小的freq是多少。想要时间复杂度 O(1) 的话,肯定不能遍历一遍去找,那就用一个变量minFreq来记录当前最小的freq吧。
  • 3.3 可能有多个key拥有相同的freq,所以 freqkey是一对多的关系,即一个freq对应一个key的列表。
  • 3.4 希望freq对应的key的列表是存在时序的,便于快速查找并删除最旧的key
  • 3.5 希望能够快速删除key列表中的任何一个key,因为如果频次为freq的某个key被访问,那么它的频次就会变成freq+1,就应该从freq对应的key列表中删除,加到freq+1对应的key的列表中。

综合各种情况,我们可以使用Map<Integer,LinkedHashSet>来解决问题,LinkedHashSet顾名思义,是链表和哈希集合的结合体。链表不能快速访问链表节点,但是插入元素具有时序;哈希集合中的元素无序,但是可以对元素进行快速的访问和删除。那么,它俩结合起来就兼具了哈希集合和链表的特性,既可以在 O(1) 时间内访问或删除其中的元素,又可以保持插入的时序。

综上,我们可以大致写一下LRU算法大致算法框架:

public class LFUCache<K, V> implements Cache<K, V> {

    /***缓存容量*/
    private int capacity;
    //key-value映射
    private HashMap<K, V> keyToVal;
    //key-freq映射
    private HashMap<K, Integer> keyToFreq;
    //freq-key映射
    private HashMap<Integer, LinkedHashSet<K>> freqToKeys;
    //key的最低频次
    private int minFreq;
 
    public LFUCache(int capacity) {
        this.capacity = capacity;
        keyToVal = new HashMap<>(capacity);
        keyToFreq = new HashMap<>(capacity);
        freqToKeys = new HashMap<>(capacity);
    }
    
    //获取缓存数据
    @Override
    public V get(K key) {
    }
    
    //添加缓存数据
    @Override
    public void put(K key,V val){
    }
}    

接下来就是实现get和put两个核心功能,get方法的执行逻辑非常简单,就是直接从K-V哈希表中获取键位key的元素即可,如果有就返回Value并同时更新对应key的访问频次即可;否则返回null,结束。

public V get(K key) {               
   if (keyToVal.containsKey(key)) {
       V val = keyToVal.get(key);  
       //更新key                     
       updateFreq(key);            
       return val;                 
   }                               
   return null; 
}

//更新key
private void updateFreq(K key) {                            
    //更新kF表                                                 
    Integer freq = keyToFreq.get(key);                      
    keyToFreq.put(key, freq + 1);                           
    //更新Fk表                                                 
    freqToKeys.get(freq).remove(key);                       
    freqToKeys.putIfAbsent(freq + 1, new LinkedHashSet<>());
    freqToKeys.get(freq + 1).add(key);                      
    if (freqToKeys.get(key).isEmpty()) {                    
        freqToKeys.remove(key);                             
        if (freq == minFreq) {                              
            minFreq++;                                      
        }                                                   
    }                                                       
}                                                           

updateFreq方法更新某个keyfreq肯定会涉及FK表和KF表,我们分别更新这两个表就行了。

和之前类似,当FK表中freq对应的列表被删空后,需要删除FK表中freq这个映射。如果这个freq恰好是minFreq,说明minFreq变量需要更新。

能不能快速找到当前的minFreq呢?这里是可以的,因为我们刚才把keyfreq加了 1 嘛,所以minFreq也加 1 就行了。

下面来实现put(key, val)方法,逻辑略微复杂,我们直接画个图来看:

public void put(K key, V val) {
    if (keyToVal.containsKey(key)) {
        //更新value
        keyToVal.put(key, val);
        //更新freq
        updateFreq(key);
        return;
    }
    if (keyToVal.size() >= this.capacity) {          
        removeMinFreqKey();
    }
    //添加新的元素
    keyToVal.put(key, val);
    keyToFreq.put(key, 1);
    freqToKeys.putIfAbsent(1, new LinkedHashSet<>());
    freqToKeys.get(1).add(key);
    //插入新值后,最小的频次肯定是1
    this.minFreq = 1;                                
}

/**                                                  
 * 核心实现:移除频次最低并且时间最老的key                             
 */                                                  
private void removeMinFreqKey() {                    
    LinkedHashSet<K> keys = freqToKeys.get(minFreq); 
    K expireKey = keys.iterator().next();            
    //更新FK                                           
    keys.remove(expireKey);                          
    //如果keys                                         
    if (keys.isEmpty()) {                            
        freqToKeys.remove(minFreq);                  
    }                                                
    //更新KF                                           
    keyToFreq.remove(expireKey);                     
    //更新KV                                           
    keyToVal.remove(expireKey);                      
}                                                    

removeMinFreqKey方法中删除某个键key肯定是要同时修改三个映射表的,借助minFreq参数可以从FK表中找到freq最小的keyList,根据时序,其中第一个元素就是要被淘汰的deletedKey,操作三个映射表删除这个key即可。

但是有个细节问题,如果keyList中只有一个元素,那么删除之后minFreq对应的key列表就为空了,也就是minFreq变量需要被更新。如何计算当前的minFreq是多少呢?

实际上没办法快速计算minFreq,只能线性遍历FK表或者KF表来计算,这样肯定不能保证 O(1) 的时间复杂度。

但是,其实这里没必要更新minFreq变量,因为你想想removeMinFreqKey这个函数是在什么时候调用?在put方法中插入新key时可能调用。而你回头看put的代码,插入新key时一定会把minFreq更新成 1,所以说即便这里minFreq变了,我们也不需要管它。

3、总结

终于总结完了,其实,感觉思想搞明白了,代码实现起来就相对容易一些。但是,还是需要多写,多实践。过段时间再来回顾一下下面将源码贴出来:

package cache.lfu;

import cache.Cache;

import java.util.HashMap;
import java.util.LinkedHashSet;

/**
 * LFU(Least Frequently Used)最近最少使用算法。它是基于“如果一个数据在最近一段时间内使用次数很少,
 * 那么在将来一段时间内被使用的可能性也很小”的思路
 * 注意LFU和LRU算法的不同之处,LRU的淘汰规则是基于访问时间,而LFU是基于访问次数的。
 *
 * @author :huangxin
 * @modified :
 * @since :2020/09/01 08:19
 */
public class LFUCache<K, V> implements Cache<K, V> {

    /***缓存容量*/
    private int capacity;
    //key-value映射
    private HashMap<K, V> keyToVal;
    //key-freq映射
    private HashMap<K, Integer> keyToFreq;
    //freq-key映射
    private HashMap<Integer, LinkedHashSet<K>> freqToKeys;
    //key的最低频次
    private int minFreq;

    public LFUCache(int capacity) {
        this.capacity = capacity;
        keyToVal = new HashMap<>(capacity);
        keyToFreq = new HashMap<>(capacity);
        freqToKeys = new HashMap<>(capacity);
    }

    @Override
    public V get(K key) {
        if (keyToVal.containsKey(key)) {
            V val = keyToVal.get(key);
            //更新key
            updateFreq(key);
            return val;
        }
        return null;
    }

    private void updateFreq(K key) {
        //更新kF表
        Integer freq = keyToFreq.get(key);
        keyToFreq.put(key, freq + 1);
        //更新Fk表
        freqToKeys.get(freq).remove(key);
        freqToKeys.putIfAbsent(freq + 1, new LinkedHashSet<>());
        freqToKeys.get(freq + 1).add(key);
        if (freqToKeys.get(key).isEmpty()) {
            freqToKeys.remove(key);
            if (freq == minFreq) {
                minFreq++;
            }
        }
    }

    @Override
    public void put(K key, V val) {
        if (keyToVal.containsKey(key)) {
            //更新value
            keyToVal.put(key, val);
            //更新freq
            updateFreq(key);
            return;
        }
        if (keyToVal.size() >= this.capacity) {
            removeMinFreqKey();
        }
        //添加新的元素
        keyToVal.put(key, val);
        keyToFreq.put(key, 1);
        freqToKeys.putIfAbsent(1, new LinkedHashSet<>());
        freqToKeys.get(1).add(key);
        //插入新值后,最小的频次肯定是1
        this.minFreq = 1;
    }

    /**
     * 核心实现:移除频次最低并且时间最老的key
     */
    private void removeMinFreqKey() {
        LinkedHashSet<K> keys = freqToKeys.get(minFreq);
        K expireKey = keys.iterator().next();
        //更新FK
        keys.remove(expireKey);
        //如果keys
        if (keys.isEmpty()) {
            freqToKeys.remove(minFreq);
        }
        //更新KF
        keyToFreq.remove(expireKey);
        //更新KV
        keyToVal.remove(expireKey);
    }


    @Override
    public String toString() {
        return "LFUCache{" +
                "capacity=" + capacity +
                ", keyToVal=" + keyToVal.toString() +
                ", keyToFreq=" + keyToFreq.toString() +
                ", freqToKeys=" + freqToKeys.toString() +
                ", minFreq=" + minFreq +
                '}';
    }

    public static void main(String[] args) {
        // 构造一个容量为 3 的 LFU 缓存
        LFUCache cache = new LFUCache(3);

        // 插入两对 (key, val),对应的 freq 为 1
        cache.put(1, 10);
        cache.put(2, 20);
        cache.put(5, 50);

        System.out.println(cache);
        // 查询 key 为 1 对应的 val
        // 返回 10,同时键 1 对应的 freq 变为 2
        System.out.println(cache.get(1));
        System.out.println(cache);
        // 容量已满,淘汰 freq 最小的并且最老键 2
        // 插入键值对 (3, 30),对应的 freq 为 1
        cache.put(3, 30);
        System.out.println(cache);
        // 键 2 已经被淘汰删除,返回 -1
        System.out.println(cache.get(2));
        System.out.println(cache);
    }

}

参考

留言区

还能输入500个字符