十分钟看懂JS的LRU Cache 算法(下)

我心飞翔 分类:javascript

上文介绍了LRU Cache的场景点击回顾,以及在es6前提下可以借助Map结构来解决,而本文将介绍在es5条件下,更加根正苗红不取巧的解决方案。

image.png

还是简单介绍下场景要求,方便没看前一篇的同学也能直接看(顺便凑点字数):

当用户访问不同站点时,浏览器需要缓存在对应站点的一些信息,当下次访问同一个站点的时候,通过读取缓存就可以实现更快速的访问。缓存的分配空间是有限的,所以当空间不足时,需要优先删除最近不经常使用的数据,实现缓存的管理。

需求整理

把上述场景问题进一步整理成代码需求:请实现一个class,提供以下功能:

  1. 提供put方法,用于写入不同的缓存数据,假设每条数据形式是{'域名','info'},例如{'https://segmentfault.com': '一些关键信息'}(如果是同一域名重复写入,则新写入覆盖旧数据);
  2. 当缓存达到上限时, 调用put写入缓存之前, 要删除最近最少使用的数据
  3. 提供get方法,用于读取缓存数据,同时需要把被读取的数据,移动到最近使用数据 ;
  4. 考虑到性能问题,希望getset的操作的复杂度是O(1)(简单理解就是,不能使用遍历)

数据选型

同样的,先考虑数据结构的选择,既然是es5那么可选的只有ArrayObject了,array通常用于需要表示顺序的数据结构,但是从上一篇文章我们可以知道,算法实现的核心,在于维持新插入的数据排在后面,旧数据放在前面的顺序,所以每次读取数据之后需要重排序,来维持这个顺序。而用数组存放数据的话,排序一定躲不开遍历,那就不符合前面的第四条,所以只能考虑Object,用Object如何表示顺序呢? 就必须要用到链表结构了。

链表介绍

基本内容

考虑到本篇文章的部分读者有可能第一次接触链表结构,还是在这里做一下简要的介绍,熟悉的读者可以跳过本节。

image.png

链表结构如上图所示,是由一些节点以及节点之间的指针串联起来的。(颜色是为了方便区分属于哪个节点的指针)

  • A``B``C``D属于常规节点,HeadTail虚拟的头部和尾部节点,这是为了方便找到链表的首末设定的;
  • 对于每个节点而言,它只会记住它的前后位置(如果是单向链表,就只需要记住一个方向;如果是双向链表,就需要分别记住前面和后面的节点,上图是双向链表)并用prenext指针来访问;

Head节点 的preTail节点next都指向null

操作图解

还是以双向链表为例,从末尾增加节点时如图所示,只需改动Tail以及实际末尾节点(本例中是D)的指针即可(关注红色线框标的节点即可):

图片

删除节点则如图(以c节点为例)只需要把该节点前后节点连接,并且把自身的两个指针指向null即可:

图片

移动节点的方式同样借用前文里”移动节点等于先删除后重新从首位插入“这个思路。

图片

如图所示,假设C节点 被get方法读取,那么需要把C节点移到链表最前端,实现从左到右的变化,看似复杂,实际上只要执行以下伪代码:

// 将节点移动到首位
moveToHead(node) {
  if(node){
     // 把B和D连起来
    node.pre.next  = node.next;// B的next指针指向D
    node.next.pre = node.pre; // D的nex指针指向B
    
    // 把C节点移动到head和A之间 
    head.next.pre = node; // A节点的pre指针 指向C
    node.next = head.next; // C节点的next指针 指向A
    node.pre = head;  //  C节点的pre指针 指向head
    head.next = node.pre; // head的next指针 指向C
  }
}
 

其实就是修改目标节点(C)的前后指针head节点的前后指针,以及**目标节点前后节点(B和D)**的前后指针(最多就涉及到5个节点,这是固定的,所以复杂度只是O(1))。

上面步骤只是解决了重排序的复杂度问题,但是还需要处理get读取时O(1)复杂度的问题,链表结构方便排序,但是读取难度较大,所以同时我们还要维护一个hash map(哈希表),在es5下用objec可以实现,那么整个算法的难点基本完成,可以分步写代码了。

