LRU即LeastRecentlyUsed，即最近最少使用。是一种常用的页面置换算法。淘汰最近长时间不用的页面其实很简单。及时淘汰不受欢迎的页面，以免让他们占坑拉屎，浪费资源。LRU是一种常见的页面置换算法。在计算中，所有的文件操作都必须在内存中进行。但是计算机内存的大小是固定的，所以我们不能把所有的文件都加载到内存中，所以我们需要制定一种策略来为文件添加到内存中选择项目。常见的页面置换算法如下：LRU最长时间没有使用过FIFO。先进先出替换算法类似于队列OPT。最优替换算法（理想中存在）NRU时钟替换算法LFU最少使用替换算法PBAPagebuffer算法LRU原理LRU的设计原理是当数据在最近一段时间被频繁访问时，将来也会被频繁访问。这意味着如果访问频繁的数据，我们需要能够快速命中它，而访问不频繁的数据，我们必须在容量超过限制时淘汰它。它的核心是利用栈来进行运算。主要有两个操作，get和putgetget，如果栈中有值，则将该值的key提升到栈顶，如果没有值，则返回null。当栈未满时，若栈中有key可放，则更新key对应的value，将key的值带入栈顶。如果没有key可放，直接push入栈。当栈满时，如果有键入栈，则更新这个键对应的值，并将键值提到栈顶；如果栈中没有putkey，则移除栈底元素，将putvalue放入栈顶解决方法：维护一个数组，提供get和put方法，限制最大数量。使用时，get可以将一个元素标记为最近使用过的，将其提升到第一项。Put可以添加某个key-value，但是需要判断是否达到了最大限制max。如果没有，它可以直接插入数组的第一项。如果达到最大限制max，则需要剔除数据末尾的一个元素。LRUCachecache=newLRUCache(2/*缓存容量*/);cache.put(1,1);cache.put(2,2);cache.get(1);//返回1cache.put(3,3);//这个操作会让key2失效cache.get(2);//返回-1（没有找到）cache.put(4,4);//这个操作会让key1失效cache.get(1);//return-1(notfound)cache.get(3);//return3cache.get(4);//return4LRU算法设计分析以上操作过程，使put和get方法的时间复杂度为O(1)、我们可以总结出缓存数据结构的必要条件：快速查找、快速插入、快速删除、有序。因为显然缓存必须有一个序列来区分最近使用和长期未使用的数据；并且我们需要找出缓存中是否已经存在该键；如果容量已满，我们需要删除最后的数据；每次访问行首时都需要插入数据。那么，什么数据结构同时满足以上条件呢？哈希表查找速度快，但数据无固定顺序；链表有顺序，插入删除速度快，查找速度慢。于是将它们组合起来形成一个新的数据结构：哈希链表。LRU缓存算法的核心数据结构是哈希链表，是双向链表和哈希表的结合。这个数据结构是这样的：js实现了具体的代码。一般的解决方案是维护一个数组，数组项存储key-value键值对。每次都需要遍历找到key值所在的数组下标。已通过leetCode146的测试，执行时间：720ms。内存消耗：58.5MB。functionLRUCache(capacity){this.capacity=capacity;//最大限制this.cache=[];};/***@param{number}key*@return{number}*/LRUCache.prototype.get=function(key){letindex=this.cache.findIndex((item)=>item.key===key);if(index===-1){return-1;}//删除这个元素，插入到数组Aletvalue=this.cache[index].value;this.cache.splice(index,1);this.cache.unshift({key,value,});returnvalue;};/***@param{number}key*@param{number}value*@return{void}*/LRUCache.prototype.put=function(key,value){letindex=this.cache.findIndex((item)=>item.key===key);//你要插入的数据已经存在，直接升级即可if(index>-1){this.cache.splice(index,1);}elseif(this.cache.length>=this.capacity){//如果已经达到最大限制，先剔除一个长时间没有使用的this.cache.pop();}this.cache.unshift({key,value});};上面的方法其实还有变体一个对象可以用来存储键值对，一个数组可以用来存储键的顺序。进阶需要O(1)时间复杂度O(1)，则无法遍历数组找到key值。可以使用ES6的Map来解决，因为Map不仅可以维护键值对，还可以记住插入的顺序。functionLRUCache(capacity){this.cache=newMap();this.capacity=capacity;//最大限制};LRUCache.prototype.get=function(key){if(this.cache.has(key)){//存在更新lettemp=this.cache.get(key);this.cache.delete(key);this.cache.set(key,temp);returntemp;}return-1;};LRUCache.prototype.put=function(key,value){if(this.cache.has(key)){//存在更新（删除后添加）this.cache.delete(key);}elseif(this.cache.size>=this.capacity){//不存在则加入//如果缓存超过最大值，则移除this.cache.delete(this.cache.keys().next().value);}this.cache.set(key，价值）;};
