LFU缓存结构

LFU

​ LFU (Least frequently used) 最不经常使用,如果一个数据在最近一段时间内使用次数很少,那么在将来一段时间内被使用的可能性也很小。实现一个LFU缓存结构需要实现如下功能:

  • set(key, value):将记录(key, value)插入该结构
  • get(key):返回key对应的value值

​ 但是缓存结构中最多放K条记录,如果新的第K+1条记录要加入,就需要根据策略删掉一条记录,然后才能把新记录加入。这个策略为:在缓存结构的K条记录中,哪一个key从进入缓存结构的时刻开始,被调用set或者get的次数最少,就删掉这个key的记录;

​ 如果调用次数最少的key有多个,上次调用发生最早的key被删除

​ 这就是LFU缓存替换算法。实现这个结构,K作为参数给出

[要求]

set和get方法的时间复杂度为O(1)

解决思路

​ 整体结构设计成发生set和get操作次数一样的key,都放在一个双向链表中(桶)。对于不同的操作次数,分别设置桶,然后桶和桶之间按照操作次数从小到大串起来,桶和桶之间也看作是一个双向链表。如下图所示:

LFU缓存结构

​ 该结构中,数据进行更新的规则是:

​ 当某一个key发生set和get时,来到key所在的位置,把key从原来的桶中去掉,也就是key的上一个节点和下一个节点直接相连,然后把key放在操作次数+1的桶中,

​ 如果没有次数+1的桶就新建,保证桶之间依然是双向链表的的链接;

​ 如果已经有次数加1的桶,就把key放在这个桶的头部

​ 如果key原来所在的桶中只有key这一条记录,就删除原来的桶,保证桶之间仍然是双向链表的链接。

​ 需要注意的是,桶和桶之间是双向链表,桶内部的的节点之间也是双向链表。本结构的难点在于,实现代码时需要维系桶之间、节点之间始终是双向链表这个关系。当结构中记录已经达到了k条,此时又有新的节点进来时,就需要删除一个节点,删除最左边的桶的尾节点即可。

​ 实现时需要借助两个map,第一个map的key和value分别是节点的key和节点对象node;第二个map的key和value分别是节点对象node和节点对象所在的桶NodeList。

实现代码

import java.util.HashMap;

public class LFUCache {

    private int capacity; // 缓存容量
    private int size; // 缓存中当前的节点数量
    private HashMap<Integer,Node> records;
    // 表示节点Node在哪个桶中
    private HashMap<Node,NodeList> heads;
    private NodeList headList; //整个结构中位于最左边的桶

    public LFU(int K){

        this.capacity = K;
        this.size = 0;
        this.records = new HashMap<>();
        this.heads = new HashMap<>();
        headList = null;
    }

    /**
     * 该函数的功能是:判断刚刚减少了一个节点的桶是否已经为空
     * 1、如果不为空,则什么也不做
     *
     * 2、如果为空,且removeNodeList是整个缓存结构中最左边的桶,则删除这个桶,同时让缓存结构
     * 中最左边的桶变为removeNodeList的下一个桶
     *
     * 3、如果为空,且removeNodeList不是整个缓存结构中最左边的桶,则删除这个桶,将removeNodeList前后的桶修改为
     * 直接双向连接
     * @param removeNodeList 表示刚刚减少了一个Node节点的桶
     * @return 返回值表示removeNodeList是否已经为空,空则返回true,否则返回false
     */
    private boolean modifyHeadList(NodeList removeNodeList){

        if (removeNodeList.isEmpty()){

            if (headList == removeNodeList){

                headList = removeNodeList.next;
                // 避免此时只有一个removeNodeList一个桶,而造成空指针异常
                if (headList != null){
                    headList.prev = null;
                }

            }else {

                removeNodeList.prev.next = removeNodeList.next;

                // 避免removeNodeList是最右边的桶,然后造成removeNodeList.next.prev产生空指针异常
                if (removeNodeList.next != null){
                    removeNodeList.next.prev = removeNodeList.prev;
                }
            }

            return true;
        }

        return false;
    }

