手动实现 LFU 缓存策略算法

我不是女神ヾ 2022-11-14 10:27 134阅读 0赞

今天分享手动实现 LFU 缓存策略算法：

LFU简介：

redis 中除了有LRU算法外，还有一个缓存策略叫做LFU， 那么LFU是什么呢？

## 一、LFU是什么 ##

LFU，全称是:Least Frequently Used，最不经常使用策略，在一段时间内，数据被使用频次最少的，优先被淘汰。最少使用（LFU）是一种用于管理计算机内存的缓存算法。主要是记录和追踪内存块的使用次数，当缓存已满并且需要更多空间时，系统将以最低内存块使用频率清除内存.采用LFU算法的最简单方法是为每个加载到缓存的块分配一个计数器。每次引用该块时，计数器将增加一。当缓存达到容量并有一个新的内存块等待插入时，系统将搜索计数器最低的块并将其从缓存中删除(本段摘自维基百科)

原理图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70][]

上面这个图就是一个LRU的简单实现思路，在链表的开始插入元素，然后每插入一次计数一次，接着按照次数重新排序链表，如果次数相同的话，按照插入时间排序，然后从链表尾部选择淘汰的数据~

## 二、LFU实现 ##

2.1 定义Node节点

Node主要包含了key和value，因为LFU的主要实现思想是比较访问的次数，如果在次数相同的情况下需要比较节点的时间，越早放入的越快      被淘汰，因此我们需要在Node节点上加入time和count的属性，分别用来记录节点的访问的时间和访问次数。其他的版本实现方式里有新加个内部类来记录 key的count和time，但是我觉得不够方便，还得单独维护一个map，成本有点大。还有一点注意的是这里实现了comparable接口，覆写了compare方法，这里 的主要作用就是在排序的时候需要用到，在compare方法里面我们首先比较节点的访问次数，在访问次数相同的情况下比较节点的访问时间，这里是为了 在排序方法里面通过比较key来选择淘汰的key

/**
     * 节点内部类
     */
    public static class Node implements Comparable<Node>{
        Object key;//键
        Object value;//值
        long time;//更新时间
        int count;//查询次数
        public Node(Object key,Object value, long time,int count){
            this.key = key;
            this.value = value;
            this.time = time;
            this.count = count;
        }
        public Object getKey() {
            return key;
        }
        public void setKey(Object key) {
            this.key = key;
        }
        public Object getValue() {
            return value;
        }
        public void setValue(Object value) {
            this.value = value;
        }
        public long getTime() {
            return time;
        }
        public void setTime(long time) {
            this.time = time;
        }
        public int getCount() {
            return count;
        }
        public void setCount(int count) {
            this.count = count;
        }
        /**
         * 实现的比较方法
         * @param o
         * @return
         */
        @Override
        public int compareTo(Node o) {
            int compare = Integer.compare(this.count, o.count);
            if(compare == 0){
                return Long.compare(this.time,o.time);
            }
            return compare;
        }
    }

2.2:定义LFU类

定义LFU类，这里采用了泛型，声明了K和V，还有总容量和一个Map(caches)用来维护所有的节点。在构造方法里将size传递进去，并且创建了一个LinkedHashMap，采用linkedHashMap的主要原因是维护key的顺序

public class NandaoLfuLinkedList<K,V> {
    
        private int capacity;//容量
        private Map<K,Node> caches;//本地缓存
    
        //构造方法
        public NandaoLfuLinkedList(int size){
            this.capacity = size;
            caches = new LinkedHashMap<K,Node>(size);
        }
    }

2.3: 添加元素

添加元素的逻辑主要是先从缓存中根据key获取节点，如果获取不到，证明是新添加的元素，然后和容量比较，大于预定容量的话，需要找出count计数最小(计数相同的情况下，选择时间最久)的节点，然后移除掉那个。如果在预定的大小之内，就新创建节点，注意这里不能使用 System.currentTimeMillis()方法，因为毫秒级别的粒度无法对插入的时间进行区分，在运行比较快的情况下，只有System.nanoTime()才可以将key的插入时间区分，默认设置count计数为1.如果能获取到，表示是旧的元素，那么就用新值覆盖旧值，计数+1，设置key的time为当前纳秒时间。最后还需要进行排序，这里可以看出插入元素的逻辑主要是添加进入缓存，更新元素的时间和计数~