算法实现

首先,提供链表节点的类,结构就是domaininfo之外,再加一个pre指针和一个next指针:

function DoubleLinkNode (domain, info){
    this.doamin = domain;
    this.info = info;
    this.pre = null;
    this.next = null;
}
 

其次,是LRU Cache的构造函数:

function LRUCache (size){
    this.size = size;
    this.hashMap = {};
    // 初始化虚拟的头尾节点 方便找到链表头尾
    this.head = new DoubleLinkNode();
    this.tail = new DoubleLinkNode();
    this.head.next = this.tail;
    this.tail.pre = this.head;
}
 

然后一样的是先写put方法,

LRUCache.prototype.put = function (domain, info){
   // 首先判断节点是否存在,存在则更新对应信息,不存在则插入
   if(this.hashmap[domain]){
     const node = this.hashmap[domian];
     node.info = info;// 更新
     this.moveToTop(node); // todo1 将节点移动到最前面
     return ;
   } 
   // 否则插入新节点
   const size = Object.keys(this.hashmap).length;
   if(size >= this.size)}{
       // 超过容量,需要先删除最不经常使用的节点,也就是末尾节点
       const node = this.tail.pre;
       this.removeNode(node); // todo2 将节点移除
   }
   // 正常插入新节点 并添加到最前面
   const newNode =  new DoubleLinkNode(domain, info);
   this.hashMap[domain] = info;
   this.moveToTop(node);
};
 

为了阅读清晰,我们先提取了moveToTopdeleteNode方法,接下来补上实现,由于前面说过思路了,也比较简单:

LRUCache.prototype.moveToTop = function (node){
    head.next.pre = node;
    node.next = head.next;
    node.pre = head; 
    head.next = node;
};
LRUCache.prototype.deleteNode = funtion(node) {
    // 链表中移除节点实际上就是将节点的前后节点相连 孤立目标节点即可
    node.prev.next = node.next;
    node.next.prev = node.prev;
    node.prev = null;
    node.next = null; 
    
    // 别忘了还要从哈希表去掉节点的key值
    delete this.hashMap[node.domain];
   
}
 

最后是get方法, 也比较简单:

LRUCache.prototype.get(domain) = function(){
    if (!this.hashmap[domain]) {
      return false;
    }
    const node = this.hashmap[domain];
    this.deleteNode(node)
    // 因为deleteNode的时候删除了 所以要重新登记
    this.hashmap[domain] = node;
    this.moveToTop(node);
    return node.info;
};
 

小结

其实双向链表的思路相对前一篇的map实现更有普适性,这个思路不仅适用于js,在C语言和其他语言一样可以实现。而且,面试也可以拿来吹牛逼(和面试无关的都不吸睛)。

关于链表结构,有算法基础的同学可能比较熟悉,但是对于第一次接触的同学同学比较陌生,所以考虑再三还是决定写的详细一些,力求每一篇文章都尽量让读者读起来不至于太费劲,更贴合自己写博客的初衷。

此外也啰嗦一句,可能算法类和源码类的文章大家都不是很喜欢(当然也可能仅仅是这类文章我写的不够容易读懂,或者大家觉得这是屠龙技,并不实用),相对而言面经和实践知识点的文章更受欢迎,毕竟人都是有畏难情绪的,不过我觉得还是可以对这些内容都做一些了解,学习算法思路,一方面对于找工作的朋友短期就有帮助,但是对于长期从事编程行业来说,也能够增长知识,锻炼逻辑能力。

图片

总结

希望大家对于喜爱的文章,能够点赞和收藏,这样也能一定程度上给我个反馈,哪些文章写的较好,哪些文章还有不足,或者对于行文风格和内容有任何意见的,都欢迎私信交流。

最后依然是惯例,RingCentral目前在杭州也设置了办公点,而且可以申请长期远程办公,告别996,工作生活两不误,有兴趣的同学可以私信咨询(主页有联系方式),可以免费帮忙内推~

回复

我来回复
  • 暂无回复内容