算法：LRU

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

目录

一、LRU简介

二、设计要素

三、引入LinkedHashMap

四、代码示例

总结

---

提示：以下是本篇文章正文内容，下面案例可供参考

一、LRU简介

LRU：最近最少使用，最大容量固定，当超过最大容量时，将符合条件的元素移除。

举个例子：

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); ? ? ? // 返回 ?1
cache.put(3, 3); ? ?// 该操作会使得密钥 2 作废
cache.get(2); ? ? ? // 返回 -1 (未找到)
cache.put(4, 4); ? ?// 该操作会使得密钥 1 作废
cache.get(1); ? ? ? // 返回 -1 (未找到)
cache.get(3); ? ? ? // 返回 ?3
cache.get(4); ? ? ? // 返回 ?4

以上例子，当写入两个元素时，容量饱和，当写入第三个元素时，就会移除一个元素，然后将第三个元素写进来。

二、设计要素

首先，查找必须得快速

其次，存储数据得快

最后，要对数据进行排序，这样能取出我们最不常用的数据，然后进行移除

三、引入LinkedHashMap

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> {

    ......

}

可以看到LinkedHashMap是HashMap的子类，我们知道HashMap对数据的存储和查询都是非常快的。?

但是单单HashMap满足不了我们的需要。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

这是HashMap的写入方法，该方法预留了一个扩展afterNodeInsertion(evict);用于子类实现，下面我们来看一下LinkedHashMap是怎么实现这个扩展方法的

void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

evict：布尔类型，表示是否需要驱逐最老的节点。如果为true，那么在插入新节点后，会检查是否需要移除最老的节点

方法内部首先声明了一个类型为LinkedHashMap.Entry的变量first。然后，如果evict为true，并且链表的头部节点不为空，那么就调用removeEldestEntry(first)方法来检查是否需要移除最老的节点

如果需要移除最老的节点，那么就获取这个节点的键值，然后调用removeNode(hash(key), key, null, false, true)方法来移除这个节点

至此，顺序的问题也解决了。

四、代码示例

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCache<K, V> extends LinkedHashMap<K, V> {

    // 容量属性
    private int capacity;

    public LRUCache(int capacity) {
        super(capacity + 1, 1.0f, true); // capacity + 1, access order
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }

    // 测试方法
    public static void main(String[] args) {
        LRUCache<Integer, String> cache = new LRUCache<>(3);
        cache.put(1, "one");
        cache.put(2, "two");
        cache.put(3, "three");
        cache.get(1); // 将1移动到链表尾部
        cache.put(4, "four"); // 移除链表头部的2，因为容量为3
        System.out.println(cache); // 输出：{3=three, 1=one, 4=four}
    }
}

---

总结

强大的扩展机制，膜拜，多练练，简单到有手就行！