如何實現一個LRU算法？

LRU就是Least recently used,最近最少使用，如果空間不足淘汰掉最近最少使用的數據。
實現方式可以有一下三種：

1、單鏈表

實現原理：
1、插入：插入數據是最新的數據，直接插入到鏈表尾部
2、查找：查找到的數據移動到鏈表尾部，代表最新訪問。
3、刪除：鏈表頭代表最近最少使用，如果鏈表滿，則刪除鏈表頭數據

時間復雜度：O(n)

2、哈希表+雙向鏈表

1、先后插入5個節點，每個節點在2個鏈表中。
2、黑色鏈表，代表哈希沖突之后的鏈表。
3、紅色鏈表，代表節點之間的順序。
4、每個節點，由4部分組成，分別是數據，黑色鏈表的next指針，紅色鏈表的pre指針和next指針。

查找：通過哈希表查找到，然后移動到雙向鏈表的尾部。
刪除：通過哈希表查找到，通過雙向鏈表拿到前驅節點，直接刪除即可。
插入：先看是否存在，如果存在移動到鏈表尾部，如果不存在，鏈表滿的話刪除頭節點，然后插入鏈表尾部，否則不滿，則直接插入鏈表尾部。

3、LinkedHashMap

LinkedHashMap繼承自HashMap，擁有HashMap的所有特性，同時LinkedHashMap增加了head和tail指針，用于實現雙向鏈表。

1、LinkedHashMap默認的支持按照插入順序保存數據，新的數據插入雙向鏈表尾部。


2、構造方法支持按照訪問順序，最新訪問的數據放到雙向鏈表尾部。

4、如何實現LRU算法呢，自動刪除掉鏈表頭的過期數據？

LinkedHashMap默認是不會自動刪除鏈表頭節點數據的，我們需要覆蓋類的一個方法：removeEldestEntry

1、實現一個類LruLinkedMap繼承LinkedHashMap

package com.jane;

import java.util.LinkedHashMap;

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

    private int size;

    public LruLinkedMap(int initialCapacity,
               float loadFactor,
               boolean accessOrder) {
        super(initialCapacity, loadFactor, accessOrder);
        this.size = initialCapacity;
    }

    /**
     * @description 重寫LinkedHashMap中的removeEldestEntry方法，當LRU中元素多余6個時，
     *              刪除最不經常使用的元素
     */
    @Override
    protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) {
        if(size() > size){
            return true;
        }
        return false;
    }

}

2、啟動文件：

package com.jane;

import java.util.Map;

public class Main {

    public static void main(String[] args) {
        LruLinkedMap<String, String> ss = new LruLinkedMap(5, 0.75f, true);

        ss.put("1", "3");
        ss.put("2", "4");
        ss.put("3", "6");
        ss.put("4", "1");
        ss.put("5", "5");

        for(Map.Entry e: ss.entrySet()) {
            System.out.println(e.getKey());
        }
        System.out.println("---------------");

        ss.get("1");

        for(Map.Entry e: ss.entrySet()) {
            System.out.println(e.getKey());
        }
        System.out.println("---------------");
        ss.put("7", "10");

        for(Map.Entry e: ss.entrySet()) {
            System.out.println(e.getKey());
        }
    }
}

3、結果：

這樣LRU就輕松的實現了。