LRU (最近最少使用) 缓存实现的两种方式

1
2
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
// 第一种方式Map方式
// Map中set加入的键值对是按照次序依次进入，比如
// var le=new Map([['0','a'],['1','b']]);
// le.keys() //{'0', '1'}
// le.keys().next() //{value: '0', done: false}
// le.keys().next().value   // '0' 得到第一个键值对的键值
var LRUCache = function (capacity) {
  this.cache = new Map();
  this.capacity = capacity;
};

LRUCache.prototype.get = function (key) {
  if (this.cache.has(key)) {
    // 保存key对应的value，删除key值，将其重新添加进数组
    let temp = this.cache.get(key);
    // 删除key对应键值对
    this.cache.delete(key);
    this.cache.set(key, temp);
    return temp;
  }
  return -1;//没有则返回-1
};

LRUCache.prototype.put = function (key, value) {
  if (this.cache.has(key)) {//如果存在
    // 删除掉这个键值对，在下方会创建
    this.cache.delete(key);
  } else if (this.cache.size >= this.capacity) {
    // 如果数据大小大于容量，删除map键值对当中的第一个，因为map是一次往后添加，最后一个键值对是最活跃的
    // this.cache.keys()遍历出键名，.next()拿到第一个键名对象，.value得到对应键名的值，然后删除
    this.cache.delete(this.cache.keys().next().value);
  }
  this.cache.set(key, value);
};

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
//哈希+双向链表解决
// 删除值的时候链表和哈希值都需要删除
// delete this.hashTable[tail.key] 
// 添加值时全部添加
// let newNode = new ListNode(key,value)
// this.hashTable[key] = newNode
class ListNode { //定义链表
    constructor(key, value) {
        this.key = key
        this.value = value
        this.next = null
        this.prev = null
    }
}
class LRUCatch {
    constructor(capacity){
        this.capacity = capacity
        this.hashTable = {} //对象，用来
        this.count = 0
        this.dummyHead = new ListNode() //虚拟头节点
        this.dummyTail = new ListNode() //虚拟尾节点
        this.dummyHead.next = this.dummyTail //因为刚开始暂时还没有真实的节点，让虚拟头节点和尾节点相连
        this.dummyTail.prev = this.dummyHead
    }
    get(key) { //查询节点
        let node = this.hashTable[key]
        if(node == null) return -1
        this.moveToHead(node)
        return node.value
    }
    put(key,value){//可能原来有这个数据则更新value，没有则添加
        let node = this.hashTable[key] //拿到传入key的node值
        if(node == null){//如果查找不到，写入新数据
            let newNode = new ListNode(key,value)
            this.hashTable[key] = newNode
            this.count++ //代表内存多了一个
            this.addToHead(newNode) //因为刚进来，所以在最上面最不肯删除
            if(this.count > this.capacity){
                this.removeLRUItem() //移除最后一个值
            }
        }else{ //如果原来存在，更新value值
            node.value = value
            this.moveToHead(node) //移动到链表头部
        }
    }
    removeLRUItem(){
        let tail = this.popTail() //删除尾节点并返回
        delete this.hashTable[tail.key] //对应的哈希表这个值也要删除
        this.count-- //移除一个元素，代表空间数量减一
    }
    popTail(){
        let tail = this.dummyTail.prev //获取到尾节点
        this.removeFromList(tail) //删除尾节点
        return tail
    }
    moveToHead(node){
        this.removeFromList(node) //先将这个节点移除
        this.addToHead(node) //然后把这个节点添加道头部
    }
    removeFromList(node){// 移除node节点
        // 设置node节点前后的指针，使其不在指向node，node就被删除
        let tempForPrev = node.prev //node前一个节点
        let tempForNext = node.next //node后一个节点
        tempForPrev.next = tempForNext //将指针下一个指向node的下一个节点
        tempForNext.prev = tempForPrev //将指针下一个指向node的前一个节点
    }
    // 添加node到头部
    addToHead(node){
        // 定义一个在head部之前的虚拟头节点，利用这个虚拟头节点实现将node插入到头部
        node.prev = this.dummyHead //node的前一个指针指向虚拟头节点
        node.next = this.dummyHead.next //node的后一个指向虚拟节点的下一个节点
        node.prev.next = node //虚拟节点的下一个指向node
        node.next.prev = node // 虚拟节点的下一个指针的前节点指向node
    }
}