LFU算法的Java代码实现

ゝ一纸荒年。 2023-10-09 20:26 61阅读 0赞

#### 算法简介 ####

算法基础解释，已经会的可以直接跳过哈。

LFU是最近不经常使用算法。
    
    听到这个名字，就问你迷糊不？
    还有个类似的叫LRU算法，叫最近最少使用算法。它的代码实现，本人实现了一波，有兴趣可以看下：
    https://juejin.cn/post/7226604941728841765
    
    好了，两者的应用场景基本一致，大多数都是缓存。
    本质上就是当我缓存的地方满了，现在又要添新的值，需要舍弃哪个旧值？
    LRU就是舍弃缓存数据中最后一次访问时间最早的数据。（注重时间）
    LFU即使舍弃访问次数最少的数据中最后一次访问时间最少的数据（注重次数+时间）
    
    什么？你还不懂？那我可要举例子了。
    复制代码

![format_png][]

玩过游戏吧，如果背包满了，现在又捡到了新的装备，所以要丢掉背包中的一个物品来放新的。
    LRU就是每捡到一个东西就放到背包最后面，然后过程中使用的也放在后面。这样我要扔东西就是直接扔最前面那一个就可以了。
    LFU就是：使用了两次的物品就是比使用1次的重要，我得先扔使用1次的。以此类推。如果多个相同次数，扔最后使用时间最早的
    你甚至可以理解为LFU就是先按照使用次数筛了下数据，再按照LRU选择
    复制代码

如何实现呢？

首先，既然先按照使用次数进行筛选，那么肯定要知道某个调用次数下都有哪些节点吧。
    所以数据结构是Map<调用次数，双向链表>。双向列表的原因是便于将某个节点删除。
    由于双向队列的实现是O（n）删除节点，所以一般是自行实现双端队列。
    同时添加新数据要放在队首，淘汰要从队尾拿，所以为了O(1),要维护到队头节点和队尾节点的映射。
    所以一般是采用两个Map来实现。
    
    其次，为了能够在O（1）时间内得到是否包含数据，还需要一个Map<key,Node>来维护数据。
    复制代码

综上：**为了实现O（1）的时间复杂度，总共需要3个Map。**

#### 逻辑分析 ####

1、get方法：相对简单。

![format_png 1][]

你看，是不是很清晰，很简单。QAQ

2、put方法：可以复用get方法。

![format_png 2][]

你看复用了后是不是也很简单。

![format_png 3][]

#### 代码实现 ####

你看，流程图有了，接下来就是编码能力了。

1、定义数据节点

class Node{
        String key;
        String value;
        //调用次数，小于0表示头尾节点
        Integer times;
        Node pre;
        Node next;
    
        Node(String key, String value, Integer times){
            this.key = key;
            this.value = value;
            this.times = times;
            pre = null;
            next = null;
        }
    }
    复制代码

解释下： key和value就不用了。 pre、next是双端队列的前后指针。 times:是当前节点的调用次数，目的是O（1）时间就能找到对应的双端队列的头尾节点。（因为每一个调用次数都会维护一个双端队列）

2、定义LFU的基本数据结构

public class LFUTest {
        //数据Map
        Map<String, Node> dataMap = new HashMap<>();
        //引用次数头节点
        Map<Integer, Node> headMap = new HashMap<>();
        //引用次数尾节点
        Map<Integer, Node> tailMap = new HashMap<>();
    
    
        int size = 0;
        int maxSize = 0;
        //最小引用次数
        int minCallTime = 1;
    
        LFUTest(int maxSize){
            this.maxSize = maxSize;
        }
    }
    复制代码

3、公告方法。从流程图可以看出，有的功能是重叠的，因此都抽出来

//创建某个引用次数的队列
    private void createCallTimeDeque(int callTime){
        Node head = new Node("head", "head", -1);
        Node tail = new Node("tail", "tail", -1);
        head.next = tail;
        tail.pre = head;
        headMap.put(callTime, head);
        tailMap.put(callTime, tail);
    }
    
    
    //判断引用次数的双向队列是否空，为空则删除，
    private void judgeAndDeleteCallTimeMap(int callTime){
        if(headMap.get(callTime).next == tailMap.get(callTime)){
            //只有head和tail（当然节点中也可以加字段表示是否是尾节点），说明队列已经空了,删除即可
            headMap.remove(callTime);
            tailMap.remove(callTime);
            //如果该引用次数刚好是最小引用次数，则最小引用次数+1
            if(callTime == minCallTime){
                minCallTime++;
            }
        }
    }
    
    //从双向链表上删除节点
    private void deleteNode(Node node){
        node.next.pre = node.pre;
        node.pre.next = node.next;
    }
    
    //把节点放到队首
    private void addHead(Node node, Node head){
        node.next = head.next;
        head.next = node;
        node.pre = head;
        node.next.pre = node;
    }
    复制代码

