LRU：最近最少使用
题目描述
image
算法设计
cache这个数据结构需要具备以下条件：
- 元素必须有时序，当容量满了以后要删除最久未使用的元素
- get方法要求在O(1)的时间复杂度内，快速找到cache中是否存在某个key
- 每次调用get方法，需要将被访问元素变为最近使用的，即cache要支持在O(1)的时间复杂度内插入和删除元素
- put方法要求在O(1)的时间复杂度内，将写入数据变为最近使用的
我们知道，哈希表支持快速查找，而链表支持快速插入和删除
因此我们需要结合哈希表和双向链表：
- 哈希表的key是题目提供的key，而value则是指向链表节点的指针
- 链表中的每个节点都有key和val两个属性
并规定：
- 每次默认从链表尾部添加元素，越靠近尾部就越是最近使用的
- 对于get方法，可以通过哈希表取出节点的val值
- 对于put方法，先删除链表的第一个节点，再将其插入到链表尾部即可
代码实现（JavaScript）
定义节点类：
class Node {
constructor(k,v){
this.key = k
this.val = v
}
}
定义双向链表类：
- 构造函数：初始化两个虚拟的头尾节点
- addLast(x)：向链表尾部添加节点x
- removeNode(x)：删除链表中的节点x
- removeFirst()：删除并返回链表的第一个节点
class DoubleList {
constructor(){
this.head = new Node(0,0)
this.tail = new Node(0,0)
this.head.next = this.tail
this.tail.prev = this.head
this.size = 0
}
addLast(x){
x.prev = this.tail.prev
x.next = this.tail
this.tail.prev.next = x
this.tail.prev = x
this.size++
}
removeNode(x){
x.prev.next = x.next
x.next.prev = x.prev
this.size--
}
removeFirst(){
if(this.size === 0){
return null
}
var first = this.head.next
this.head.next = first.next
first.next.prev = this.head
this.size--
return first
}
}
定义构造函数LRUcache
var LRUCache = function(capacity) {
this.list = new DoubleList()
this.map = new Map()
this.capacity = capacity
};
编写get方法：
- 通过map找到指定key的节点x
- 从链表中删除节点x
- 将节点x添加到链表尾部
- 更新map
- 返回节点x的val值
LRUCache.prototype.get = function(key) {
if(!this.map.has(key)){
return -1
}
let tempNode = this.map.get(key)
this.list.removeNode(tempNode)
this.list.addLast(tempNode)
this.map.set(key,tempNode)
return tempNode.val
};
编写put方法：
若key已存在：
- 通过map找到指定key的节点x
- 从链表中删除节点x
- 更新节点x的val值，更新map
- 将节点x添加到链表尾部
若key不存在：
- 若容量已满，删除链表第一个节点，更新map
- 创建节点x，指定其key和val
- 将节点x添加到链表尾部
LRUCache.prototype.put = function(key, value) {
if(this.map.has(key)){
let tempNode = this.map.get(key)
this.list.removeNode(tempNode)
tempNode.val = value
this.map.set(key,tempNode)
this.list.addLast(tempNode)
}else{
if(this.list.size === this.capacity){
let deleteNode = this.list.removeFirst()
this.map.delete(deleteNode.key)
}
let tempNode = new Node(key,value)
this.list.addLast(tempNode)
this.map.set(key,tempNode)
}
};