/**
     * 新加数据的方法
     * @param key
     * @param value
     */
    public void put(K key,V value){
        Node node = caches.get(key);
        if(node == null){
            if(caches.size()>=capacity){
                K leastKey = removeLeastCount();
                caches.remove(leastKey);
            }
            node = new Node(key,value,System.nanoTime(),1);
            caches.put(key,node);
        }else {
            node.value = value;
            node.setCount(caches.size()+1);
            node.setTime(System.nanoTime());
        }
        sort();
    }

删除次数最少的方法：

淘汰最小的元素这里调用了Collections.min方法，然后通过比较key的compare方法，找到计数最小和时间最长的元素，直接从缓存中移除~

/**
     * 排序方法
     */
    private void sort() {
        List<Map.Entry<K,Node>> list = new ArrayList<>(caches.entrySet());
        Collections.sort(list, new Comparator<Map.Entry<K, Node>>() {
            @Override
            public int compare(Map.Entry<K, Node> o1, Map.Entry<K, Node> o2) {
                return o2.getValue().compareTo(o1.getValue());
            }
        });
        caches.clear();//先删除缓存
        //重新赋值
        for(Map.Entry<K,Node> kNodeEntry : list){
            caches.put(kNodeEntry.getKey(),kNodeEntry.getValue());
        }
    }

排序方法：

每次put或者get元素都需要进行排序，排序的主要意义在于按照key的cout和time进行一个key顺序的重组，这里的逻辑是首先将缓存map创建成一个list，然后按照Node的value进行，重组整个map。然后将原来的缓存清空，遍历这个map， 把key和value的值放进去原来的缓存中的顺序就进行了重组~这里区分于LRU的不同点在于使用了java的集合API，LRU的排序是进行节点移动。而在LFU中实现比较复杂，因为put的时候不光得比较基数还有时间。如果不借助java的API的话，可以新维护一个节点频率链表，每次将key保存在这个节点频率链表中移动指针，从而也间接可以实现排序~

/**
     * 删除访问量最小的数据
     * @return
     */
    private K removeLeastCount() {
        Collection<Node> values = caches.values();
        Node min = Collections.min(values);
        return (K)min.getKey();
    }

2.4:获取元素

获取元素首先是从缓存map中获取，否则返回null，在获取到元素之后需要进行节点的更新，计数+1和刷新节点的时间，根据LFU的原则，在当前时间获取到这个节点以后，这个节点就暂时变成了热点节点，但是它的cout计数也有可能是小于某个节点的count的，所以

此时不能将它直接移动到链表顶，还需要进行一次排序，重组它的位置~

/**
     * 查询数据的方法
     * @param key
     * @return
     */
    public V get(K key){
        Node node = caches.get(key);
        if(node != null){
            node.setTime(System.nanoTime());
            node.setCount(node.getCount()+1);
            sort();
            return (V)node.value;
        }
        return null;
    }

2.5测试方法：

//测试方法
    public static  void main(String[] args) {
        NandaoLfuLinkedList<Integer, String> lruCache = new NandaoLfuLinkedList<>(3);
        lruCache.put(1, "A");
        lruCache.put(2, "B");
        lruCache.put(3, "C");
        //lruCache.get(3);
        lruCache.get(2);
      //  lruCache.get(3);
     //   lruCache.get(3);
     //   lruCache.get(1);
      //  lruCache.put(4, "D");
      /*  lruCache.put(4, "D");
        lruCache.put(5, "E");
        lruCache.put(6, "F");*/
    
        //   lruCache.get(1);
        //  lruCache.put(7, "G");
           /* lruCache.get(2);
        lruCache.get(3);
        lruCache.get(6);*/
        //重新put节点3
        //  lruCache.put(3,"C");
    
        final Map<Integer, Node> caches = (Map<Integer, Node>) lruCache.caches;
        for (Map.Entry<Integer, Node> nodeEntry : caches.entrySet()) {
            System.out.print(nodeEntry.getValue().value+" ");
        }
    }

测试图解：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 1][]

执行结果：

![20210328224413682.png][]

到此LFU算法分享完毕，大家多测试、多练习定会很快熟悉！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70]: /images/20221022/d4dcf5d76fb64e46b9cdf0b8f5909547.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210328224739876.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA==,size_16,color_FFFFFF,t_70
[20210328224413682.png]: https://img-blog.csdnimg.cn/20210328224413682.png