4、get方法

public Node get(String key){
        //数据Map中没key，说明没数据，直接返回null
        if(!dataMap.containsKey(key)){
            return null;
        }
        Node node = dataMap.get(key);
        //将数据从原来的双向队列中删除
        deleteNode(node);
    
        //获得原来的调用次数
        int callTime = node.times;
    
        //判断当前引用次数队列是否空,空则删除，同时变更最小引用数
        judgeAndDeleteCallTimeMap(callTime);
    
        callTime++;
        //将节点放入下一个调用次数的双向队列
        if(!headMap.containsKey(callTime)){
            //不存在下一个调用次数的双向队列，所以要创建
            createCallTimeDeque(callTime);
        }
        //将节点放入下一个调用次数的双向队列中
        addHead(node, headMap.get(callTime));
    
        //调用次数+1
        node.times ++;
        //完成，返回得到的数据即可
        return node;
    }
    复制代码

5、put方法

//存放数据
    public void put(String key, String value){
    
        if(dataMap.containsKey(key)){
            //如果数据中已经有了数据，和get操作一致，但要重新设置value值
            Node node = get(key);
            //Java引用传递，所以直接重新setValue值就行
            node.value = value;
            return;
        }
        //最大容量。
        if(size == maxSize){
            //达到最大容量，得删除一个(最小引用数队列的队尾节点）
            deleteNode(tailMap.get(minCallTime).pre);
            //判断
            judgeAndDeleteCallTimeMap(minCallTime);
            size--;
        }
    
        //判断引用为1的队列
        if(!headMap.containsKey(1)){
             //不存在，就创建
            createCallTimeDeque(1);
        }
        //创建封装数据
        Node data = new Node(key, value, 1);
        //将数据放在引用次数1的位置
        dataMap.put(key, data);
        addHead(data, headMap.get(1));
    
        //最小引用次数为1，总数+1
        minCallTime = 1;
        size++;
    
    }
    复制代码

#### 最终代码 ####

1、最终的主要代码，也不多啊，总共连回车也才150行嘛

![format_png 4][]

public class LFUTest {
        //定义节点
        class Node{
            String key;
            String value;
            //调用次数，小于0表示头尾节点
            Integer times;
            Node pre;
            Node next;
    
            Node(String key, String value, Integer times){
                this.key = key;
                this.value = value;
                this.times = times;
                pre = null;
                next = null;
            }
        }
    
        //数据Map
        Map<String, Node> dataMap = new HashMap<>();
        //引用次数头节点
        Map<Integer, Node> headMap = new HashMap<>();
        //引用次数尾节点
        Map<Integer, Node> tailMap = new HashMap<>();
    
    
        int size = 0;
        int maxSize = 0;
        //最小引用次数
        int minCallTime = 1;
    
        LFUTest(int maxSize){
            this.maxSize = maxSize;
        }
    
        //get
        public Node get(String key){
            //数据Map中没key，说明没数据，直接返回null
            if(!dataMap.containsKey(key)){
                return null;
            }
            Node node = dataMap.get(key);
            //将数据从原来的双向队列中删除
            deleteNode(node);
    
            //获得原来的调用次数
            int callTime = node.times;
    
            //判断当前引用次数队列是否空,空则删除，同时变更最小引用数
            judgeAndDeleteCallTimeMap(callTime);
    
            callTime++;
            //将节点放入下一个调用次数的双向队列
            if(!headMap.containsKey(callTime)){
                //不存在下一个调用次数的双向队列，所以要创建
                createCallTimeDeque(callTime);
            }
            //将节点放入下一个调用次数的双向队列中
            addHead(node, headMap.get(callTime));
    
            //调用次数+1
            node.times ++;
            //完成，返回得到的数据即可
            return node;
        }
    
