关于java:手写LRU缓存淘汰算法

31次阅读

共计 6525 个字符，预计需要花费 17 分钟才能阅读完成。

手写 LRU 缓存淘汰算法

背景

在咱们这个日益谋求高效的世界，咱们对任何事件的期待都显得非常的塌实，网页页面刷新不进去，好烦，电脑关上运行程序慢，又是好烦！那怎么办，技术的产生不就是咱们所服务么，明天咱们就聊一聊 缓存 这个技术，并应用咱们熟知的数据结构 –用链表实现 LRU 缓存淘汰算法。

在学习如何应用链表实现 LRU 缓存淘汰算法前，咱们先提出几个问题，大家好好思考下，问题如下：

  • 什么是缓存，缓存的作用？
  • 缓存的淘汰策略有哪些？
  • 如何应用链表实现 LRU 缓存淘汰算法，有什么特点，如何优化？

好了，咱们带着下面的问题来学进行上面的学习。

1、什么是缓存，缓存的作用是什么?

缓存 能够简略的了解为保留数据的一个 正本 ，以便于后续可能疾速的进行拜访。 以计算机的应用场景为例，当 cpu 要拜访内存中的一条数据时，它会先在缓存里查找，如果可能找到则间接应用，如果没找到，则须要去内存里查找；

同样的，在数据库的拜访场景中，当我的项目零碎须要查询数据库中的某条数据时，能够先让申请查问缓存，如果命中，就间接返回缓存的后果，如果没有命中，就查询数据库，并将查问后果放入缓存，下次申请时查问缓存命中，间接返回后果，就不必再次查询数据库。

通过以上两个例子，咱们发现无论在哪种场景下，都存在这样一个程序：先缓存，后内存 ； 先缓存，后数据库 。然而缓存的存在也占用了一部分内存空间，所以缓存是典型的以 空间换工夫 ，就义数据的 实时性 ，却满足计算机运行的 高效性。

认真想一下，咱们日常开发中遇到缓存的例子还挺多的。

  • 操作系统的缓存

缩小与磁盘的交互

  • 数据库缓存

缩小对数据库的查问

  • Web 服务器缓存

缩小对应用服务器的申请

  • 客户浏览器的缓存

缩小对网站的拜访

2、缓存有哪些淘汰策略?

缓存的实质是以 空间换工夫，那么缓存的容量大小必定是无限的，当缓存被占满时，缓存中的那些数据应该被清理进来，那些数据应该被保留呢？这就须要缓存的淘汰策略来决定。

事实上，罕用的缓存的淘汰策略有三种：先进先出算法(First in First out FIFO)；淘汰肯定期间内被拜访次数起码的页面(Least Frequently Used LFU)；淘汰最长工夫未被应用的页面(Least Recently Used LRU)

这些算法在不同档次的缓存上执行时具备不同的效率，须要联合具体的场景来抉择。

2.1 FIFO 算法

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

  • 新拜访的数据插入 FIFO 队列的尾部，队列中数据由队到队头按程序程序挪动
  • 队列满时，删除队头的数据

2.2 LRU 算法

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

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

2.3 LFU 算法

LFU 算法 是依据数据的历史拜访频率来淘汰数据，因而，LFU 算法中的每个数据块都有一个援用计数，所有数据块依照援用计数排序，具备雷同援用计数的数据块则依照工夫排序。在缓存中，它的设计准则是：如果数据被拜访屡次，那么未来它的拜访频率也会更高。

  • 新退出数据插入到队列尾部（援用计数为 1；
  • 队列中的数据被拜访后，援用计数减少，队列从新排序；
  • 当须要淘汰数据时，将曾经排序的列表最初的数据块删除。

3、如何应用链表实现缓存淘汰，有什么特点，如何优化？

在下面的文章中咱们了解了 缓存的概念 及淘汰策略 ，其中LRU 算法 是口试 / 面试中考查比拟频繁的，我秋招的时候，很多公司都让我手写了这个算法，为了防止大家采坑，上面，咱们就手写一个 LRU 缓存淘汰算法。

咱们都晓得链表的模式不止一种，咱们应该抉择哪一种呢？

思考三分钟 ……..

好了，颁布答案！

