LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是「如果数据最近被访问过，那么将来被访问的几率也更高」。

实现 1

最常见的实现是使用一个链表（LinkedHashMap）保存缓存数据，详细算法实现如下：
缓存淘汰算法 LRU 算法实现 - 图1

  1. 新数据插入到链表头部；
    2. 每当缓存命中（即缓存数据被访问），则将数据移到链表头部；
    3. 当链表满的时候，将链表尾部的数据丢弃。

分析
【命中率】
当存在热点数据时，LRU 的效率很好，但偶发性的、周期性的批量操作会导致 LRU 命中率急剧下降，缓存污染情况比较严重。
【复杂度】
实现简单。
【代价】
命中时需要遍历链表，找到命中的数据块索引，然后需要将数据移到头部。（LinkedList 查询慢、增删快）

代码

  1. package com.zcq.algorithm.LRU;
  3. import java.util.ArrayList;
  4. import java.util.Collection;
  5. import java.util.LinkedHashMap;
  6. import java.util.Map;
  7. import java.util.concurrent.locks.Lock;
  8. import java.util.concurrent.locks.ReentrantLock;
  10. /**
  11.  * 类说明：利用 LinkedHashMap 实现简单的缓存， 必须实现 removeEldestEntry 方法，具体参见JDK文档
  12.  *
  13.  * @param <K>
  14.  * @param <V>
  15.  */
  16. public class LRULinkedHashMap<K, V> extends LinkedHashMap<K, V> {
  18.     /**
  19.      * 容量
  20.      */
  21.     private final int maxCapacity;
  23.     /**
  24.      * 负载因子
  25.      */
  26.     private static final float DEFAULT_LOAD_FACTOR = 0.75f;
  28.     private final Lock lock = new ReentrantLock();
  30.     public LRULinkedHashMap(int maxCapacity) {
  31.         super(maxCapacity, DEFAULT_LOAD_FACTOR, true);
  32.         this.maxCapacity = maxCapacity;
  33.     }
  35.     /**
  36.      * 重写此方法来判断是否移除元素
  37.      *
  38.      * @param eldest
  39.      * @return
  40.      */
  41.     @Override
  42.     protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) {
  43.         return size() > maxCapacity;
  44.     }
  46.     @Override
  47.     public boolean containsKey(Object key) {
  48.         lock.lock();
  49.         try {
  50.             return super.containsKey(key);
  51.         } finally {
  52.             lock.unlock();
  53.         }
  54.     }
  57.     @Override
  58.     public V get(Object key) {
  59.         lock.lock();
  60.         try {
  61.             return super.get(key);
  62.         } finally {
  63.             lock.unlock();
  64.         }
  65.     }
  67.     @Override
  68.     public V put(K key, V value) {
  69.         lock.lock();
  70.         try {
  71.             return super.put(key, value);
  72.         } finally {
  73.             lock.unlock();
  74.         }
  75.     }
  77.     @Override
  78.     public int size() {
  79.         lock.lock();
  80.         try {
  81.             return super.size();
  82.         } finally {
  83.             lock.unlock();
  84.         }
  85.     }
  87.     @Override
  88.     public void clear() {
  89.         lock.lock();
  90.         try {
  91.             super.clear();
  92.         } finally {
  93.             lock.unlock();
  94.         }
  95.     }
  97.     public Collection<Map.Entry<K, V>> getAll() {
  98.         lock.lock();
  99.         try {
  100.             return new ArrayList<Map.Entry<K, V>>(super.entrySet());
  101.         } finally {
  102.             lock.unlock();
  103.         }
  104.     }
  106.     public static void main(String[] args) {
  107.         Map map = new LRULinkedHashMap(3);
  108.         map.put(1, "a");
  109.         System.out.println(map.toString());
  110.         map.put(2, "b");
  111.         System.out.println(map.toString());
  112.         map.put(3, "c");
  113.         System.out.println(map.toString());
  114.         map.put(4, "d");
  115.         System.out.println(map.toString());
  116.         map.put(1, "a");
  117.         System.out.println(map.toString());
  118.         map.put(2, "b");
  119.         System.out.println(map.toString());
  120.     }
  121. }

实现 2

LRUCache 的链表 + HashMap 实现
缓存淘汰算法 LRU 算法实现 - 图2
传统意义的 LRU 算法是为每一个 Cache 对象设置一个计数器，每次 Cache 命中则给计数器 + 1，而 Cache 用完，需要淘汰旧内容，放置新内容时，就查看所有的计数器，并将最少使用的内容替换掉。

它的弊端很明显，如果 Cache 的数量少，问题不会很大， 但是如果 Cache 的空间过大，达到 10W 或者 100W 以上，一旦需要淘汰，则需要遍历所有计算器，其性能与资源消耗是巨大的。效率也就非常的慢了。

原理： 将 Cache 的所有位置都用双连表连接起来，当一个位置被命中之后，就将通过调整链表的指向，将该位置调整到链表头的位置，新加入的 Cache 直接加到链表头中。（并且 Map 查询元素为 O(1)）

