LinkedHashMap分析(基于jdk1.8)

HashMap有一個問題就是迭代的順序無法保證,也就是和put進去的順序不同,有時候可能需要保證迭代的時候與put進去的順序一致,這個時候就可以使用LinkedHashMap了

首先要搞清楚為什么HashMap無法保證迭代的順序和put的順序為什么無法相同,
首先放入map的桶,也就是數(shù)組的順序是和put的順序沒有聯(lián)系的,恰恰迭代的時候是根據(jù)數(shù)組里的順序來的,代碼如下:

final Node<K,V> nextNode() {
            Node<K,V>[] t;
            Node<K,V> e = next;
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (e == null)
                throw new NoSuchElementException();
                //把hashmap的table引用給t數(shù)組
            if ((next = (current = e).next) == null && (t = table) != null) {
                //do while循環(huán),直到數(shù)組中的某個對象不為null時返回null
                do {} while (index < t.length && (next = t[index++]) == null);
            }
            return e;
        }

所以為了解決這個問題,LinkedHashMap的靜態(tài)內(nèi)部類Entry繼承了HashMap的Node并且增加了before和after的成員變量

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

然后問題來了,增加的這些節(jié)點是怎么在put的時候弄上去的呢,看看重寫的方法吧
我本來以為是重寫了putVal()方法呢,然而我還是naive,其實是重寫了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);
        //這個方法將put的方法形成一個鏈表
        linkNodeLast(p);
        return p;
    }
    
    /**
    *私有方法
    *
    **/    
    private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
        LinkedHashMap.Entry<K,V> last = tail;
        tail = p;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }

好,再來看看LinkedHashMap的迭代方法,直接看nextNode就行啦:

 final LinkedHashMap.Entry<K,V> nextNode() {
            LinkedHashMap.Entry<K,V> e = next;
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (e == null)
                throw new NoSuchElementException();
                //終于不用通過桶去循環(huán)找下一個不為null的數(shù)組對象啦
            current = e;
            next = e.after;
            return e;
        }