LFU算法的Java代码实现

算法简介

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

LFU是最近不经常使用算法。

听到这个名字，就问你迷糊不？
还有个类似的叫LRU算法，叫最近最少使用算法。它的代码实现，本人实现了一波，有兴趣可以看下：
https://juejin.cn/post/7226604941728841765

好了，两者的应用场景基本一致，大多数都是缓存。
本质上就是当我缓存的地方满了，现在又要添新的值，需要舍弃哪个旧值？
LRU就是舍弃缓存数据中最后一次访问时间最早的数据。（注重时间）
LFU即使舍弃访问次数最少的数据中最后一次访问时间最少的数据（注重次数+时间）

什么？你还不懂？那我可要举例子了。

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

如何实现呢？

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

其次，为了能够在O（1）时间内得到是否包含数据，还需要一个Map<key,Node>来维护数据。

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

逻辑分析

1、get方法：相对简单。

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

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

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

代码实现

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

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行嘛

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常用。