最近最少使用(LRU)缓存淘汰算法

本文阅读 14 分钟
首页 代码,Java 正文

目录

1 概述

2 链表

2.1 插入、删除操作

2.2 循环链表

2.3 双向链表

3 基于链表实现 LRU 缓存淘汰算法

*3.1 优化

4 彩蛋

先抛个结论:其实链表就可以,但我们可以用哈希表来优化。

 

想了一下,目前阶段的博客还是要从基础说起,以免对同学们带来不好的体验。不急,慢慢来。

 

来自一段百度百科对缓存的介绍:

缓存是一种提高数据读取性能的技术,缓存的工作原理是当CPU要读取一个数据时,首先从CPU缓存中查找,找到就立即读取并送给CPU处理;没有找到,就从速率相对较慢的内存中读取并送给CPU处理,同时把这个数据所在的数据块调入缓存中,可以使得以后对整块数据的读取都从缓存中进行,不必再调用内存。

缓存的大小有限,当缓存空间被占满时,我们需要一个策略来决定,哪些数据应该被清理出去,常见的策略有三种:

  • 先进先出 FIFO(First In,First Out)
  • 最少使用 LFU(Least Frequently Used)
  • 最近最少使用 LRU(Least Recently Used)

 

先从底层结构上看一下:

img

数组需要一块连续的内存空间来存储,对内存的要求比较高。链表则只需要一个“指针”将一组零散的内存块串联起来使用。

我们把链表串联起来的内存块称为链表的“结点”。为了将所有的结点串起来,每个链表的结点除了存储数据之外,还需要记录链上的下一个结点的地址,如下图所示:

img

其中有两个结点是比较特殊的,它们分别是第一个结点和最后一个结点。第一个结点被称作头结点,最后一个结点被称作尾结点。有了头节点,我们就可以遍历得到整条链表。而尾结点的指针不是指向下一个结点,而是指向一个空地址 null。

 

2.1 插入、删除操作

与数组一样,链表也支持数据的查找、插入和删除。

在进行数组的插入、删除操作时,需要做大量的数据搬移,时间复杂度是 O(n)。

在进行链表的插入、删除操作时,因为链表的存储空间本身就不是连续的,所以不需要为了保持内存的连续性而搬移结点。

img

img

针对链表的插入和删除操作,我们只需要考虑相邻结点的指针改变,所以对应的时间复杂度是 O(1)。

 

然而如果链表要想访问第 k 个元素,就没有数组那么高效了。因为链表中的数据并非连续存储的,无法像数组那样,根据首地址和下标直接计算出对应的内存地址,而是需要根据指针一个结点一个结点地依次遍历,直到找到相应的结点。

 

2.2 循环链表

img

循环链表的优点是从链尾到链头比较方便。当要处理的数据具有环型结构特点时,就特别适合采用循环链表。比如我们之前做过的选队长问题。

 

2.3 双向链表

单向链表只有一个方向,结点只有一个后继指针 next 指向后面的结点。而双向链表支持两个方向,每个结点不止有一个后继指针 next指向后面的结点,还有一个前驱指针 prev指向前面的结点。

img

双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以,如果存储同样多的数据,双向链表要比单链表占用更多的内存空间。虽然两个指针比较浪费存储空间,但可以支持双向遍历。

双向链表可以支持 O(1) 时间复杂度的情况下找到前驱结点,使得双向链表插入、删除等操作比单链表更简单。

 

用空间换时间。开篇提到的缓存实际上就是利用了这种思想。如果我们把数据存储在硬盘上,会比较节省内存,但每次查找数据都要询问一次硬盘,会比较慢。但如果我们通过缓存技术,事先将数据加载在内存中,虽然会比较耗费内存空间,但是每次数据查询的速度就大大提高了。

 

我们可以维护一个有序单链表,越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时,我们从链表头开始顺序遍历链表。

  1. 如果此数据之前已经被缓存了,我们遍历得到这个数据对应的结点,并将其从原来的位置删除,然后再插入到链表的头部。
  2. 如果此数据没有在缓存链表中,又可以分为两种情况:
    2. 如果此时缓存未满,则将此结点直接插入到链表的头部; 2. 如果此时缓存已满,则链表尾结点删除,将新的数据结点插入链表的头部。

具体解释如下:

public static void main(String[] args) {
        // 缓存容量为2
        LRUCache cache = new LRUCache(2);

        // 此时存入了1,缓存内{1}
        cache.put(1);

        // 此时存入了2,缓存内{2 -> 1}
        cache.put(2);

        // 此时存入了3,但缓存空间已满,所以移掉1存入3
        // 缓存内{3 -> 2}
        cache.put(3);
        
        // 此时使用了数据2
        // 缓存内{2 -> 3}
        cache.get(2);

    }

img

链表节点类:

要存储的信息: 

    值、下一个节点

package base;

public class Node {
    public int val;
    public Node next;

    public Node(int v) {
        this.val = v;
    }

    public Node(int v, Node next) {
        this.val = v;
        this.next = next;
    }
}

单向链表类:

设置一个虚拟头节点、属性size记录链表长度

