利用LRU（哈希链表）实现本地缓存

认识哈希链表

Untitled.png

本质就是：散列表+链表。它被用于实现LRU等算法。

作用：

  • 散列表：提供O(1) 复杂度下的快速读
  • 双向链表：提供 O(1) 复杂度下的快速增删修改

认识LRU算法

LRU 是 Least Recently Used 的缩写，这种算法认为最近使用的数据是热门数据，下一次很大概率将会再次被使用。而最近很少被使用的数据，很大概率下一次不再用到。当缓存容量的满时候，优先淘汰最近很少使用的数据。

LRU 算法具体步骤：

  • 新数据直接插入到链表头部
  • 缓存数据被命中，将数据移动到链表头部
  • 缓存已满的时候，移除链表尾部数据

LRU算法特点：

  • 容量有上限，用于本地缓存能防止被撑爆。
  • 缓存命令中率高。清空缓存时，先清空不经常被访问的缓存；如果缓存经常被访问，那么会一直保存
  • 读写性能高，时间复杂度均为O(1)

利用LRU优化本地缓存

数据结构

基于LRU的哈希链表实现。

为什么选择哈希链表实现？
0、从需求出发，考虑使用哪些数据结构：要求快速访问，读O(1)；快速增删，写O(1)
1、哈希链表 = 哈希表 + （双向）链表
2、链表：O(1) 时间内快速增删，但是读复杂度O(N)
3、哈希表：更次存入链表时，每个节点有2个字段，key和value；同时更新map。
下次需要查缓存时，直接根据key，从map中读取缓存值即可，复杂度是O(1)

在nodejs中，双向链表库使用了 yallist.js ：

  • 只支持插入尾部，不支持插入头部。所以和常见的lru的链表相反，尾部节点是最新命中节点，头部是最远命中节点
  • yallist每个节点的结构是 { value, prev, next } 。prev保存上一个节点引用，next保存下一个节点引用。例如：想要访问其上的值，要访问：node.value.value
  • 由于保存了prev和next指针，因此其上的removeNode等方法的复杂度是O(1)，不需要像单链表那样从头到位遍历

代码

引入yallist，并且定义缓存节点类型：

1
2
3
4
5
6
7
8
9
const yallist = require("yallist");
// key: 缓存键名
// value：缓存值
class Node {
    constructor(key, value) {
        this.key = key;
        this.value = value;
    }
}

实现LRU：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**
 * 为什么链表中节点要存key和value呢？
 * 在移除链表中节点的时候，可以根据节点的key，移除map中的数据时候，需要key。
 */
class LRUCache {
    constructor(capacity = 10) {
        this.map = new Map();
        this.doubleLinkedList = yallist.create([]);
        this.capacity = capacity;
    }

    /**
     * 读取缓存
     * 1、无：返回null
     * 2、有：拿到缓存的值，返回；并且将key对应的缓存节点更新到尾部
     */
    get(key) {
        if (this.map.has(key)) {
            const node = this.map.get(key);
            this.put(key, node.value.value);
            return node.value;
        }
        return null;
    }

    /**
     * 更新缓存
     * 简单的情况：就是将节点放入链表中，然后(key,节点)放入到map中
     * 更多情况：
     *  1. 检查是否存在key
     *  2. 检查是否到达容量上限
     */
    put(key, value) {
        if (this.map.has(key)) {
            // 如果双向链表中存在节点，那么将此节点移出，以备之后将其放入尾部
            this.doubleLinkedList.removeNode(this.map.get(key));
        } else {
            // 如果不存在此节点，那么应该检查是否到达容量。
            // 如果到达容量，应该把最远（不常用）访问的节点移除
            if (this.doubleLinkedList.length === this.capacity) {
                const headNode = this.doubleLinkedList.head;
                this.map.delete(headNode.value.key);
                this.doubleLinkedList.removeNode(headNode);
            }
        }
        // 将新节点放入尾部，代表最近访问
        this.doubleLinkedList.push(new Node(key, value));
        // 更新map中的数据，用于之后O(1)的查找
        this.map.set(key, this.doubleLinkedList.tail);
    }

    print() {
        console.log("output1: ", this.map.keys());
        console.log("output2: ", this.doubleLinkedList.toArray());
    }
}

可以在leetcode上做题：

bookmark