概念

LinkedHashMap也是Java集合框架的一員，是HashMap的子類。LinkedHashMap可以保存插入順序，底層是通過HashMap的哈希表和雙向鏈表保存數(shù)據(jù)。

類結(jié)構(gòu)

LinkedHashMap繼承于HashMap，實現(xiàn)了Map接口。重寫了部分HashMap類中的方法。

類成員

Entry 類

    static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }

Entry是LinkedHashMap靜態(tài)內(nèi)部類，繼承了HashMap.Node<K,V>類，在Node類的基礎上增加了before、 after節(jié)點用來構(gòu)成雙向循環(huán)鏈表。

head & tail

    // 頭結(jié)點
    transient LinkedHashMap.Entry<K,V> head;
    // 尾節(jié)點
    transient LinkedHashMap.Entry<K,V> tail;

head和tail節(jié)點分別記錄分別記錄著雙向循環(huán)鏈表頭結(jié)點和尾節(jié)點。

accessOrder

    final boolean accessOrder;

accessOrder 用來區(qū)分對LinkedHashMap中元素順序。accessOrder為false時（默認為false），按照插入順序，accessOrder為true時，按照訪問順序。

構(gòu)造函數(shù)

LinkedHashMap提供了5種構(gòu)造函數(shù)。

    public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false;
    }

      public LinkedHashMap(int initialCapacity) {
        super(initialCapacity);
        accessOrder = false;
    }

    public LinkedHashMap() {
        super();
        accessOrder = false;
    }

    public LinkedHashMap(Map<? extends K, ? extends V> m) {
        super();
        accessOrder = false;
        putMapEntries(m, false);
    }
    
    public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }

實際上LinkedHashMap的構(gòu)造函數(shù)時調(diào)用父類HashMap的構(gòu)造函數(shù)實現(xiàn)的。前四種accessOrder均為false，也就是表明默認按照插入順序。第五種構(gòu)造函數(shù)可以指定accessOrder的值。

get(Object key) 方法

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

get方法重寫了HashMap中get方法。不同的時候，在查找出元素后，如果當前是按照元素訪問順序的模式，這里會通過調(diào)用afterNodeAccess方法把元素添加至鏈表的尾部。因為按照元素訪問的模式中，會按照訪問效率排序，最少訪問的靠前，最新訪問的靠后。

put(K key, V value) 方法

LinkedHashMap的put方法并沒有重寫父類HashMap的put方法。而是重寫了其中的newNode、newTreeNode、afterNodeAccess和afterNodeInsertion方法。

linkNodeLast 方法

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

    
        TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
        TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);
        linkNodeLast(p);
        return p;
    }

LinkedHashMap重寫了newTreeNode和newTreeNode方法。這兩個方法在創(chuàng)建新節(jié)點的時候，都調(diào)用了linkNodeLast方法。

    private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
        LinkedHashMap.Entry<K,V> last = tail;
        tail = p;
        if (last == null)
            // 尾節(jié)點為空，p設置為head節(jié)點
            head = p;
        else {
            // 將節(jié)點添加至鏈表尾部
            p.before = last;
            last.after = p;
        }
    }

linkNodeLast方法中將給定的節(jié)點，將節(jié)點添加到雙向鏈表的尾部。

afterNodeAccess 方法

LinkedHashMap重寫了afterNodeAccess方法，在put方法中，當遇到了put的key相同的時候，更新節(jié)點的同時，調(diào)用afterNodeAccess方法，如果accessOrder為true的時候，將會把節(jié)點添加至鏈表尾部。

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

removeEldestEntry方法在LinkedHashMap直接return false。如果有需要，我們可以選擇重寫removeEldestEntry方法，來定義老節(jié)點first在put新數(shù)據(jù)時的刪除機制。

總結(jié)

LinkedHashMap通過重新HashMap部分方法來實現(xiàn)其可以按插入順序或者訪問順序的特性。由于LinkedHashMap按照訪問順序的特性，可以用來實現(xiàn)LRU算法。

LinkedHashMap是非線程安全的，只適用于單線程，多線程環(huán)境慎用。