网络技术分享-LRU缓存淘汰算法

在了解LRU之前，我们应该先了解一下缓存。我们都知道电脑有高速缓存，可以暂时存放最常用的数据。当缓存数据超过一定大小时，系统会对其进行回收。为了腾出空间来缓存新的数据，但是从系统中检索数据的成本比较高。CacheRequirements:FixedSize:缓存需要有一定的限制来限制内存的使用。快速访问：缓存插入和查找操作应该很快，最好是O(1)时间。达到内存限制时替换条目：缓存应该有一个高效的算法来在内存满时驱逐条目如果提供缓存替换算法来辅助管理，根据设置的内存大小，删除最少使用的数据并回收它在系统之前主动释放空间会让整个检索过程非常快，于是出现了LRU缓存淘汰算法。LRU原理及实现LRU（LeastRecentlyUsed）缓存淘汰算法提出最近频繁访问的数据应该有更高的保留，淘汰那些不经常访问的数据，即最近使用的数据将有很大的概率被再次使用。丢弃最长时间未访问的数据的目的是为了方便以后更快地获取数据。比如Vue的keep-live组件就是LRU的一种实现。实现的中心思想分为以下几个步骤：向链表头部插入新数据。每当缓存命中（即缓存数据被访问），数据就被移到链表的头部。当缓存内存满时（链表满时），淘汰链表尾部的数据。Example这里用一个例子来说明LRU的实现过程，具体可以参考这里。一开始内存空间是空的，所以依次输入A、B、C是没有问题的。添加D的时候出现问题，内存空间不够，所以根据LRU算法，A在内存空间停留时间最长的，选择A，淘汰掉。当B再次被引用时，内存空间中的B又被激活，C成为内存空间中最久未被使用的那个。当E再次加入内存空间时，此时内存空间再次不足。选出在内存空间中时间最长的C，将其从内存中淘汰。此时内存空间中存放的对象为E->B->D。基于双向链表和HashMap，常见的LRU实现LRU算法是基于双向链表和HashMap实现的。双向链表：用于管理缓存数据节点的顺序，新数据和缓存命中（最近访问过）的数据放在Header节点，尾节点根据内存大小淘汰。HashMap：存储所有节点的数据，当LRU缓存命中（用于数据访问）时，拦截并进行数据替换和删除操作。双向链表双向链表是许多链表中的一种。链表采用链式存储结构。链表中的每个元素称为数据节点。每个数据节点包含一个数据字段和一个指针字段。指针域可以决定节点之间的顺序，通过更新数据节点指针域的指向可以更新链表的顺序。双向链表的每个数据节点包含一个数据域和两个指针域：proir指向前一个数据节点；data指向当前数据节点的数据；next指向下一个数据节点；指针域决定了链表的顺序，那么双向链表有一个双向指针域，数据节点不是单指向的，而是双向指向的。即proir指针域指向上一个数据节点，next指针域指向下一个数据节点。同理：单向链表只有一个指针域。循环（circular）链表有一个双向指针域，头节点的指针域指向尾节点，尾节点的指针域指向头节点。特殊节点：Header和Tailer节点的链表中有两个特殊节点，即Header节点和Tailer节点，分别代表头节点和尾节点，头节点代表最新数据或Cache命中（最近accesseddata），尾节点代表一个长时间没有被使用，即将被淘汰的数据节点。作为一个算法，大家会关注它的时间和空间复杂度O(n)。基于双向链表的双向指针字段的优点，为了降低时间复杂度，从而保证LRU的新数据和缓存命中的数据位于链表的最前面(Header)，缓存消除时删除最后一个节点(Tailer)，避免从头到尾遍历数据，降低算法的时间复杂度。同时，基于双向链表带来的优势，可以改变各个数据节点的指针字段，从而实现链表数据的更新，如果提供Header和Tailer节点作为标识，则headerinsertion方法可以用来快速增加节点。根据Tailer节点的说法，链表的顺序也可以在缓存被淘汰的时候快速更新，避免从头到尾的遍历，降低算法的时间复杂度。排序示例LRU链表中有[6,5,4,3,2,1]6个数据节点，其中6所在的数据节点为Header节点，1所在的数据节点为Tailer（尾巴）节点。如果此时访问了数据3（缓存命中），则应该将3更新到链表的头部。想到一个数组应该删除3，但是如果我们利用双向链表的双向指针，我们可以顺便快速实现链表的更新：3被删除的时候，4和4之间没有其他结点2，即4的下一个指针字段指向2所在的数据节点；同理，2的proir指针字段指向2所在的数据节点。HashMap至于为什么要用HashMap，一句话可以概括，主要是HashMap通过Key可以更快的获取，从而降低了算法的时间复杂度。比如：当我们从HashMap中获取缓存时，时间复杂度基本控制在O(1)，而如果我们从链表遍历一次，时间复杂度为O(n)。当我们访问一个已经存在的节点时，我们需要将这个节点移动到头节点。这时候我们需要删除链表中的这个节点，在表头后面添加一个新的节点。这时候先去HashMap获取节点删除节点关系，避免从链表遍历，时间复杂度从O(N)降低到O(1)。由于前端没有HashMap相关的API，我们可以使用Object或者Map来代替。代码实现现在让我们利用掌握的数据结构来设计实现一个，或者参考LeeCode146题。链表节点EntryexportclassEntry{value:Tkey:string|numbernext:Entryprev:Entryconstructor(val:T){this.value=val;}}双链表主要职责：在向头节点和尾节点插入新数据时，将新数据移动到头节点。删除数据时，更新被删除节点前后两个节点的指向字段/***简单双链表。相对于数组，删除操作复杂度为O(1)。*@constructor*/exportclassLinkedList{head:Entrytail:Entryprivate_len=0/***在尾部插入一个新值*/insert(val:T):Entry{constentry=newEntry(val);this.insertEntry(入口);返回入口；}/***在尾部插入一个条目*/insertEntry(entry:Entry){if(!this.head){this.head=this.tail=entry;}else{this.tail.next=entry;entry.prev=this.tail;entry.next=null;this.tail=入口；}这个._len++；}/***删除条目。*/remove(entry:Entry){constprev=entry.prev;constnext=entry.next;if(prev){prev.next=next;}else{//是头this.head=next;}if(next){next.prev=prev;}else{//是尾巴this.tail=prev;}entry.next=entry.prev=null;这。_len--;}/***获取长度*/len():number{returnthis._len;}/***清除列表*/clear(){this.head=this.tail=null;这个._len=0;}}LRU核心算法主要职责：向链表添加数据并更新链表序列当缓存命中时更新链表序列内存溢出丢弃过时的链表数据/***LRUCache*/exportdefaultclassLRU{private_list=newLinkedList()private_maxSize=10private_lastRemovedEntry:Entryprivate_map:Dictionary>={}constructor(maxSize:number){this._maxSize=maxSize;}/***@return删除的值*/put(key:string|number,value:T):T{constlist=this._list;constmap=this._map;让删除=空；if(map[key]==null){constlen=list.len();//重用最后删除的条目letentry=this._lastRemovedEntry;if(len>=this._maxSize&&len>0){//移除最近最少使用的constleastUsedEntry=list.head;list.remove(leastUsedEntry);删除地图[leastUsedEntry.key]；removed=leastUsedEntry.value;this._lastRemovedEntry=leastUsedEntry;}if(entry){entry.value=value;}else{entry=newEntry(value);}entry.key=键；list.insertEntry(条目);地图[键]=条目；返回删除；}get(key:string|number):T{constentry=this._map[key];constlist=this._list;if(entry!=null){//将最近使用的条目放在尾部if(entry!==list.tail){list.remove(entry);list.insertEntry(条目);}返回条目。值；}}/***清除缓存*/clear(){this._list.clear();这个._map={};}len(){返回this._list.len();}}其他LRU算法除了上面常见的LRU算法，随着需求越来越复杂多样，基于LRU的思想也衍生出了很多优化算法，比如：LRU-K算法LRU-双队列（2Q）算法LRU-多队列（MQ）算法LFU算法LRU变体算法参考链接Zrender-LRU知乎-存款淘汰算法--LRU算法LRU算法LRU策略详解及实现