事实上，链表依照不同的连接结构能够划分为 单链表 、 循环链表 和双向链表。

  • 单链表
  • 每个节点只蕴含一个指针，即后继指针。
  • 单链表有两个非凡的节点，即首节点和尾节点，用首节点地址示意整条链表，尾节点的后继指针指向空地址 null。
  • 性能特点：插入和删除节点的工夫复杂度为 O(1)，查找的工夫复杂度为 O(n)。
  • 循环链表
  • 除了尾节点的后继指针指向首节点的地址外均与单链表统一。
  • 实用于存储有循环特点的数据，比方约瑟夫问题。
  • 双向链表
  • 节点除了存储数据外，还有两个指针别离指向前一个节点地址（前驱指针 prev）和下一个节点地址（后继指针 next）
  • 首节点的前驱指针 prev 和尾节点的后继指针均指向空地址。

双向链表相较于单链表的一大劣势在于：找到前驱节点的工夫复杂度为 O(1)，而单链表只能从头节点缓缓往下找，所以依然是 O(n). 而且，对于插入和删除也是有优化的。

咱们可能会有问题：单链表的插入删除不是 O(1)吗？

是的，然而个别状况下，咱们想要进行插入删除操作，很多时候还是得先进行查找，再插入或者删除，可见其实是先 O(n), 再 O(1)。

不相熟链表解题的同学能够先看看我的上一篇算法解析文章刷了 LeetCode 链表专题，我发现了一个机密。

因为咱们须要删除操作，删除一个节点不仅要失去该节点自身的指针，也须要操作其它前驱节点的指针，而双向链表可能间接找到前驱，保障了操作工夫复杂度为 O(1)，因而应用双向链表作为实现 LRU 缓存淘汰算法的构造会更高效。

算法思路

保护一个双向链表，保留所有缓存的值，并且最老的值放在链表最初面。

  • 当拜访的值在链表中时：将找到链表中值将其删除，并从新在链表头增加该值（保障链表中 数值的程序是从新到旧）
  • 当拜访的值不在链表中时：当链表已满：删除链表最初一个值，将要增加的值放在链表头 当链表未满：间接在链表头增加

3.1 LRU 缓存淘汰算法

极客工夫王争的《数据结构与算法之美》给出了一个应用有序单链表实现 LRU 缓存淘汰算法，代码如下：

public class LRUBaseLinkedList<T> {

    /**
     * 默认链表容量
     */
    private final static Integer DEFAULT_CAPACITY = 10;

    /**
     * 头结点
     */
    private SNode<T> headNode;

    /**
     * 链表长度
     */
    private Integer length;

    /**
     * 链表容量
     */
    private Integer capacity;

    public LRUBaseLinkedList() {this.headNode = new SNode<>();
        this.capacity = DEFAULT_CAPACITY;
        this.length = 0;
    }

    public LRUBaseLinkedList(Integer capacity) {this.headNode = new SNode<>();
        this.capacity = capacity;
        this.length = 0;
    }

    public void add(T data) {SNode preNode = findPreNode(data);

        // 链表中存在，删除原数据，再插入到链表的头部
        if (preNode != null) {deleteElemOptim(preNode);
            intsertElemAtBegin(data);
        } else {if (length >= this.capacity) {
                // 删除尾结点
                deleteElemAtEnd();}
            intsertElemAtBegin(data);
        }
    }

    /**
     * 删除 preNode 结点下一个元素
     *
     * @param preNode
     */
    private void deleteElemOptim(SNode preNode) {SNode temp = preNode.getNext();
        preNode.setNext(temp.getNext());
        temp = null;
        length--;
    }

    /**
     * 链表头部插入节点
     *
     * @param data
     */
    private void intsertElemAtBegin(T data) {SNode next = headNode.getNext();
        headNode.setNext(new SNode(data, next));
        length++;
    }

    /**
     * 获取查找到元素的前一个结点
     *
     * @param data
     * @return
     */
    private SNode findPreNode(T data) {
        SNode node = headNode;
        while (node.getNext() != null) {if (data.equals(node.getNext().getElement())) {return node;}
            node = node.getNext();}
        return null;
    }

    /**
     * 删除尾结点
     */
    private void deleteElemAtEnd() {
        SNode ptr = headNode;
        // 空链表间接返回
        if (ptr.getNext() == null) {return;}

        // 倒数第二个结点
        while (ptr.getNext().getNext() != null) {ptr = ptr.getNext();
        }

        SNode tmp = ptr.getNext();
        ptr.setNext(null);
        tmp = null;
        length--;
    }

    private void printAll() {SNode node = headNode.getNext();
        while (node != null) {System.out.print(node.getElement() + ",");
            node = node.getNext();}
        System.out.println();}

    public class SNode<T> {

        private T element;

        private SNode next;

        public SNode(T element) {this.element = element;}

        public SNode(T element, SNode next) {
            this.element = element;
            this.next = next;
        }