public Node head;
// 链表元素数
private int size;

public SingleList() {
   // 初始化双向链表的数据
   head = new Node(-1);
   head.next = null;
   size = 0;
}

提供添加元素的方法:

/**
     * 在第index处插入元素e
     * @param index
     * @param e
     */
    public void add(int index, int e){
        if (index < 0 || index > size)
            throw new IllegalArgumentException("Add failed. Illegal index.");

        Node prev = head;
        for (int i = 0; i < index; i ++){
            prev = prev.next;
        }
        prev.next = new Node(e, prev.next);
        size ++;
    }
// 在链表尾部添加节点 x
public void addLast(Node x) {
    add(size, x.val);
}
// 在链表头部添加节点 x
public void addFirst(Node x) {
    add(0, x.val);
}

 

提供删除元素的方法:

  • 根据索引删除
// 从链表中删除index处的元素
    public Node remove(int index){
        if (index < 0 || index > size)
            throw new IllegalArgumentException("Set failed. Illegal index.");

        Node prev = head;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        Node retNode = prev.next;
        prev.next = retNode.next;
        retNode.next = null;
        size --;

        return retNode;
    }
  • 删除传入节点
// 删除节点x
    public void remove(Node x){
        Node pre = head;
        Node node = head.next;
        while (node != null){
            if (node == x){
                pre.next = node.next;
                node.next = null;
            }
            node = node.next;
            pre = pre.next;
        }
    }
  • 删除第一或最后一个元素
/**
     * 删除最后一个节点
     * @return
     */
    public Node removeLast() {
        return remove(size - 1);
    }

    /**
     * 删除第一个节点
     * @return
     */
    public Node removeFirst(){
        return remove(0);
    }

提供根据数值寻找节点的方法:

/**
     * 根据值寻找节点
     * @param val
     * @return
     */
    public Node findByValue(int val){
        Node node = head;
        while (node != null){
            if (node.val == val){
                return node;
            }
            node = node.next;
        }
        return null;
    }

LRU缓存算法类:

用链表的底层来实现缓存,构造函数传入初始容量

public class LRUCache {
    private SingleList cache;

    private int cap;    // 最大容量

    public LRUCache(int capacity) {
        this.cap = capacity;
        cache = new SingleList();
    }

}

将某个val提升为最近使用的:

private void makeRecently(int val) {
        Node x = cache.findByValue(val);
        // 先从链表中删除这个节点
        cache.remove(x);
        // 重新插到队头
        cache.addFirst(x);
    }

添加最近使用的val:

private void addRecently(int val) {
        Node x = new Node(val);
        // 链表头部就是最近使用的元素
        cache.addFirst(x);
    }

删除某一个val:先找到对应节点,然后删除

private void deleteVal(int val) {
        Node x = cache.findByValue(val);
        // 从链表中删除
        cache.remove(x);
    }

删除最久未使用的val:

private void removeLeastRecently() {
        // 链表尾部元素就是最久未使用的
        cache.removeLast();
    }

 使用缓存中的某个数据:

public Node get(int val) {
        Node x = cache.findByValue(val);
        if (x == null){
            return null;
        }
        // 将该数据提升为最近使用的
        makeRecently(val);
        return x;
    }

放入新数据:如果缓存已经满了则需要删除最久未使用的

public void put(int val) {
        if (cache.findByValue(val) != null) {
            // 删除旧的数据
            deleteVal(val);
            // 新插入的数据为最近使用的数据
            addRecently(val);
            return;
        }

        if (cap == cache.size()) {
            // 删除最久未使用的元素
            removeLeastRecently();
        }
        // 添加为最近使用的元素
        addRecently(val);
    }

打印方法:

public void printCache(){
        Node pointer = cache.head;
        while (pointer != null){
            System.out.print("[" + pointer.val + "] ->");
            pointer = pointer.next;
        }
        System.out.println();
    }

 

*3.1 优化

我们可以继续优化这个实现思路,比如引入散列表(Hash table)来记录每个数据的位置,将缓存访问的时间复杂度降到 O(1)。这里缓存改为存储键值对了,其实上面的单向链表的每个Node也可以存储两个值,key和value,有兴趣的同学们可以自己尝试一下

如果想让 put 和 get 方法的时间复杂度为 O(1),我们可以尝试总结以下几点:

  1. cache 中的元素存储时必须能体现先后顺序,以区分最近使用的和久未使用的数据;
    <li>要在 cache 中快速找某个 key 是否存在并得到对应的 val;</li>

<li>每次访问 cache 中的值,需要将其变为最近使用的,即,要支持在任意位置快速插入和删除元素。</li>

哈希表查找快,但是数据无固定顺序;链表有顺序之分,插入删除快,但是查找慢。

 

所以,结合一下,用哈希链表

 

实际上LRU算法的核心数据结构就是哈希链表,长这样:

img

再看上面的条件:

  1. 同单链表的情况相同,如果从头部插入元素,显然越靠近尾部的元素是最久未使用的。(当然反过来也成立);
  2. 对于一个key,可以通过HashTable快速查找到val;
  3. 链表显然是支持在任意位置快速插入和删除的。只不过传统的链表查找元素的位置较慢,而这里借助哈希表,通过 key快速映射到一个链表节点,然后进行插入和删除。

