天天看點
傳回

Java LinkedHashMap類源碼解析

LinkedHashMap繼承了HashMap，他在HashMap的基礎上增加了一個雙向連結清單的結構，連結清單預設維持key插入的順序，重複的key值插入不會改變順序，适用于使用者需要傳回一個順序相同的map對象的情況。還可以生成access-order順序的版本，按照最近通路順序來存儲，剛被通路的結點處于連結清單的末尾，适合LRU，put get compute merge都算作一次通路，其中put key值相同的結點也算作一次通路，replace隻有在換掉一個鍵值對的時候才算一次通路，putAll産生的通路順序取決于原本map的疊代器實作。

在插入鍵值對時，可以通過對removeEldestEntry重寫來實作新鍵值對插入時自動删除最舊的鍵值對

擁有HashMap提供的方法，疊代器因為是通過周遊雙向連結清單，是以額外開銷與size成正比與capacity無關，是以選擇過大的初始大小對于周遊時間的增加沒有HashMap嚴重，後者的周遊時間依賴與capacity。

同樣是非線程安全方法，對于LinkedHashMap來說，修改結構的操作除了增加和删除鍵值對外，還有對于access-order時進行了access導緻疊代器順序改變，主要是get操作，對于插入順序的來說，僅僅修改一個已有key值的value值不是一個修改結構的操作，但對于通路順序，put和get已有的key值會改變順序。疊代器也是fail-fast設計，但是fail-fast隻是一個調試功能，一個設計良好的程式不應該出現這個錯誤

因為HashMap加入了TreeNode，是以現在LinkedHashMap也有這個功能

 以下描述中的連結清單，若無特别說明都是指LinkedHashMap的雙向連結清單

先來看一下基本結構，每個鍵值對加入了前後指針，集合加入了頭尾指針來形成雙向連結清單，accessOrder代表連結清單是以通路順序還是插入順序存儲

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

    /**
     * The head (eldest) of the doubly linked list.頭部
     */
    transient LinkedHashMap.Entry<K,V> head;

    /**
     * The tail (youngest) of the doubly linked list.尾部
     */
    transient LinkedHashMap.Entry<K,V> tail;

    //true通路順序 false插入順序
    final boolean accessOrder;

然後是幾個内部方法。linkNodeLast将p連接配接到連結清單尾部

private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
        LinkedHashMap.Entry<K,V> last = tail;
        tail = p;
        if (last == null)
            head = p;//原本連結清單為空則p同時為頭部
        else {
            p.before = last;
            last.after = p;
        }
    }

transferLinks用dst替換src

private void transferLinks(LinkedHashMap.Entry<K,V> src,
                               LinkedHashMap.Entry<K,V> dst) {
        LinkedHashMap.Entry<K,V> b = dst.before = src.before;
        LinkedHashMap.Entry<K,V> a = dst.after = src.after;
        if (b == null)
            head = dst;
        else
            b.after = dst;
        if (a == null)
            tail = dst;
        else
            a.before = dst;
    }

reinitialize在調用HashMap方法的基礎上，将head和tail設為null

void reinitialize() {
        super.reinitialize();
        head = tail = null;
    }

newNode生成一個LinkedHashMap結點，next指向e，插入到LinkedHashMap連結清單末端

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);//建立一個鍵值對，next指向e
        linkNodeLast(p);//p插入到LinkedHashMap連結清單末端
        return p;
    }

replacementNode根據原結點生成一個LinkedHashMap結點替換原結點

Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
        LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
        LinkedHashMap.Entry<K,V> t =
            new LinkedHashMap.Entry<K,V>(q.hash, q.key, q.value, next);//生成一個新的鍵值對next是給出的next參數
        transferLinks(q, t);//用t替換q
        return t;
    }

newTreeNode生成一個TreeNode結點，next指向next，插入到LinkedHashMap連結清單末端

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);//生成一個TreeNode，next指向參數next
        linkNodeLast(p);//p插入到LinkedHashMap連結清單末端
        return p;
    }

replacementTreeNode根據結點p生成一個新的TreeNode，next設為給定的next，替換原本的p

TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
        LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
        TreeNode<K,V> t = new TreeNode<K,V>(q.hash, q.key, q.value, next);
        transferLinks(q, t);//根據結點p生成一個新的TreeNode，next設為給定的next，替換原本的p
        return t;
    }

afterNodeRemoval從LinkedHashMap的鍊上移除結點e

void afterNodeRemoval(Node<K,V> e) { 
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        p.before = p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a == null)
            tail = b;
        else
            a.before = b;
    }