        //存放数据
        public void put(String key, String value){
    
            if(dataMap.containsKey(key)){
                //如果数据中已经有了数据，和get操作一致，但要重新设置value值
                Node node = get(key);
                //Java引用传递，所以直接重新setValue值就行
                node.value = value;
                return;
            }
            //最大容量。
            if(size == maxSize){
                //达到最大容量，得删除一个(最小引用数队列的队尾节点）
                deleteNode(tailMap.get(minCallTime).pre);
                //判断
                judgeAndDeleteCallTimeMap(minCallTime);
                size--;
            }
    
            //判断引用为1的队列
            if(!headMap.containsKey(1)){
                 //不存在，就创建
                createCallTimeDeque(1);
            }
            //创建封装数据
            Node data = new Node(key, value, 1);
            //将数据放在引用次数1的位置
            dataMap.put(key, data);
            addHead(data, headMap.get(1));
    
            //最小引用次数为1，总数+1
            minCallTime = 1;
            size++;
    
        }
    
    
        //打印
        public void printAll(){
            System.out.println("-----");
            for(Integer callTime : headMap.keySet()){
                Node head = headMap.get(callTime);
                System.out.print(callTime+":");
                while(head != null){
                    System.out.print( "{"+head.key+","+head.value+"}");
                    head = head.next;
                }
                System.out.println();
            }
            System.out.println("*****");
        }
    
        //创建某个引用次数的队列
        private void createCallTimeDeque(int callTime){
            Node head = new Node("head", "head", -1);
            Node tail = new Node("tail", "tail", -1);
            head.next = tail;
            tail.pre = head;
            headMap.put(callTime, head);
            tailMap.put(callTime, tail);
        }
    
    
        //判断引用次数的双向队列是否空，为空则删除，
        private void judgeAndDeleteCallTimeMap(int callTime){
            if(headMap.get(callTime).next == tailMap.get(callTime)){
                //只有head和tail（当然节点中也可以加字段表示是否是尾节点），说明队列已经空了,删除即可
                headMap.remove(callTime);
                tailMap.remove(callTime);
                //如果该引用次数刚好是最小引用次数，则最小引用次数+1
                if(callTime == minCallTime){
                    minCallTime++;
                }
            }
        }
    
        //从双向链表上删除节点
        private void deleteNode(Node node){
            node.next.pre = node.pre;
            node.pre.next = node.next;
        }
    
        //把节点放到队首
        private void addHead(Node node, Node head){
            node.next = head.next;
            head.next = node;
            node.pre = head;
            node.next.pre = node;
        }
    
    }
    复制代码

2、这里贴下测试代码吧

public static void main(String[] args) {
        int data[] = new int[]{2,1,2,1,2,3,4};
    
        LFUTest lfuTest = new LFUTest(3);
    
        for(int i : data){
            if(lfuTest.get(i+"") == null){
                lfuTest.put(i+"", i+"v");
            }
            lfuTest.printAll();
        }
    
        lfuTest.put("4", "4+V");
        lfuTest.printAll();
    }
    复制代码

#### 小结 ####

LFU算法的实现主要是依靠3个Map，其中一个Map用来记录数据，一个Map记录调用次数和头节点的关系，便于直接在某个调用次数的队头插入数据。一个Map记录调用次数和尾节点的关系，便于直接将队尾的元素去除。

整体都是以空间换时间的思想。代码的复杂度为O（1），因此如果可以接受稍微高点的复杂度，那么可以将调用次数的两个Map合并成一个Deque，这样只有2个map，但是deque的常用实现类LinkedList在1.8时候删除Node是for遍历，所以删除的时间复杂度就是O（n）了；同理，如果接受get复杂度为O（n），那么可以去掉数据Map。

以上分析目的是让大家更了解为啥要用3个Map，实际场景中，一般都是追求时间复杂度而牺牲部分空间复杂度，所以基本是都是3个Map常用。

[format_png]: https://img-blog.csdnimg.cn/img_convert/3b97b0844c65f9f46c6b7f7e09c0ab6e.webp?x-oss-process=image/format,png
[format_png 1]: https://img-blog.csdnimg.cn/img_convert/e5ec0cbd053076ed3b64f1af3bce247c.webp?x-oss-process=image/format,png
[format_png 2]: https://img-blog.csdnimg.cn/img_convert/0dad546b00aefbbd0302df0c4e52d572.webp?x-oss-process=image/format,png
[format_png 3]: https://img-blog.csdnimg.cn/img_convert/ea48f1d98dc94f81609133b41022a5a5.webp?x-oss-process=image/format,png
[format_png 4]: https://img-blog.csdnimg.cn/img_convert/bbd16e8f4f32de926f6afb7e341ba937.webp?x-oss-process=image/format,png