欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LRU缓存

程序员文章站 2022-07-15 16:57:47
...

一、什么是LRU算法

LRU,Least Recently Used算法,即一种缓存淘汰策略。

计算机的缓存容量有限,若缓存满了则需要删除一些内容,给新的缓存腾出空间,但问题是要删除哪些内容呢?当然是把用的少的缓存删掉,把最有用的数据继续保留以便于继续使用。那么如何判定哪些数据是有用的呢?

缓存淘汰的策略有很多,而LRU则是一种较为简单常用的算法,LRU判定最近使用过的数据为有用的,很久都没用过的数据是无用的,在内存满了就优先删除很久未使用,也就是无用的数据。

常见的场景如手机的后台运行缓存,我们依次打开了[设置] [网易云音乐] [优酷视频] [bilibili],假设手机只允许同时打开个应用程序,那么在我们打开bilibili的那一刻,就会将最久未使用的 [设置] 关闭,腾出空间给 [bilibili]

 

二、LRU的算法描述

①接收一个capacity的参数作为缓存的最大容量

②实现put(key,value)方法存入键值对

③实现get(key)方法获取key对应的value,若不存在返回-1

//缓存容量为2
LRUCache cache = new LRUCache(2);
//可以把cache理解为一个队列
//最近使用过的在队列头,久未使用的在队列尾

cache.put(1,1);//cache = [(1,1)]

cache.put(2,2);//cache = [(2,2),(1,1)]

cache.get(1);//此时访问了key为1的entry 因此将其移动到队列头 cache = [(1,1),(2,2)]

cache.put(3,3);//此时容量已满,需要删除久未使用的数据,也就是队列尾 然后插入新的数据 cache = [(3,3),(1,1)]

cache.get(2);//return -1

cache.put(1,4);//key=1已经存在,只需要覆盖value即可 且此时需要将更新的entry提前到队列头 cache = [(1,4),(3,3)]

 

三、LRU算法设计

要让LRUCache的put和get方法时间复杂度为O(1),那么要求数据结构的查询时间为O(1),插入时间为O(1),删除时间为O(1),且有序。

为了区分最近使用和久未使用的数据,我们必须要求cache有序;能够在cache中判断key是否存在;cache容量满了需要删除最后一个entry;每次访问的entry都重新放在队列头部。

为此我们可以考虑到HashMap与LinkedList的结合——LinkedHashMap

LRU缓存算法的核心就是基于LinkedHashMap实现的,其核心就是通过HashMap赋予链表查询迅速的特性

LRU缓存(图片来源LeetCode)

 

四、代码实现

首先将双向链表实现

class DoubleLinkedList {
    class Entry{
        int key;
        int value;
        Entry prev;
        Entry next;

        Entry(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private Entry head;

    private Entry tail;

    private int size;

    public LRUCache() {
        //缓存初始化
        head = new Entry(0,0);
        tail = new Entry(0,0);
        head.next = tail;
        tail.prev = head;
        int size = 0;
    }

    //在链表首部添加entry
    public void addFirst(Entry entry) {
        entry.next = head.next;
        entry.prev = head;
        head.next.prev = entry;
        head.next = entry;
        size++;
    }

    //删除链表中的entry
    public void remove(Entry entry) {
        Entry prev = entry.prev;
        Entry next = entry.next;
        prev.next = next;
        next.prev = prev;
        size--;
    }

    //删除链表中最后一个节点并返回
    public Entry removeLast() {
        if (tail.prev == head) {
            return null;
        }
        Entry last = tail.prev;
        remove(last);
        return last;
    }

    public int size() {
        return size;
    }
}

然后结合HashMap即可:

public class LRUCache {
    private HashMap<Integer, DoubleLinkedList.Entry> map;

    private DoubleLinkedList cache;

    private int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        cache = new DoubleLinkedList();
    }

    public int get(int key) {
        //若map中不存在cache映射的key return -1
        if (!map.containsKey(key)) {
           return -1;
        }
        int val = map.get(key).value;
        //将get过的entry提前,put方法直接采用了删除尾部,首部添加的策略。
        put(key,val);
        return val;
    }

    public void put(int key, int val) {
        DoubleLinkedList.Entry x = new DoubleLinkedList.Entry(key,val);
        if (map.containsKey(key)) {
            //可以理解为缓存队列尾部删除 首部添加
            cache.remove(map.get(key));
            cache.addFirst(x);

            //map中添加该entry的映射
            map.put(key,x);
        } else {
            //当缓存已满,不仅要删除最后一个Entry,还要把map中映射到该节点的key同时删除,而这个key只能通过Entry得到。
            if(capacity == cache.size()) {
                //删除链表最后一个数据
                DoubleLinkedList.Entry last = cache.removeLast();
                map.remove(last.key);
            }
            cache.addFirst(x);
            map.put(key,x);
        }
    }
}

以上就是LRU的简单实现,

原文参考LeetCode:https://leetcode-cn.com/problems/lru-cache/solution/lru-ce-lue-xiang-jie-he-shi-xian-by-labuladong/

放个源码:https://github.com/whl-1998/DataStructAndAlgorithm/tree/master/src/com/whl