LinkedHashMap代碼詳解(一)

HashMap 在周遊map時，資料是無序的，在某些需要按照put順序周遊時，就用到了LinkedHashMap，LinkedHashMap是HashMap的子類，并且用一條雙向連結清單來存儲資料插入的順序

transient LinkedHashMap.Entry<K,V> head; //連結清單的頭節點
transient LinkedHashMap.Entry<K,V> tail; //連結清單的尾節點
final boolean accessOrder;               //是否開啟lru算法(最活躍的點放在連結清單頭部)           

put():

由于LinkedHashMap沒有put方法，put操作用的還是HashMap的方法，但是重寫了newNode(int hash, K key, V value, Node e) ，afterNodeAccess(Node e),afterNodeInsertion(boolean evict)方法

1 table中不存在相同的key

if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);           

LinkedhashMap重寫了newNode方法，将新增的節點加傳入連結表尾部，上代碼

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
        LinkedHashMap.Entry<K,V> p =
            new LinkedHashMap.Entry<K,V>(hash, key, value, e);
        linkNodeLast(p);
        return p;
    }
    private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
        LinkedHashMap.Entry<K,V> last = tail;
        tail = p;//尾節點指向新節點
        if (last == null)//如果原尾節點為空，證明連結清單還沒有資料，頭節點指向新節點p
            head = p; 
        else {        //連結清單不為空
            p.before = last; 
            last.after = p;//原尾節點建立雙向連結
        }
    }           

2 table數組中存在相同的key

if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }           

發生了節點資料操作(value替換)，如果開啟了LRU(accessOrder=true)，則将修改的節點放傳入連結表尾部，HashMap.afterNodeAccess() 為空函數

LinkedHashMap overwirte了該方法

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;
              
            /**重寫上面的指派操作
            LinkedHashMap.Entry<K,V> p =(LinkedHashMap.Entry<K,V>)e；
            LinkedHashMap.Entry<K,V> b(befor) = p.before；
            LinkedHashMap.Entry<K,V> a(after) = p.after;           
            **/
            p.after = null; //将修改的節點after置為null
            if (b == null)  //如果b==null  證明e是頭結點
                head = a;  //将連結清單頭結點指向 e.next
            else            //e不是頭結點
                b.after = a;  // e.befor.after = e.after
                             // e節點的上一個節點的next指向e的下一個節點,移除e
            if (a != null)   //如果e的下一個節點不為空
                a.before = b;//e.after.befor= e.after
                             // e節點的下一個節點的befor指向e的上一個節點，雙向連結清單的反向箭頭
            else             // a == null e是尾部節點
                last = b;    //last指向e的上一個節點
            if (last == null) //如果 last== null 證明 隻有一個節點
                head = p;      //頭部尾部都指向該節點
            else {              // p不是頭節點
                p.before = last; //将p放在連結清單尾部 
                last.after = p;
            }
            tail = p;
            ++modCount;        //map操作數+1，(重新指派且開啟LRU，modCount會兩次+1)
        }
    }           

3 在執行完put操作後，調用afterNodeInsertion方法

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);
        }
    }
   protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return false;
    }           

evict 在hashMap中預設為true，LinkedHashMap.removeEldestEntry ()預設傳回false，

該方法的yongfasj用法是 配合LRU算法，自定義Class繼承LinkedHashMap方法并重寫removeEldestEntry 方法，

在特定條件下傳回true，移除連結清單中最左側的節點

可以使用該特性進行緩存建立，保留最近活躍的資料，開啟LRU需要将開頭提到的accessOrder 置為true

該參數隻能在LinkedHashMap new時指定，需要同時指定擴充因子loadFactor 預設為0.75f

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

get():

LinkedHashMap get方法，可以看到 和hashMap是一緻的，隻是加了accessOrder 判斷，開啟LRU後，将擷取的資料放在連結清單的最右側，提高該節點的活躍程度

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;
    }