LRU(Least recently used)最近最少运用，它的中心思想是“假设数据最近被拜访过，那么未来被拜访的几率也更高”。因此 LRU 算法会依据数据的历史拜访记载来停止排序，假设空间不足，就会淘汰掉最近最少运用的数据。

2 LRU 完成原理

由于 LRU 算法会将最近运用的数据优先级上升，因此需求数据结构支持排序，链表十分适宜。

为什么不思索数组呢?

由于 LRU 算法，普通都会运用在拜访比较频繁的场景，因此，对数据的移动会频繁，而数组一旦移动，需求将移动到值的位置前面的一切数据的位置全部改动，效率比较低，不引荐运用。

3 双向链表之LinkedHashMap

前面我们剖析到 LRU 的算法完成，可以运用链表完成，java 中 LinkedHashMap 就是一个双向链表。

LinkedHashMap是HashMap的子类，在HashMap数据结构的基础上，还维护着一个双向链表链接一切entry，这个链表定义了迭代顺序，通常是数据插入的顺序。

我们来看看LinkedHashMap的源码：

从源码中的定义可以看到，accessOrder 属性可以指定遍历 LinkedHashMap 的顺序，true 表示按照拜访顺序，false 表示按照插入顺序，默以为 false。

由于LRU对拜访顺序敏感，因此运用true来复杂验证一下：

public class LRUTest { 

    public static void main(String[] args) { 

        LinkedHashMap<String, Object> map = new LinkedHashMap<>(16, 0.75f, true); 

        map.put("a", 1); 

        map.put("b", 2); 

        map.put("c", 3); 

        System.out.println("before get " + map); 

        map.get("a"); 

        System.out.println("after get" + map); 

    }} 

运转结果如下：

before get {a=1, b=2, c=3} 

after get{b=2, c=3, a=1} 

可以看到经过 accessOrder = true，可以让 LinkedHashMap 按照拜访顺序停止排序。

那么 LinkedHashMap 是怎样做的呢?

我们看下get办法

public V get(Object key) { 

    Node<K,V> e; 

    // 获取node 

    if ((e = getNode(hash(key), key)) == null) 

        return null; 

    // 假设 accessOrder = true，则执行afterNodeAccess办法 

    if (accessOrder) 

        afterNodeAccess(e); 

    return e.value; 

} 

再看下afterNodeAccess办法，发现停止移动节点，到此移动节点的原理我们了解了

void afterNodeAccess(Node<K,V> e) { // move node to last 

   LinkedHashMap.Entry<K,V> last; 

   if (accessOrder && (last = tail) != e) { 

       LinkedHashMap.Entry<K,V> p =            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;        p.after = null;        if (b == null) 

           head = a;        else 

(责任编辑：admin)