数据结构算法---LRU缓存


  • LRU缓存是什么?

  1. LRU算法就是一种缓存淘汰策略,其他常见的缓存淘汰策略有这几种:

    • FIFO(First in first out): 先进先出式的淘汰机制,队列式的
    • LRU(Least recently used):最近最少使用的,将很长时间没有使用过的淘汰掉
    • LFU(Least frequently used):计算每个信息的访问次数,踢走访问次数最少的那个;如果访问次数一样,就踢走好久没用过的那个
  2. 缓存是什么以及为什么要使用缓存

    • 缓存的目的:
      • 1.提升速度。将一些需要频繁访问的数据存放在高速缓存中,可以在需要的时候快速获取到
      • 2.通过缓存一些变化频率较小的数据,来减少对数据请求方的访问次数,减少服务器的请求压力。
    • 为什么需要上述的LRU等缓存策略?
        因为现实中各个服务的资源都是有限的,不断堆积的数据缓存会占用大量的服务器空间,因此需要采取一些策略来释放资源以用来承载新到来的需要缓存的数据,以支持服务长期稳定的运行
    • 有哪些方式实现数据缓存?
      • 1.使用JDK或者其他框架所提供的容器类,在服务器内存中缓存数据
      • 2.通过一些NOSql数据库服务进行缓存,不会占用当前服务器的资源。如:redis,elastic等
      • 3.可以使用一些开源的已经封装好的缓存框架帮助我们更好的使用缓存。如:Spring的springCache,Alibaba开源的JetCache等

  • 实现LRU缓存需要实现哪些功能?

  1. 作为缓存最基本的操作就是能够将数据写入和读取数据,最好这两种操作都能在O(1)的时间复杂度完成;
  2. get()操作读取数据没什么好说的:当前key存在则返回数据,不存在则返回-1;
  3. 写入数据时的put操作逻辑如下:


    put操作.png

  • 实现上述功能需要什么样的数据结构支撑?

  1. 在O(1)的时间复杂度内实现get操作: 使用HashMap来存储KV数据
  2. put()操作需要对加入的value标记其加入的顺序,且需要在O(1)的复杂度内完成数据的删除以及将其标记为最新访问的元素。
  • 元素有序:使用链表可以规定元素头插或者尾插,从而使新插入的元素或者最近访问的元素存放在链表头或链表尾部来保证链表中元素的顺序
  • 在较短时间内实现链表的删除:链表中删除一个节点时不仅要有该节点的指针,还需要该节点前驱结点的指针,因次可以采用双向链表DoubleLinkedList来实现O(1)的删除操作。
  因此,我们可以采用哈希表和双向链表结合来实现LRU缓存。

  Java中已经对拥有上述特性的类作了专门的封装,即java.util.LinkedHashMap类。(方法4)


  • 具体实现(3种写法)

  • 使用LinkedList和HashMap实现:
import java.util.LinkedList;
import java.util.concurrent.ConcurrentHashMap;

/**
 * LRU缓存实现
 */
class LRUCache {

    static class Node {
       public int key, val;
       public Node prev,next;
       public Node(int k,int v){
           this.key = k;
           this.val = v;
       }
    }

    private LinkedList<Node> cache;
    private ConcurrentHashMap<Integer, Node> map;
    private int cap;

    public LRUCache(int capacity) {
        this.cap = capacity;
        this.cache = new LinkedList<>();
        this.map = new ConcurrentHashMap<>();
    }

    public int get(int key) {
        if (!map.containsKey(key)){
            return -1;
        }else {
            Node node = map.get(key);
            //移除该节点并将其插到头部
            cache.remove(node);
            cache.addFirst(node);
            return node.val;
        }
    }

