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

93 阅读 0 评论 62 点赞

我是靠谱客的博主勤恳御姐，最近开发中收集的这篇文章主要介绍LRU (最近最少使用) 缓存实现的两种方式，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目如下

LRU最近最少使用，是一种常用的页面置换算法，在容量一定的情况下，删除内存中最近最久未使用的数据。

首先第一种方式：Map

利用在Map当中键值的方式进行存储数据，它的特性就是我们新加入set进去的键值对在其内部是有顺序排列的，及我们set一个键值对它就会去放在后面，这时如果我们容量已满，那么只需要删除掉第一个键值即可（因为常使用（把他移到后方）的和新进入的都会在后方添加进去），然后就实现了一个LRU算法
具体解释都已在代码详细注释

// 第一种方式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);
};

在这里插入图片描述

第二种方式哈希表+双向链表

为什么要用这种方式实现？

如果只用哈希表是无序的存储，不可能知道哪些是刚使用的还是最久未使用的，不可能全部遍历添加时间来实现，所以不推荐，如果是利用数组的话，插入和移动元素以及删除，那么其时间复杂度达到O（n）,所以不推荐，如果是链表，使用单向链表我们必须去使用指向前一个指针，只能去遍历查找，时间复杂度又达到O(n)，所以不推荐，使用双向链表利用指针去实现，有前后指针，时间复杂度为O(1)可以采用。
我们只要在哈希表中存一个key，这就是一个寻找地址，利用这个地址去链表找到对应的值即可（链表和哈希表的key值是相同的）
具体解释都已在代码详细注释

//哈希+双向链表解决
// 删除值的时候链表和哈希值都需要删除
// 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
    }
}