这次我们从尾部插入,从头部删除~

 

双向链表的节点类Node:

只增加了一个指向上一个节点的指针 Node pre

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

依靠实现的节点类Node给出双向链表的实现:

构造方法初始化头尾虚节点,链表元素个数

class DoubleList {
    // 头尾虚节点
    public 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,时间 O(1)
    public void addLast(Node x) {
        x.prev = tail.prev;
        x.next = tail;
        tail.prev.next = x;
        tail.prev = x;
        size++;
    }

删除节点x的方法:

删除一个节点不光要得到该节点本身的指针,也需要操作其前驱节点的指针,双向链表由于有pre指针的存在所以删除操作的时间复杂度为O(1) 

// 删除链表中的 x 节点(x 一定存在)
    // 由于是双链表且给的是目标 Node 节点,时间 O(1)
    public void remove(Node x) {
        x.prev.next = x.next;
        x.next.prev = x.prev;
        size--;
    }

删除链表第一个节点的方法:

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

LRU缓存算法类:

有了双向链表的实现,我们只需要在 LRU 算法中把它和哈希表结合起来即可

构造方法:

class LRUCache {
    // key -> Node(key, val)
    private HashMap<Integer, Node> map;
    // Node(k1, v1) <-> Node(k2, v2)...
    private DoubleList cache;
    // 最大容量
    private int cap;

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

接下来先设计一些辅助函数,用于随后进行操作的:

将某个值设置为最近使用的:

private void makeRecently(int key) {
        Node x = map.get(key);
        // 先从链表中删除这个节点
        cache.remove(x);
        // 重新插到队尾
        cache.addLast(x);
    }

添加一个元素,该元素为最新使用的:

private void addRecently(int key, int val) {
        Node x = new Node(key, val);
        // 链表尾部是最近使用的元素
        cache.addLast(x);
        // 维护map
        map.put(key, x);
    }

删除元素:

private void deleteKey(int key) {
        Node x = map.get(key);
        // 从链表中删除
        cache.remove(x);
        // 维护map
        map.remove(key);
    }

删除最久没用的元素:其实就是删除第一个节点

private void removeLeastRecently() {
        // 链表头部的第一个元素就是最久未使用的
        Node deletedNode = cache.removeFirst();
        // 维护map
        int deletedKey = deletedNode.key;
        map.remove(deletedKey);
    }

有了上面这些辅助函数,接下来就可以实现LRU算法的get和put方法了:

get方法:

public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        // 将该数据提升为最近使用的
        makeRecently(key);
        return map.get(key).val;
    }

put方法:

img

public void put(int key, int val) {
        if (map.containsKey(key)) {
            // 删除旧的数据
            deleteKey(key);
            // 新插入的数据为最近使用的数据
            addRecently(key, val);
            return;
        }

        if (cap == cache.size()) {
            // 删除最久未使用的元素
            removeLeastRecently();
        }
        // 添加为最近使用的元素
        addRecently(key, val);
    }

打印方法:

public void printCache(){
        Node pointer = cache.head.next;
        while (pointer != cache.tail){
            System.out.print("[" + pointer.key + "," + pointer.val + "] ->");
            pointer = pointer.next;
        }
        System.out.println();
    }

 

说了这么多其实也同时解决了 leetcode146 ,大家可以自行探索~

 

Java已经内置了相应的哈希链表LinkedHashMap这个数据结构我们可以直接拿过来用,逻辑和上文相同

class LRUCache {
    int capacity;    // 缓存大小
    LinkedHashMap<Integer, Integer> cache = new LinkedHashMap<>();

    public LRUCache(int capacity) { 
        this.capacity = capacity;
    }
    
    // 从缓存中取出数据方法
    public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        }
        
        makeRecently(key);
        return cache.get(key);
    }
    
    // 向缓存中添加数据方法
    public void put(int key, int val) {
        if (cache.containsKey(key)) {
            // 修改 key 的值
            cache.put(key, val);
            // 将 key 变为最近使用
            makeRecently(key);
            return;
        }

        if (cache.size() >= this.capacity) {
            // 链表头部
            int oldestKey = cache.keySet().iterator().next();
            cache.remove(oldestKey);
        }
       
        cache.put(key, val);
    }
    
    // 将数据设置为最近使用
    private void makeRecently(int key) {
        int val = cache.get(key);
        // 删除 key,重新插入到队尾
        cache.remove(key);
        cache.put(key, val);
    }
}

 

 

 

如有更多需要可以关注我的个人公众号【N小王日记】,里面有我个人联系方式。

img

 

本文为互联网自动采集或经作者授权后发布,本文观点不代表立场,若侵权下架请联系我们删帖处理!文章出自:https://wangjiawei.blog.csdn.net/article/details/108039409
-- 展开阅读全文 --
安全面试之XSS(跨站脚本攻击)
« 上一篇 07-24

发表评论

成为第一个评论的人

热门文章

标签TAG

最近回复