算法笔记——LRU和LFU缓存结构

LRU缓存结构

问题描述：

设计可以变更的缓存结构（LRU）
【题目】
设计一种缓存结构，该结构在构造时确定大小，假设大小为K，并有两个功能：
set(key,value)：将记录(key,value)插入该结构。
get(key)：返回key对应的value值。
【要求】
1．set和get方法的时间复杂度为O(1)。
2．某个key的set或get操作一旦发生，认为这个key的记录成了最经常使用的。
3．当缓存的大小超过K时，移除最不经常使用的记录，即set或get最久远的。
【举例】
假设缓存结构的实例是cache，大小为3，并依次发生如下行为：
1．cache.set("A",1)。最经常使用的记录为("A",1)。
2．cache.set("B",2)。最经常使用的记录为("B",2)，("A",1)变为最不经常的。
3．cache.set("C",3)。最经常使用的记录为("C",2)，("A",1)还是最不经常的。
4．cache.get("A")。最经常使用的记录为("A",1)，("B",2)变为最不经常的。
5．cache.set("D",4)。大小超过了3，所以移除此时最不经常使用的记录("B",2)，
加入记录 ("D",4)，并且为最经常使用的记录，然后("C",2)变为最不经常使用的
记录

分析问题

• 简单分析LRU结构需要以下几个功能
• 必须有明确的大小K，可在构造方法中传入
• set方法为键值对的形式，所以必须准备HasnMap，才能使得set和get方法的时间复杂度为O(1);
• 调整某个key成为最经常用的节点，所以可以维护一个关于value的双向链表，那么这里直接做一个Node节点，value作为他的属性之一。
• 当大小超载时，移除最不经常使用的，假设双端链表尾部就是最经常使用的节点，双端链表头部最不进场使用，所以这里直接把头节点删掉就可以了
• 一旦对一个节点进行修改了，那么需要将修改的节点移动到双端聊表尾部。

代码

    static class Node<V>{
        V value;
        Node<V> last;
        Node<V> next;

        public Node(V value) {
            this.value = value;
        }
    }

    static class DoubleLinkedList<V>{
        Node<V> head;
        Node<V> tail;

        public DoubleLinkedList(){
            this.head = null;
            this.tail = null;
        }

        // 添加一个节点
        void addNode(Node node){
            if(head == null){
                this.head = node;
                this.tail = node;
            }else{
                this.tail.next = node;
                node.last = this.tail;
                this.tail = node;
            }
        }

        // 将某个节点node移动到链表尾部
        void moveNodeToTail(Node node){
            if(this.tail == node){
                return;
            }
            if(this.head == node){
                this.head = node.next;
                this.head.last = null;
            }else{
                node.last.next = node.next;
                node.next.last = node.last;
            }
            node.last = this.tail;
            node.next = null;
            this.tail.next = node;
            this.tail = node;
        }

        // 移除双向链表的头节点
        Node<V> removeHeadNode(){
            if(this.head == null) {
                return null;
            }
            Node<V> res = this.head;
            if(this.head == this.tail){
                this.head = null;
                this.tail = null;
            }else{
                this.head = res.next;
                res.next = null;
                this.head.last = null;
            }
            return res;
        }
    }

    public static class MyCache<K,V>{
        HashMap<K,Node<V>> keyNodeMap;
        HashMap<Node<V>,K> valueKeyMap;
        DoubleLinkedList<V> nodeList;
        int capacity;

        public MyCache(int capacity) {
            if(capacity < 1){
                throw new RuntimeException("容量不可以小于1");
            }
            this.capacity = capacity;
            this.keyNodeMap = new HashMap<>();
            this.valueKeyMap = new HashMap<>();
            this.nodeList = new DoubleLinkedList<>();
        }

        // 根据指定的K获取value
        public V get(K key){
            if(this.keyNodeMap.containsKey(key)){
                Node<V> res = this.keyNodeMap.get(key);
                this.nodeList.moveNodeToTail(res);
                return res.value;
            }
            return null;
        }
        
        // 向缓存结构中添加键值对
        public void set(K key,V value){
            if(this.keyNodeMap.containsKey(key)){
                Node<V> cur = this.keyNodeMap.get(key);
                cur.value = value;
                this.nodeList.moveNodeToTail(cur);
            }else{
                Node<V> temp = new Node<V>(value);
                this.keyNodeMap.put(key,temp);
                this.valueKeyMap.put(temp,key);
                this.nodeList.addNode(temp);
                if(this.keyNodeMap.size() == this.capacity + 1){
                    Node<V> removeValue = this.nodeList.removeHeadNode();
                    K removeKey = this.valueKeyMap.get(removeValue);
                    this.keyNodeMap.remove(removeKey);
                    this.valueKeyMap.remove(removeValue);
                }
            }
        }
    }

LFU缓存结构

LeetCode | 460. LFU缓存

题目描述

请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。它应该支持以下操作：get 和 put。
- get(key) - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。
- put(key, value) - 如果键已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最近 最少使用的键。
【项的使用次数】就是自插入该项以来对其调用 get 和 put 函数的次数之和。使用次数会在对应项被移除后置为 0 。

基本思路