这样，在多次进行 Cache 操作后，最近被命中的，就会被向链表头方向移动，而没有命中的，而想链表后面移动，链表尾则表示最近最少使用的 Cache。

当需要替换内容时候，链表的最后位置就是最少被命中的位置，我们只需要淘汰链表最后的部分即可。

上面说了这么多的理论， 下面用代码来实现一个 LRU 策略的缓存。

非线程安全，若实现安全，则在响应的方法加锁。

  1. package com.zcq.algorithm.LRU;
  3. import java.util.HashMap;
  5. /**
  6.  * LRUCache 的链表 + HashMap 实现
  7.  *
  8.  * @param <K>
  9.  * @param <V>
  10.  */
  11. public class LRUCache<K, V> {
  13.     private int currentCacheSize;
  14.     private int cacheCapacity;
  15.     private HashMap<K, CacheNode> caches;
  16.     private CacheNode first;
  17.     private CacheNode last;
  19.     public LRUCache(int size) {
  20.         currentCacheSize = 0;
  21.         this.cacheCapacity = size;
  22.         caches = new HashMap<>(size);
  23.     }
  25.     public void put(K k, V v) {
  26.         CacheNode node = caches.get(k);
  27.         if (node == null) {
  28.             if (caches.size() >= cacheCapacity) {
  29.                 caches.remove(last.key);
  30.                 removeLast();
  31.             }
  32.             node = new CacheNode();
  33.             node.key = k;
  34.         }
  35.         node.value = v;
  36.         moveToFirst(node);
  37.         caches.put(k, node);
  38.     }
  40.     public Object get(K k) {
  41.         CacheNode node = caches.get(k);
  42.         if (node == null) {
  43.             return null;
  44.         }
  45.         moveToFirst(node);
  46.         return node.value;
  47.     }
  49.     public Object remove(K k) {
  50.         CacheNode node = caches.get(k);
  51.         if (node != null) {
  52.             if (node.pre != null) {
  53.                 node.pre.next = node.next;
  54.             }
  55.             if (node.next != null) {
  56.                 node.next.pre = node.pre;
  57.             }
  58.             if (node == first) {
  59.                 first = node.next;
  60.             }
  61.             if (node == last) {
  62.                 last = node.pre;
  63.             }
  64.         }
  66.         return caches.remove(k);
  67.     }
  69.     public void clear() {
  70.         first = null;
  71.         last = null;
  72.         caches.clear();
  73.     }
  75.     private void moveToFirst(CacheNode node) {
  76.         if (first == node) {
  77.             return;
  78.         }
  79.         if (node.next != null) {
  80.             node.next.pre = node.pre;
  81.         }
  82.         if (node.pre != null) {
  83.             node.pre.next = node.next;
  84.         }
  85.         if (node == last) {
  86.             last = last.pre;
  87.         }
  88.         if (first == null || last == null) {
  89.             first = last = node;
  90.             return;
  91.         }
  93.         node.next = first;
  94.         first.pre = node;
  95.         first = node;
  96.         first.pre = null;
  97.     }
  99.     private void removeLast() {
  100.         if (last != null) {
  101.             last = last.pre;
  102.             if (last == null) {
  103.                 first = null;
  104.             } else {
  105.                 last.next = null;
  106.             }
  107.         }
  108.     }
  110.     @Override
  111.     public String toString() {
  112.         StringBuilder sb = new StringBuilder();
  113.         CacheNode node = first;
  114.         while (node != null) {
  115.             sb.append(String.format("%s:%s ", node.key, node.value));
  116.             node = node.next;
  117.         }
  119.         return sb.toString();
  120.     }
  122.     class CacheNode {
  123.         CacheNode pre;
  124.         CacheNode next;
  125.         Object key;
  126.         Object value;
  128.         public CacheNode() {
  130.         }
  131.     }
  133.     public static void main(String[] args) {
  135.         LRUCache<Integer, String> lru = new LRUCache<>(3);
  137.         lru.put(1, "a");    // 1:a
  138.         System.out.println(lru.toString());
  139.         lru.put(2, "b");    // 2:b 1:a
  140.         System.out.println(lru.toString());
  141.         lru.put(3, "c");    // 3:c 2:b 1:a
  142.         System.out.println(lru.toString());
  143.         lru.put(4, "d");    // 4:d 3:c 2:b
  144.         System.out.println(lru.toString());
  145.         lru.put(1, "aa");   // 1:aa 4:d 3:c
  146.         System.out.println(lru.toString());
  147.         lru.put(2, "bb");   // 2:bb 1:aa 4:d
  148.         System.out.println(lru.toString());
  149.         lru.put(5, "e");    // 5:e 2:bb 1:aa
  150.         System.out.println(lru.toString());
  151.         lru.get(1);         // 1:aa 5:e 2:bb
  152.         System.out.println(lru.toString());
  153.         lru.remove(11);     // 1:aa 5:e 2:bb
  154.         System.out.println(lru.toString());
  155.         lru.remove(1);      //5:e 2:bb
  156.         System.out.println(lru.toString());
  157.         lru.put(1, "aaa");  //1:aaa 5:e 2:bb
  158.         System.out.println(lru.toString());
  159.     }
  160. }