afterNodeInsertion可能移除最舊的結點，需要evict為true同時連結清單不為空同時removeEldestEntry需要重寫

void afterNodeInsertion(boolean evict) { 
        LinkedHashMap.Entry<K,V> first;
        if (evict && (first = head) != null && removeEldestEntry(first)) {//removeEldestEntry需要重寫才從發揮作用，否則一定傳回false
            K key = first.key;//移除連結清單頭部的結點
            removeNode(hash(key), key, null, false, true);
        }
    }

afterNodeAccess在通路過後将結點e移動到連結清單尾部，需要Map是access-order，若移動成功則增加modCount

void afterNodeAccess(Node<K,V> e) { 
        LinkedHashMap.Entry<K,V> last;
        if (accessOrder && (last = tail) != e) {//Map是access-order同時e不是連結清單的尾部
            LinkedHashMap.Entry<K,V> p =
                (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
            p.after = null;
            if (b == null)//将結點e從連結清單中剪下
                head = a;
            else
                b.after = a;
            if (a != null)
                a.before = b;
            else
                last = b;
            if (last == null)
                head = p;
            else {
                p.before = last;
                last.after = p;
            }
            tail = p;//結點e移動到連結清單尾部
            ++modCount;//因為有access-order下結點被移動，是以增加modCount
        }
    }

構造函數方面，accessOrder預設是false插入順序，初始大小為16，負載因子為0.75，這裡是同HashMap。複制構造也是調用了HashMap.putMapEntries方法

containsValue周遊連結清單尋找相等的value值，這個操作一定不會造成結構改變

public boolean containsValue(Object value) {
        for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {//檢查同樣是根據LinkedHashMap提供的連結清單順序進行周遊
            V v = e.value;
            if (v == value || (value != null && value.equals(v)))
                return true;
        }
        return false;
    }

get方法複用HashMap的getNode方法，若找到結點且Map是通路順序時，要将通路的結點放到連結清單最後，若沒找到則傳回null。而getOrDefault僅有的差別是沒找到時傳回defaultValue

public V get(Object key) {
        Node<K,V> e;
        if ((e = getNode(hash(key), key)) == null)//複用HashMap的getNode方法
            return null;
        if (accessOrder)
            afterNodeAccess(e);//access-order時将e放到隊尾
        return e.value;
    }

    public V getOrDefault(Object key, V defaultValue) {
       Node<K,V> e;
       if ((e = getNode(hash(key), key)) == null)
           return defaultValue;//複用HashMap的getNode方法，若沒有找到對應的結點則傳回defaultValue
       if (accessOrder)
           afterNodeAccess(e);//access-order時将e放到隊尾
       return e.value;
   }

clear方法在HashMap的基礎上要把head和tail設為null

public void clear() {
        super.clear();
        head = tail = null;
    }

removeEldestEntry在put和putAll插入鍵值對時調用，原本是一定傳回false的，如果要自動删除最舊的鍵值對要傳回true，需要進行重寫。比如下面這個例子，控制size不能超過100

private static final int MAX_ENTRIES = 100;

     protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > MAX_ENTRIES;
     }

下面兩個方法和HashMap相似，傳回key的Set和value的Collection還有傳回鍵值對的Set，這個是直接引用，是以對它們的remove之類的修改會直接回報到LinkedHashMap上

public Set<K> keySet() {
        Set<K> ks = keySet;
        if (ks == null) {
            ks = new LinkedKeySet();
            keySet = ks;
        }
        return ks;//傳回key值的set
    }

    public Collection<V> values() {
        Collection<V> vs = values;
        if (vs == null) {
            vs = new LinkedValues();
            values = vs;
        }
        return vs;//傳回一個包含所有value值的Collection
    }

    public Set<Map.Entry<K,V>> entrySet() {
        Set<Map.Entry<K,V>> es;
        return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es;//傳回一個含有所有鍵值對的Set
    }

檢查HashMap的putVal方法，我們可以看到在找到了相同key值并修改value值時會調用afterNodeAccess，對于access-order會改變結點順序

if (e != null) { // 找到了相同的key則修改value值并傳回舊的value
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
java c++ 存儲 安全 安全存儲java java編碼安全存儲 linkedhashmap源碼解析 java char存儲 hashmap java源碼分析
上一篇: 混合雲存儲跨雲災備方案之跨雲複制
下一篇: java 并發程式設計中的ConcurrentModificationException 異常問題

繼續閱讀