        public SNode() {this.next = null;}

        public T getElement() {return element;}

        public void setElement(T element) {this.element = element;}

        public SNode getNext() {return next;}

        public void setNext(SNode next) {this.next = next;}
    }

    public static void main(String[] args) {LRUBaseLinkedList list = new LRUBaseLinkedList();
        Scanner sc = new Scanner(System.in);
        while (true) {list.add(sc.nextInt());
            list.printAll();}
    }
}

这段代码不论缓存有没有满，都须要遍历一遍链表，所以这种基于链表的实现思路，缓存拜访的工夫复杂度为 O(n)。

3.2 应用哈希表优化 LRU

事实上，这个思路还能够持续优化，咱们能够把单链表换成 双向链表 ，并引入 散列表。

  • 双向链表反对查找前驱，保障操作的工夫复杂度为 O(1)
  • 引入散列表记录每个数据的地位，将缓存拜访的工夫复杂度降到 O(1)

哈希表查找较快，然而数据无固定的程序；链表倒是有程序之分。插入、删除较快，然而查找较慢。将它们联合，就能够造成一种新的数据结构 –哈希链表(LinkedHashMap)

力扣上 146 题 -LRU 缓存机制刚好能够拿来练手，题图如下：

题目：

使用你所把握的数据结构，设计和实现一个 LRU (最近起码应用) 缓存机制。

  • 实现 LRUCache 类：

LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1。
void put(int key, int value) 如果关键字曾经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字 - 值」。当缓存容量达到下限时，它应该在写入新数据之前删除最久未应用的数据值，从而为新的数据值留出空间。

思路：

咱们的思路就是 哈希表 + 双向链表

  • 哈希表用于满足题目工夫复杂度 O(1)的要求，双向链表用于存储程序
  • 哈希表键值类型：<Integer, ListNode>，哈希表的键用于存储输出的 key，哈希表的值用于存储双向链表的节点
  • 双向链表的节点中除了 value 外还须要蕴含 key，因为在删除最久未应用的数据时，须要通过链表来定位 hashmap 中该当删除的键值对
  • 一些操作：双向链表中，在前面的节点示意被最近拜访
  • 新退出的节点放在链表开端，addNodeToLast(node)
  • 若容量达到下限，去除最久未应用的数据，removeNode(head.next)
  • 若数据新被拜访过，比方被 get 了或被 put 了新值，把该节点挪到链表开端，moveNodeToLast(node)
  • 为了操作的不便，在双向链表头和尾别离定义一个 head 和 tail 节点。

代码

class LRUCache {
    private int capacity;
    private HashMap<Integer, ListNode> hashmap; 
    private ListNode head;
    private ListNode tail;

    private class ListNode{
        int key;
        int val;
        ListNode prev;
        ListNode next;
        public ListNode(){}
        public ListNode(int key, int val){
            this.key = key;
            this.val = val;
        }
    }

    public LRUCache(int capacity) {
        this.capacity = capacity;
        hashmap = new HashMap<>();
        head = new ListNode();
        tail = new ListNode();
        head.next = tail;
        tail.prev = head;
    }

    private void removeNode(ListNode node){
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void addNodeToLast(ListNode node){
        node.prev = tail.prev;
        node.prev.next = node;
        node.next = tail;
        tail.prev= node;
    }

    private void moveNodeToLast(ListNode node){removeNode(node);
        addNodeToLast(node);
    }
    
    public int get(int key) {if(hashmap.containsKey(key)){ListNode node = hashmap.get(key);
            moveNodeToLast(node);
            return node.val;
        }else{return -1;}
    }
    
    public void put(int key, int value) {if(hashmap.containsKey(key)){ListNode node = hashmap.get(key);
            node.val = value;
            moveNodeToLast(node);
            return;
        }
        if(hashmap.size() == capacity){hashmap.remove(head.next.key);
            removeNode(head.next);
        }

        ListNode node = new ListNode(key, value);
        hashmap.put(key, node);
        addNodeToLast(node);
    }
}

伟人的肩膀

[1]数据结构与算法之美 - 王争

[2]力扣 -LRU 缓存机制(146 题)

[3]https://blog.csdn.net/yangpl_…

[4]https://leetcode-cn.com/probl…

本文由博客群发一文多发等经营工具平台 OpenWrite 公布

正文完
java
发表至： java
2021-03-01
 0
关于java:论基础理论知识的重要性
WebSocket协议 8 问
关于java:springbootroute二十一quartz实现动态定时任务
关于java:Spring-GraphQL成为Spring顶级项目将发布第一个里程碑版本