FIFO是最简单的缓存算法。设置缓存的上限。当达到缓存的上限时，会按照先进先出的策略进行淘汰，然后加入新的k-v。一个对象作为缓存，通过一个数组匹配对象中记录的添加顺序来判断是否达到上限。如果达到上限，则取数组中的第一个元素键，对应删除对象中的键值。/***FIFO队列算法实现缓存*需要一个对象和一个数组作为辅助*数组记录入口顺序*/classFifoCache{constructor(limit){this.limit=limit||10this.map={}this.keys=[]}set(key,value){letmap=this.mapletkeys=this.keysif(!Object.prototype.hasOwnProperty.call(map,key)){if(keys.length===this.limit){deletemap[keys.shift()]//先进先出，删除队列第一个元素}keys.push(key)}map[key]=value//判断map中的key是否存在赋值}get(key){returnthis.map[key]}}module.exports=FifoCacheLRULRU(Leastrecentlyused，最近最少使用)算法。该算法的观点是，最近被访问过的数据在未来被访问的概率更高。当缓存已满时，最不感兴趣的数据将首先被淘汰。算法实现思路：基于双链表的数据结构，如果没有全成员，则将新的k-v放在链表的头部，每次获取缓存中的k-v，则k-v为移到最前面，缓存满的时候，先淘汰最后一个。双向链表的特点是有头指针和尾指针，每个节点都有prev（前驱）和next（后继）指针，分别指向它的前一个和后一个节点。重点：双链表插入过程中要注意顺序。在保持链表不间断的情况下，必须先处理指针，最后将原来的头指针指向新插入的元素。代码实现中，请关注我的注释中说明的顺序！classLruCache{constructor(limit){this.limit=limit||10//head指针指向header元素，这是最常用的元素this.head=this.tail=undefinedthis.map={}this.size=0}get(key,IfreturnNode){letnode=this.map[key]//如果找不到包含属性`key`的缓存对象if(node===undefined)return//如果找到缓存对象已经尾巴（最近使用）if(node===this.head){//判断该节点是否为首节点//如果是，则皆大欢喜，不移动元素直接返回returnnode?node:node.value}//不是头节点，必须移动元素if(node.prev){//首先要判断节点是否有前驱if(node===this.tail){//有前驱，如果是tail节点，再一步，让tail指针指向当前节点的前驱this.tail=node.prev}//交出当前节点的后继者指向当前节点的前任者。node.prev.next=node.next}if(node.next){//判断节点是否有后继//如果有后继，直接让后继的前驱指向当前节点节点的前驱.next.prev=node.prev//整个过程就是取出当前节点，并保证链表是连续的，将当前节点移到下方}node.prev=undefined//移到最前面，所以没有前驱node.next=this.head//注意！！！这里首先要接过之前的leader！！！！让当前节点的后继指向原来的headif(this.head){this.head.prev=node//让前一个head的前驱指向当前节点}this.head=node//这一步交接完成后才能进行！否则，你就找不到以前的领导了！返回IfreturnNode？node:node.value}set(key,value){//之前的算法可以直接存储k-v，现在需要将简单的k-v封装成一个满足双链表的节点//1.检查是否已经有这个Nodeletnode=this.get(key,true)if(!node){if(this.size===this.limit){//判断缓存是否达到上限//已到达，应删除最后一个节点。if(this.tail){this.tail=this.tail.prevthis.tail.prev.next=undefined//平滑断开后，销毁当前节点this.tail.prev=this.tail.next=undefinedthis.map[this.tail.key]=undefined//当前缓存内存释放一个slotthis.size--}node={key:key}this.map[key]=nodeif(this.head){//判断缓存中有没有节点this.head.prev=nodenode.next=this.head}else{//缓存中没有值，大家开心，直接让head指向新节点就可以了this.head=nodethis.tail=node}this.size++//减少一个缓存槽}}//节点存在与否都要重新赋值node.value=value}}module.exports=LruCache具体思路是如果待获取的节点不是头节点点（即已经是最近使用过的节点，无需移动节点位置）先进行平滑断开操作，处理指针指针对关系，取出需要移到最前面的结点，进行链表的插入操作