    /**
     * 函数功能:当node节点的操作次数加1了,将这个节点从原来的桶中放入操作次数+1的桶中
     * 整个过程要保证桶之间仍然是双向链表,也要保证节点之间仍然是双向链表
     * @param node 要移动位置的节点
     * @param oldNodeList node未移动位置之前所在的桶
     */
    private void move(Node node,NodeList oldNodeList){

        oldNodeList.deleteNode(node);

        // preList表示操作次数加1的后对应的那个桶的前一个桶
        // 如果oldNodeList删除node之后,空了,此时需要将oldNodeList删掉,那么次数加1后对应的那个桶的前一个桶就是oldNodeList.prev
        // 如果oldNodeList删除node之后,不空,那么oldNodeList依然是次数加1后对应的那个桶的前一个桶
        NodeList preList = modifyHeadList(oldNodeList) ? oldNodeList.prev : oldNodeList;
		
        // nextList表示操作次数加1后对应的那个桶或者操作次数加1后的那个桶的下一个桶
        NodeList nextList = oldNodeList.next;

        if (nextList == null){

            NodeList newList = new NodeList(node);
            if (preList != null){
                preList.next = newList;
            }
            newList.prev = preList;

            if (headList == null){
                headList = newList;
            }
            heads.put(node,newList);

        }else {

            if (nextList.head.times == node.times){

                nextList.addNodeToHead(node);
                heads.put(node,nextList);

            }else {

                NodeList newList = new NodeList(node);
                if (preList != null){
                    preList.next = newList;
                }

                newList.prev = preList;
                newList.next = nextList;
                nextList.prev = newList;

                if (headList == nextList){
                    headList = newList;
                }

                heads.put(node,newList);
            }
        }

    }

    public void set(int key,int value){

        if (records.containsKey(key)){

            Node node = records.get(key);
            node.value = value;
            node.times ++;
            NodeList curNodeList = heads.get(node);
            move(node,curNodeList);
        }else {

            if (size == capacity){
                Node node = headList.tail;
                headList.deleteNode(node);
                modifyHeadList(headList);
                records.remove(node.key);
                heads.remove(node);
                size --;
            }

            Node node = new Node(key, value, 1);
            if (headList == null){

                headList = new NodeList(node);
            }else {

                if (headList.head.times == node.times){

                    headList.addNodeToHead(node);
                }else {

                    NodeList newList = new NodeList(node);
                    newList.next = headList;
                    headList.prev = newList;
                    headList = newList;
                }
            }
            records.put(key,node);
            heads.put(node,headList);
            size ++;
        }
    }

    public int get(int key){

        if (!records.containsKey(key)){
            return -1;
        }

        Node node = records.get(key);
        node.times ++;
        NodeList curNodeList = heads.get(node);
        move(node,curNodeList);
        return node.value;
    }

    /**
     * 节点的数据结构
     */
    class Node{

        public int key;
        public int value;
        public int times; // 该节点发生set和get的次数总和

        public Node next;
        public Node prev;

        public Node(int key,int value,int times){

            this.key = key;
            this.value = value;
            this.times = times;
        }
    }

    /**
     * 桶的数据结构
     */
    class NodeList{

        public Node head; // 指向桶的头节点的指针
        public Node tail; // 指向桶的尾节点的指针
        public NodeList next;
        public NodeList prev;

        // 初始化
        public NodeList(Node node){

            head = node;
            tail = node;
        }

        /**
         * 将一个新的节点加入桶中,新的节点作为桶中新的头节点
         * @param newNode
         */
        public void addNodeToHead(Node newNode){
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
        }

        /**
         * 删除Node节点并保证node的上下文环境重新连接
         * @param node
         */
        public void deleteNode(Node node){

            if (head == tail){
                head = null;
                tail = null;
            }else {

                if (head == node){

                    head = node.next;
                    head.prev = null;
                }else if (node == tail){

                    tail = node.prev;
                    tail.next = null;

                }else {

                    node.next.prev = node.prev;
                    node.prev.next = node.next;
                }
            }
            node.next = null;
            node.prev = null;
        }

        public boolean isEmpty(){

            return head == null;
        }

    }
}
上一篇:leetcode——对链表进行插入排序


下一篇:坏掉的项链(洛谷P1203题题解,C++语言描述)