手写 LRU 算法

2022-10-27 12:07:51

定义

缓存的本质是以空间换时间，那么缓存的容量大小肯定是有限的，当缓存被占满时，缓存中的那些数据应该被清理出去，那些数据应该被保留呢？这就需要缓存的淘汰策略来决定。

事实上，常用的缓存的淘汰策略有三种：先进先出算法(First in First out FIFO)；淘汰一定时期内被访问次数最少的页面(Least Frequently Used LFU)；淘汰最长时间未被使用的页面(Least Recently Used LRU)

这些算法在不同层次的缓存上执行时具有不同的效率，需要结合具体的场景来选择。

FIFO算法

FIFO算法即先进先出算法，常采用队列实现。在缓存中，它的设计原则是：如果一个数据最先进入缓存中，则应该最早淘汰掉

新访问的数据插入FIFO队列的尾部，队列中数据由队到队头按顺序顺序移动
队列满时，删除队头的数据

LRU 算法

LRU算法是根据对数据的历史访问次数来进行淘汰数据的，通常使用链表来实现。在缓存中，它的设计原则是：如果数据最近被访问过，那么将来它被访问的几率也很高。

步骤：

新加入的数据插入到链表的头部
每当缓存命中时(即缓存数据被访问)，则将数据移到链表头部
当来链表已满的时候，将链表尾部的数据丢弃

LFU算法

LFU 算法是根据数据的历史访问频率来淘汰数据，因此，LFU算法中的每个数据块都有一个引用计数，所有数据块按照引用计数排序，具有相同引用计数的数据块则按照时间排序。在缓存中，它的设计原则是：如果数据被访问多次，那么将来它的访问频率也会更高。
步骤：

新加入数据插入到队列尾部（引用计数为1；
队列中的数据被访问后，引用计数增加，队列重新排序；
当需要淘汰数据时，将已经排序的列表最后的数据块删除。

基础数据结构

维护一个双向链表，保存所有缓存的值，并且最老的值放在链表最后面。
当访问的值在链表中时： 将找到链表中值将其删除，并重新在链表头添加该值（保证链表中数值的顺序是从新到旧）
当访问的值不在链表中时： 当链表已满：删除链表最后一个值，将要添加的值放在链表头当链表未满：直接在链表头添加

LRU的具体实现

利用双向链表与散列表的结合：

双向链表支持查找前驱，保证操作的时间复杂度为O(1)
引入散列表记录每个数据的位置，将缓存访问的时间复杂度降到O(1)

具体思路

哈希表用于满足题目时间复杂度 O(1) 的要求，双向链表用于存储顺序
哈希表键值类型：<Integer, ListNode>，哈希表的键用于存储输入的 key，哈希表的值用于存储双向链表的节点
双向链表的节点中除了 value 外还需要包含 key ，因为在删除最久未使用的数据时，需要通过链表来定位 hashmap 中应当删除的键值对
一些操作：双向链表中，在后面的节点表示被最近访问
- 新加入的节点放在链表末尾，addNodeToLast(node)
- 若容量达到上限，去除最久未使用的数据，removeNode(head.next)
- 若数据新被访问过，比如被 get了或被 put了新值，把该节点挪到链表末尾，moveNodeToLast(node)
为了操作的方便，在双向链表头和尾分别定义一个head和tail节点。

代码实现

import java.util.HashMap;
//定义LIstNode
class ListNode{
    int key;
    int val;
    ListNode pre;
    ListNode next;
    public ListNode(){

    }
    public ListNode(int key,int val){
        this.key = key;
        this.val = val;
    }
}
public class LRU {
        private int capacity;
        public HashMap<Integer,ListNode> hashMap;
        //定义的双向链表
        public   ListNode head;
        public   ListNode tail;

        //定义构造函数，初始化变量
        public LRU(int capacity){
            this.capacity = capacity;
            head = new ListNode();
            tail = new ListNode();
            head.next = tail;
            tail.pre = head;
            hashMap = new HashMap<>();
        }
        //链表操作：删除某个节点
        private void removeNode(ListNode listNode){
//                listNode.pre = listNode.next;
                listNode.pre.next = listNode.next;
                listNode.next.pre = listNode.pre;

        }
        //链表操作：添加新的节点，添加到最后
        private  void appednList(ListNode listNode){
            //将其添加到我们的虚拟列表的表尾部
            tail.pre.next = listNode;
            listNode.pre = tail.pre;
            listNode.next = tail;
            tail.pre = listNode;
        }
        //链表：将节点从当前位置移动到链表最后
        private  void  moveNode(ListNode listNode){

                removeNode(listNode);
                appednList(listNode);
        }
        //redisCache操作_get 指定 key 节点
        public  int get(int key){
                if(hashMap.containsKey(key)){
                    ListNode listNode = hashMap.get(key);
                    //调整list Node 的位置
                    moveNode(listNode);
                    return listNode.val;
                }else{
                    return -1;
                }
        }
        //想象为 redis 中的 put 操作
        public  void put(int key,int value){
            if(hashMap.containsKey(key)){
                ListNode listNode = hashMap.get(key);
                listNode.val = value;
                moveNode(listNode);
            } else {
                if(hashMap.size()==this.capacity){
                    //此时缓存区已满，需要进行刷新删除那些不需要的
                    //LRU删除最前面的即可
                    hashMap.remove(head.next);
                    removeNode(head.next);
                }
                //满了就 flush 后添加，没满就直接添加
                ListNode listNode = new ListNode(key,value);
                hashMap.put(key,listNode);
                appednList(listNode);



            }
        }

}

测试代码：

import java.util.HashMap;

public class LRUTest {
    public static void showHashMap(ListNode head){
        ListNode node= head.next;
        System.out.println("===================");
        while(node!=null && node.key!=0){
            System.out.println(""+node.key+":"+node.val);
            node = node.next;
        }

    }
    public static void main(String[] args) {
        LRU lurCache = new LRU(5);
        lurCache.put(1,1);
        lurCache.put(2,2);
        lurCache.put(3,3);
        lurCache.put(4,4);
        lurCache.put(5,5);
        showHashMap(lurCache.head);

        lurCache.put(1,10);
        showHashMap(lurCache.head);

        lurCache.put(6,6);
        showHashMap(lurCache.head);
    }
}

码农公寓

定义