• 同LRU结构，将键值对存储在Node节点中。
• 创建一个双向链表，链表中每一个位置都是一个双向链表，所有具有相同操作次数的节点node放在同一个位置重新构成双向链表
• 所以当插入一个元素时，如果该元素存在，则需要将其操作次数加1，然后将其添加到大链表的新的位置中；如果不存在，则创建该节点，默认操作次数为1
• 获取一个元素时，该Node的操作次数也加1，然后调整到大链表新的位置
• 剩下的问题就是扣边界了。

代码

// 首先定义节点类型
class Node{
    int key;
    int value;
    int times;
    Node up;
    Node down;

    public Node(int key, int value, int times){
        this.key = key;
        this.value = value;
        this.times = times;
    }
}

//定义NodeList类，LFU包含一个由NodeList构成的双端链表
class NodeList{
    Node head;
    Node tail;
    NodeList last;
    NodeList next;

    public NodeList(Node node){
        this.head = node;
        this.tail = node;
    }

    // 将一个节点node插入此nodeList的头步
    public void addNodeFromHead(Node newNode){
        newNode.down = this.head;
        this.head.up = newNode;
        this.head = newNode;
    }

    // 判断当前的nodeList是否为null
    public boolean isEmpty(){
        return this.head == null;
    }

    // 从当前的nodeList中删除一个node
    public void deleteNode(Node node){
        if(this.head == this.tail){
            this.head = null;
            this.tail = null;
        }else{
            if(this.head == node){
                this.head = node.down;
                this.head.up = null;
            }else if(this.tail == node){
                this.tail = node.up;
                this.tail.down = null;
            }else{
                node.up.down = node.down;
                node.down.up = node.up;
            }
        }
        node.up = null;
        node.down = null;
    }
}

class LFUCache {
    // 定义成员变量
    int capacity;
    int size;
    HashMap<Integer,Node> records;
    HashMap<Node,NodeList> heads;
    NodeList headList;

    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.records = new HashMap<Integer,Node>();
        this.heads = new HashMap<Node,NodeList>();
        this.headList = null;
    }
    
    public int get(int key) {
        int res  = -1;
        if(records.containsKey(key)){
            Node node = records.get(key);
            res = node.value;
            node.times++;
            NodeList curNodeList = heads.get(node);
            move(node,curNodeList);
        }
        return res;
    }
    
    public void put(int key, int value) {
        if(this.capacity == 0) {
            return;
        }
        // 如果当前的key指向的节点存在
        if(records.containsKey(key)){
            Node node = records.get(key);
            node.value = value;
            node.times++;
            NodeList curNodeList = heads.get(node);  // 获取当前的node存在的NodeList
            move(node,curNodeList);    // 将node移动到新的NodeList中，并调正curNodeList
        }
        // 如果当前的key指向的节点不存在
        else{
            //r如果容量超限
            if(this.size == this.capacity){
                //删除headList的tail
                Node tail = this.headList.tail;
                this.headList.deleteNode(tail);
                modifyHeadList(this.headList); // 更新当前的headList，如果为null调整
                records.remove(tail.key);
                heads.remove(tail);
                this.size--;
            }
            // 创建新的Node进行插入
            Node node = new Node(key,value,1);
            if(this.headList == null){
                this.headList = new NodeList(node);
            }else{
                if(this.headList.head.times == node.times){
                    this.headList.addNodeFromHead(node);
                }else{
                    NodeList newList = new NodeList(node);
                    newList.next = this.headList;
                    this.headList.last = newList;
                    this.headList = newList;
                }
            }
            records.put(key,node);
            heads.put(node,this.headList);
            this.size++;
        }
    }

    private void move(Node node, NodeList oldNodeList){
        // 首先从原来的NodeList中删除node节点
        oldNodeList.deleteNode(node);
        NodeList preList = modifyHeadList(oldNodeList) ? oldNodeList.last : oldNodeList;  // 调整oldNodeList
        NodeList nextList = oldNodeList.next;
        if(nextList == null){
            // 新建一个Nodelist,把node扔进去
            NodeList newList = new NodeList(node);
            if(preList != null){
                preList.next = newList;
            }
            newList.last = preList;
            if(this.headList == null){
                this.headList = newList;
            }
            heads.put(node,newList);
        }else{
            if(nextList.head.times == node.times){
                // 将node放到头步
                nextList.addNodeFromHead(node);
                heads.put(node,nextList);
            }else{
                NodeList newList =  new NodeList(node);
                if(preList != null){
                    preList.next = newList;
                }
                newList.last = preList;
                newList.next = nextList;
                nextList.last = newList;
                if(this.headList == nextList){
                     this.headList = newList;
                }
                heads.put(node,newList);
            }
        }
    }

    private boolean modifyHeadList(NodeList nodeList){
        // 如果当前的nodeList为null，则要进行删除
        if(nodeList.isEmpty()){
            if(this.headList == nodeList){
                this.headList = nodeList.next;
                if(this.headList != null){
                    this.headList.last = null;
                }
            }else{
                nodeList.last.next = nodeList.next;
                if(nodeList.next != null){
                    nodeList.next.last = nodeList.last;
                }
            }
            return true;
        }
        //否则返回false
        return false;
    }
}