    public void put(int key, int value) {
        Node node = new Node(key, value);
        if (map.containsKey(key)){
            //更新值,并前置到头结点
            cache.remove(map.get(key));
            cache.addFirst(node);
            map.put(key, node);
        }else {
            //不存在,先判断容量
            if (cap == cache.size()){
                //删除最后一个节点
                Node lastNode = cache.removeLast();
                map.remove(lastNode.key);
            }
            cache.addFirst(node);
            map.put(key, node);
        }
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */
  • 自己定义双向链表的实现(推荐:头插作为最近使用元素)
import java.util.concurrent.ConcurrentHashMap;

class LRUCache {
    /**
     * 定义链中的Node
     */
    static class DLinkedNode {
        int key, value;
        DLinkedNode prev, next;

        public DLinkedNode() {
        }

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

    ConcurrentHashMap<Integer, DLinkedNode> map = new ConcurrentHashMap<>();
    DLinkedNode head, tail;
    private int size;
    private int capacity;

    public LRUCache(int cap) {
        this.capacity = cap;
        this.size = 0;
        this.head = new DLinkedNode();
        this.tail = new DLinkedNode();
        //连接首尾节点
        head.next = tail;
        tail.prev = head;
    }

    /**
     * 获取值
     * @param key
     * @return
     */
    public int get(int key){
        if (!map.containsKey(key)){
            return -1;
        }else {
            DLinkedNode node = map.get(key);
            //更新到头部
            moveToHead(node);
            return node.value;
        }
    }

    /**
     * 添加值
     * @param key
     * @param val
     */
    public void put(int key,int val){
        DLinkedNode node = new DLinkedNode(key, val);
        //当前键值对存在,直接更新
        if (map.containsKey(key)){
            //删除旧值再添加,而不是直接移动
            removeNode(map.get(key));
            addToHead(node);
            map.put(key,node);
        }else {
            //容量已满
            if (size==capacity){
                DLinkedNode tail = removeTail();
                map.remove(tail.key);
                size--;
            }
            map.put(key,node);
            addToHead(node);
            size++;
        }
    }

    /**
     * 添加到头结点(相当于一次插入节点 o(1))
     *
     * @param node
     */
    private void addToHead(DLinkedNode node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    /**
     * 删除节点(断开链)
     *
     * @param node
     */
    private void removeNode(DLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    /**
     * 移动到头节点处
     *
     * @param node
     */
    private void moveToHead(DLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }

    /**
     * 删除尾结点(删除虚拟尾结点的前一个节点)
     *
     * @return
     */
    private DLinkedNode removeTail() {
        DLinkedNode node = tail.prev;
        removeNode(node);
        return node;
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */
  • 自己定义双向链表的实现(推荐:尾插作为最近使用元素,并对哈希表和双向链表的处理调用多做了一层封装,使直接调用方法的逻辑更为清晰)
public class LRUCache {

    //定义双向链表所需的Node类
    private class Node{
        public int key,val;
        public Node prev,next;
        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    //双向链表 此处假设双向链表在尾部添加节点,则头部节点为最久未使用节点
    private class DoubleList{
        //首尾结点
        private Node head,tail;
        //链表元素数
        private int size;
        public DoubleList() {
            head = new Node(0,0);
            tail = new Node(0,0);
            head.next = tail;
            tail.prev = head;
            size =0;
        }

        //在链表尾部添加节点x,节点数量+1
        public void addLast(Node x){
            x.prev = tail.prev;
            x.next = tail;
            tail.prev.next = x;
            tail.prev = x;
            size++;
        }

        //删除链表中的节点x
        public void remove(Node x){
            x.prev.next = x.next;
            x.next.prev = x.prev;
            size--;
        }

        //删除链表中的第一个节点并返回该节点
        public Node removeFirst(){
            if (head.next == tail){
                return null;
            }
            Node first = head.next;
            remove(first);
            return first;
        }

        //返回链表长度
        public int size(){return size;}
    }

    private HashMap<Integer,Node> map;
    private DoubleList cache;
    private int capacity;

    public LRUCache(int cap) {
        this.map = new HashMap<Integer,Node>();
        this.cache = new DoubleList();
        this.capacity = cap;
    }

    //将某个Key提升为最近使用
    private void makeRecently(int key){
        Node node = map.get(key);
        //删除节点
        cache.remove(node);
        //添加到最近使用
        cache.addLast(node);
    }

    //添加最近使用节点
    private void addRecently(int key,int val){
        Node node = new Node(key, val);
        /**本代码采用链表尾部插入作为最近使用的元素*/
        cache.addLast(node);
        //在Map中添加key的映射
        map.put(key,node);
    }

    //删除key
    private void deleteKey(int key){
        Node node = map.get(key);
        //缓存中删除
        cache.remove(node);
        //Map中删除
        map.remove(key);
    }

    //当缓存容量不足时,删除最久未使用的节点
    private void removeLeastRecently(){
        /**本代码链表头部的第一个节点即为最久未使用的节点*/
        Node deleteNode = cache.removeFirst();
        int key = deleteNode.key;
        map.remove(key);
    }

    public int get(int key){
        if (!map.containsKey(key)){
            return -1;
        }
        makeRecently(key);
        return map.get(key).val;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)){
            //删除旧数据
            deleteKey(key);
            //将当前插入数据设置为最近使用
            addRecently(key, value);
            return;
        }
        if (capacity==cache.size){
            removeLeastRecently();
        }
        addRecently(key, value);
    }
}

  • 直接继承java封装好的LinkedHashMap类,重写其中的关于清理最旧数据的条件即可
class LRUCache extends LinkedHashMap<Integer, Integer>{
    private int capacity;
    
    public LRUCache(int capacity) {
        super(capacity, 0.75F, true);
        this.capacity = capacity;
    }

    public int get(int key) {
        return super.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        super.put(key, value);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity; 
    }
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 201,552评论 5 474
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 84,666评论 2 377
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 148,519评论 0 334
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,180评论 1 272
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,205评论 5 363
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,344评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,781评论 3 393
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,449评论 0 256
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,635评论 1 295
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,467评论 2 317
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,515评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,217评论 3 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,775评论 3 303
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,851评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,084评论 1 258
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,637评论 2 348
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,204评论 2 341

推荐阅读更多精彩内容

  • 转载https://blog.csdn.net/jake_li/article/details/50659868 ...
    VincentHK阅读 1,010评论 0 3
  • 内容来源:网上找的,并非原创,原链接找不到了!特此说明!! 排序 比较排序 冒泡排序 重复地走访过要排序的数列,每...
    sunjiandev阅读 272评论 0 0
  • 久违的晴天,家长会。 家长大会开好到教室时,离放学已经没多少时间了。班主任说已经安排了三个家长分享经验。 放学铃声...
    飘雪儿5阅读 7,462评论 16 22
  • 今天感恩节哎,感谢一直在我身边的亲朋好友。感恩相遇!感恩不离不弃。 中午开了第一次的党会,身份的转变要...
    迷月闪星情阅读 10,543评论 0 11
  • 可爱进取,孤独成精。努力飞翔,天堂翱翔。战争美好,孤独进取。胆大飞翔,成就辉煌。努力进取,遥望,和谐家园。可爱游走...
    赵原野阅读 2,711评论 1 1