缓存淘汰算法--LRU算法

LRU（Least recently used，最近最少使用)算法根据数据的历史访问记录淘汰数据，其核心思想是如果数据最近被访问，未来更有可能被访问。详细算法如下:

优缺点：

• 当有热点数据时，LRU效率很好，但偶尔、周期性的批量操作会导致LRU命中率急剧下降，缓存污染严重。
• 在命中时，需要遍历链表，找到命中的数据块索引，然后将数据移到头部。

LRU-KK代表最近使用的次数，所以LRU可以认为是LRU-1。LRU-K主要目的是解决LRU算法缓存污染的核心思想是将最近使用一次的判断标准扩展到最近使用K次。详细算法如下：

1. 第一次访问数据，加入访问历史列表；
2. 访问历史列表中的数据未达到K次访问的，按照一定的规则（FIFO，LRU）淘汰；
3. 当访问历史队列中的数据访问次数达到K次时，从历史队列中删除数据索引，将数据移动到缓存队列，缓存队列按时间重新排序；
4. 再次访问缓存数据队列后，重新排序；
5. 在需要淘汰数据时，淘汰缓存队列中排在最后的数据，即淘汰倒数第K次访问最长的数据。

优缺点：

• LRU-K减少了缓存污染带来的问题LRU要高。LRU-K队列是算法复杂，算法复杂，成本高。
• 由于LRU-K还需要记录被访问但没有放入缓存的对象，所以内存消耗会比LRU更多；当数据量很大时，内存消耗会相当可观。
• LRU-K需要根据时间进行排序(可以在淘汰时进行排序，也可以立即排序)，CPU消耗比LRU要高。

public class LRUCache {        private int cacheSize;//缓存大小       private Hashtable nodes;////缓存容器       private int currentSize;////       private CacheNode first;//(实现双链表)链表头       private CacheNode last;//(实现双链表)链表尾           /**       * 链表节点       * @author Administrator       *       */       class CacheNode {           CacheNode prev;//前一节点           CacheNode next;//后节点           Object value;//值           Object key;//键           CacheNode() {           }       }       public LRUCache(int i) {           currentSize = 0;           cacheSize = i;           nodes = new Hashtable(i);////缓存容器       }              /**       * 获取缓存中的对象       * @param key       * @return       */       public Object get(Object key) {           CacheNode node = (CacheNode) nodes.get(key);           if (node != null) {               moveToHead(node);               return node.value;           } else {               return null;           }       }              /**       * 添加缓存       * @param key       * @param value       */       public void put(Object key, Object value) {           CacheNode node = (CacheNode) nodes.get(key);                      if (node == null) {               ///缓存容器是否超过了大小.               if (currentSize >= cacheSize) {                   if (last != null)///删除最少使用的删除                       nodes.remove(last.key);                   removeLast();               } else {                   currentSize  ;               }                              node = new CacheNode();           }           node.value = value;           node.key = key;           将最新使用的节点放在链表头，表示最新使用.           moveToHead(node);           nodes.put(key, node);       }       /**       * 将缓存删除       * @param key       * @return       */       public Object remove(Object key) {           CacheNode node = (CacheNode) nodes.get(key);           if (node != null) {               if (node.prev != null) {               if (node.prev != null) {                   node.prev.next = node.next;               }               if (node.next != null) {                   node.next.prev = node.prev;               }               if (last == node)                   last = node.prev;               if (first == node)                   first = node.next;           }           return node;       }       public void clear() {           first = null;           last = null;       }       /**       * 删除链表尾部节点       *  表示 删除最少使用的缓存对象       */       private void removeLast() {           //链表尾不为空,指向链表的尾部null. 删除连表尾(删除最少使用的缓存对象)           if (last != null) {               if (last.prev != null)                   last.prev.next = null;               else                   first = null;               last = last.prev;           }       }              /**       * 移动到链表头，这个节点是最新使用的       * @param node       */       private void moveToHead(CacheNode node) {           if (node == first)               return;           if (node.prev != null)               node.prev.next = node.next;           if (node.next != null)               node.next.prev = node.prev;           if (last == node)               last = node.prev;           if (first != null) {               node.next = first;               first.prev = node;           }           first = node;           node.prev = null;           if (last == null)               last = first;       }    } 

为了方便大家刷题，我们对文章进行了分类整理，免费为大家提供刷题服务。程序员不欺骗程序员，赶紧扫码刷小程序！

为了一站式解决面者刷题问题，部分内容可能存在摘录情况，如有侵权辛苦您留言联系我们，我们会删除文章或添加引用文案，Thanks！！