這是LRU算法的核心，比如Glide里無論是內(nèi)存緩存還是硬盤緩存，其實核心都是用到了LRU算法，而LRU算法核心是靠這個LinedHashMap來實現(xiàn)的。
先來看一下定義的一些方法，因為是繼承的HashMap，所以內(nèi)部大部分方法是和HashMap一樣，不同的是HashMap中的Node方法是只有next的單向鏈表，而在LinedHashMap中因為需要保持插入或者讀取順序，所以變成了雙向的鏈表LinkedHashMapEntry中是包含before和after。
盜用一下大佬的圖

image.png

public class LinkedHashMap<K,V> extends HashMap<K,V>
    implements Map<K,V>
{
    /**
     * HashMap.Node subclass for normal LinkedHashMap entries.
     */
    static class LinkedHashMapEntry<K,V> extends HashMap.Node<K,V> {
        LinkedHashMapEntry<K,V> before, after;
        LinkedHashMapEntry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }
    /**
     * The head (eldest) of the doubly linked list.
     */
    transient LinkedHashMapEntry<K,V> head;

    /**
     * The tail (youngest) of the doubly linked list.
     */
    transient LinkedHashMapEntry<K,V> tail;
 
·····

put方法是直接繼承的hashmap的，沒有重新（通過newNode實現(xiàn)的雙鏈表操作），我們主要看一下get這個方法，是如何實現(xiàn)get之后改變位置的。首先根據(jù)key，把當(dāng)前節(jié)點搞出來 getNode(hash(key)，然后判斷一下是不是accessOrder=true，如果true，則會把訪問過的元素放在鏈表后面，放置順序是訪問的順序 ，如果false，按出入順序遍歷

  public V get(Object key) {
        Node<K,V> e;
        if ((e = getNode(hash(key), key)) == null)
            return null;
        if (accessOrder)
            afterNodeAccess(e);
        return e.value;
    }

再看下核心的afterNodeAccess方法，這是節(jié)點變化的核心方法，盡量注釋的詳細到每一行。

  void afterNodeAccess(Node<K,V> e) { // move node to last
        LinkedHashMapEntry<K,V> last;
        if (accessOrder && (last = tail) != e) {
            LinkedHashMapEntry<K,V> p =(LinkedHashMapEntry<K,V>)e //拿到當(dāng)前的節(jié)點
             , b = p.before // 拿到當(dāng)前節(jié)點的前一個節(jié)點
             , a = p.after; //拿到當(dāng)前節(jié)點的后一個節(jié)點
            p.after = null; //因為當(dāng)前節(jié)點要當(dāng)做最后一個節(jié)點，所以當(dāng)前節(jié)點后邊不需任何節(jié)點了，置空
            if (b == null) //如果當(dāng)前節(jié)點前邊一個節(jié)點是空的，在代表當(dāng)前節(jié)點是頭節(jié)點
                head = a; //這就好說了，頭結(jié)點變成后邊一個節(jié)點了
            else
                b.after = a;//如果不是，那就把前邊節(jié)點的后連接和后邊節(jié)點連起來
            if (a != null) //如果后一個節(jié)點不是空的
                a.before = b;//那把后邊一個節(jié)點的前連接和上一個節(jié)點連起來
            else
                last = b; //如果后邊節(jié)點是空的，那當(dāng)前就是最后一個節(jié)點
            if (last == null) // 如果當(dāng)前l(fā)ast是空的，沒有數(shù)據(jù)？
                head = p;//那直接把頭節(jié)點變成前節(jié)點
            else {
                p.before = last; //如果前邊都沒有 是正常的鏈表 ，把當(dāng)前的頭節(jié)點和最后個連接起來
                last.after = p;//把最后一個的后節(jié)點和當(dāng)前的節(jié)點連接起來
            }
            tail = p; //當(dāng)前節(jié)點賦值給全局變量的最后節(jié)點
            ++modCount; //整體節(jié)點累加
        }
    }

image.png

感謝 coolblog大佬 。