利用LRU(哈希链表)实现本地缓存

利用LRU(哈希链表)实现本地缓存

Tags
缓存设计
LRU算法
哈希算法
链表
CreatedTime
Aug 19, 2022 10:44 AM
Slug
2022-01-23-lru-cache
UpdatedTime
Last updated August 19, 2022

认识哈希链表

notion image
本质就是:散列表+链表。它被用于实现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,并且定义缓存节点类型:
const yallist = require("yallist"); // key: 缓存键名 // value:缓存值 class Node { constructor(key, value) { this.key = key; this.value = value; } }
实现LRU:
/** * 为什么链表中节点要存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上做题: