数据结构与算法之LRU: 实现 LRU 缓存算法功能 (Javascript版)

关于LRU缓存

• LRU - Lease Recently Used 最近使用

• 如果内存优先，只缓存最近使用的，删除 ‘沉睡’ 数据

• 核心 api: get set

• 分析

  • 使用哈希表来实现, O(1)
  • 必须是有序的，常用放在前面，沉睡放在后面, 即：有序，可排序
  • 这样 {} 不符合要求；Map是可以排序的，按照设置顺序

class LRUCache {private length: numberprivate data: Map<any, any> = new  Map()constructor(length: number) {if (length < 1) throw new Error('invalid length')this.length = length}set(key: any, value: any) {const data = this.dataif (data.has(key)) {data.delete(key)}data.set(key, value)if (data.size > this.length) {// 如果超出了容量，则删除 Map 最老的元素const delKey = data.keys().next().valuedata.delete(delKey)}}get(key: any): any {const data = this.dataif(!data.has(key)) return nullconst value = data.get(key)data.delete(key)data.set(key, value) // 保持最新的return value}
}const lruCache = new LRUCache(2)
lruCache.set(1, 1) // { 1=1 }
lruCache.set(2, 2) // { 1=1,  2=2 }
lruCache.get(1) // 1 {2=2, 1=1}
lruCache.set(3,3) // {1=1, 3=3}
lruCache.get(2) // null
lruCache.set(4,4) // {3=3, 4=4}
lruCache.get(1) // null
lruCache.get(3) // {4=4, 3=3}
lruCache.get(4) // 4 {3=3, 4=4}

不用 Map 如何实现 LRU 缓存

• 注意：有序
• 结合 Object + Array
• 将Array改造成双向链表

const obj1 = {value: 1, key: 'a'}
const obj2 = {value: 2, key: 'b'}
const obj3 = {value: 3, key: 'c'}const data = [obj1, obj2, obj3]
const map =  {'a': obj1, 'b': obj2, 'c': obj3}

• 上述数据结构很精妙

interface IListNode {value: anykey: stringprev?: IListNodenext?: IListNode
}export default class LRUCache {private length: numberprivate data: { [key: string]: IListNode } = {}private dataLength: number = 0private listHead: IListNode | null = nullprivate listTail: IListNode | null = nullconstructor(length: number) {if (length < 1) throw new Error('invalid length')}private moveToTail(curNode: IListNode) {const tail = this.listTailif (tail === curNode) return// 1. 让 pre next 断绝与 curNode的关系const preNode = curNode.prevconst nextNode = curNode.nextif (prevNode) {if (nextNode) {preNode.next = nextNode} else {delete prevNode.next}}if (nextNode) {if (prevNode) {nextNode.prev = prevNode} else {delete nextNode.prev}if (this.listHead === curNode) this.listHead = nextNode}// 2. 让 curNode 断绝与 prev， next的关系delete curNode.prevdelete curNode.next// 3. 在list 末尾重新建立 curNode 的新关系if (tail) {tail.next = curNodecurNode.prev = tail}this.listTail = curNode}private tryClean() {while(this.dataLength > this.length) {const head = ths.listHeadif (!head) throw new Error('head is null')const headNext = head.nextif (!headNext) throw new Error('headNext is null')// 1. 断绝head和next的关系delete headNext.prevdelete head.next// 2. 重新赋值 listHeadthis.listHead = headNext// 3. 清理 data, 重新计数delete this.data[head.key]this.dataLength -= 1}}get(key: string):any {const data = this.dataconst curNode  = data[key]if (!curNode) return nullif (this.listTail === curNode) {reutrn curNode.vlaue}// curNode 移动到末尾this.moveToTail(curNode)}set(key: string, value: any) {const data = this.dataconst curNode  = data[key]if (!curNode) {// 新增数据const newNode: IListNode = {key, value}// 移动到末尾this.moveToTail(newNode)data[key] = newNodethis.dataLength ++if (this.dataLength === 1) this.listHead = newNode} else {// 修改现有数据curNode.value = value// 移动到末尾this.moveToTail(curNode)}// 长度超过了，则需要清理this.tryClean()}
}

功能性测试

const lruCache = new LRUCache(2)
lruCache.set('1', 1) // { 1=1 }
lruCache.set('2', 2) // { 1=1,  2=2 }
lruCache.get('1') // 1 {2=2, 1=1}
lruCache.set('3',3) // {1=1, 3=3}
lruCache.get('2') // null
lruCache.set('4',4) // {3=3, 4=4}
lruCache.get('1') // null
lruCache.get('3') // {4=4, 3=3}
lruCache.get('4') // 4 {3=3, 4=4}

• 数据结构设计：data 和 list 分别存储什么
• 双向链表的操作非常繁琐，代码很容易写错， 不易调试
• 链表 node 要存储 node.key, 否则需要遍历 data 删除