LinkedHashMap源碼探究

LinkedHashMap繼承于HashMap，有HashMap的所有特性，除此之外LinkedHashMap維護了一個雙重連結清單，這個連結清單定義了元素的通路順序包括：插入順序和通路順序，預設為按照插入順序

關于HashMap介紹參考以下

http://blog.csdn.net/nuannuandetaiyang/article/details/71108241

LinkedHashMap的構造函數

public LinkedHashMap() {
        init();
        accessOrder = false;//元素順序，預設為插入順序
    }
    public LinkedHashMap(int initialCapacity) {
        //調用HashMap的構造方法
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    public LinkedHashMap(int initialCapacity, float loadFactor) {
        this(initialCapacity, loadFactor, false);
    }
    public LinkedHashMap(
            int initialCapacity, float loadFactor, boolean accessOrder) {
        super(initialCapacity, loadFactor);
        init();
        this.accessOrder = accessOrder;
    }
           

LinkedHashMap數組的每一項也針對HashMapEntry做了延伸，添加了一個指向後一個元素的nxt指針和前一個元素的prv指針

static class LinkedEntry<K, V> extends HashMapEntry<K, V> {
        LinkedEntry<K, V> nxt;
        LinkedEntry<K, V> prv;

        /** Create the header entry */
        LinkedEntry() {
            super(null, null, , null);
            nxt = prv = this;
        }

        /** Create a normal entry */
        LinkedEntry(K key, V value, int hash, HashMapEntry<K, V> next,
                    LinkedEntry<K, V> nxt, LinkedEntry<K, V> prv) {
            super(key, value, hash, next);
            this.nxt = nxt;
            this.prv = prv;
        }
    }
           

LinkedHashMap的資料讀取

@Override public V get(Object key) {
        /*
         * This method is overridden to eliminate the need for a polymorphic
         * invocation in superclass at the expense of code duplication.
         */
        if (key == null) {
            HashMapEntry<K, V> e = entryForNullKey;
            if (e == null)
                return null;
            if (accessOrder)
                makeTail((LinkedEntry<K, V>) e);
            return e.value;
        }

        int hash = Collections.secondaryHash(key);
        HashMapEntry<K, V>[] tab = table;
        for (HashMapEntry<K, V> e = tab[hash & (tab.length - )];
                e != null; e = e.next) {
            K eKey = e.key;
            if (eKey == key || (e.hash == hash && key.equals(eKey))) {
            // 如果定義了LinkedHashMap的疊代順序為通路順序，則删除以前位置上的元素，并将最新通路的元素添加到連結清單表頭。
                if (accessOrder)
                    makeTail((LinkedEntry<K, V>) e);
                return e.value;
            }
        }
        return null;
    }

    /**
     * Relinks the given entry to the tail of the list. Under access ordering,
     * this method is invoked whenever the value of a  pre-existing entry is
     * read by Map.get or modified by Map.put.
     */
    private void makeTail(LinkedEntry<K, V> e) {
        // Unlink e
        //從連結清單中删除目前元素
        e.prv.nxt = e.nxt;
        e.nxt.prv = e.prv;
        //添加元素到連結清單頭
        // Relink e as tail
        //得到頭指針
        LinkedEntry<K, V> header = this.header;
        //臨時儲存header指向的prv元素
        LinkedEntry<K, V> oldTail = header.prv;
        e.nxt = header;
        e.prv = oldTail;
        oldTail.nxt = header.prv = e;
        modCount++;
    }
           

新增的節點插入過程見圖示

整體跟HashMap的資料讀取沒多大差別，主要的差別在于會根據accessOrder的狀态執行makeTail方法，