Java LinkedHashMap 底層實(shí)現原理分析

目錄

在實(shí)現上，LinkedHashMap很多方法直接繼承自HashMap，僅為維護雙向鏈表覆寫(xiě)了部分方法。所以，要看懂 LinkedHashMap 的源碼，需要先看懂 HashMap 的源碼。

默認情況下，LinkedHashMap的迭代順序是按照插入節點(diǎn)的順序。也可以通過(guò)改變accessOrder參數的值，使得其遍歷順序按照訪(fǎng)問(wèn)順序輸出。

這里我們只討論LinkedHashMap和HashMap的不同之處，LinkedHashMap的其他操作和特性具體請參考HashMap

我們先來(lái)看下兩者的區別：

import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
public class Test04 {
    public static void main(String[] args) {
        Map<String, String> map = new LinkedHashMap<String, String>();
        map.put("ahdjkf", "1");
        map.put("ifjdj", "2");
        map.put("giafdja", "3");
        map.put("agad", "4");
        map.put("ahdjkge", "5");
        map.put("iegnj", "6");
        System.out.println("LinkedHashMap的迭代順序(accessOrder=false)：");
        Iterator iterator = map.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry entry = (Map.Entry) iterator.next();
            System.out.println(entry.getKey() + "=" + entry.getValue());
        }

        Map<String, String> map1 = new LinkedHashMap<String, String>(16,0.75f,true);
        map1.put("ahdjkf", "1");
        map1.put("ifjdj", "2");
        map1.put("giafdja", "3");
        map1.put("agad", "4");
        map1.put("ahdjkge", "5");
        map1.put("iegnj", "6");

        map1.get("ahdjkf");
        map1.get("ifjdj");
        System.out.println("LinkedHashMap的迭代順序(accessOrder=true)：");
        Iterator iterator1 = map1.entrySet().iterator();
        while (iterator1.hasNext()) {
            Map.Entry entry = (Map.Entry) iterator1.next();
            System.out.println(entry.getKey() + "=" + entry.getValue());
        }

        Map<String, String> map2 = new HashMap<>();
        map2.put("ahdjkf", "1");
        map2.put("ifjdj", "2");
        map2.put("giafdja", "3");
        map2.put("agad", "4");
        map2.put("ahdjkge", "5");
        map2.put("iegnj", "6");

        System.out.println("HashMap的迭代順序：");    
        Iterator iterator2 = map2.entrySet().iterator();
        while (iterator2.hasNext()) {
            Map.Entry aMap = (Map.Entry) iterator2.next();
            System.out.println(aMap.getKey() + "=" + aMap.getValue());
        }
    }
}
Output：
LinkedHashMap的迭代順序(accessOrder=false)：
ahdjkf=1
ifjdj=2
giafdja=3
agad=4
ahdjkge=5
iegnj=6
LinkedHashMap的迭代順序(accessOrder=true)：
giafdja=3
agad=4
ahdjkge=5
iegnj=6
ahdjkf=1
ifjdj=2
HashMap的迭代順序：
iegnj=6
giafdja=3
ifjdj=2
agad=4
ahdjkf=1
ahdjkge=5

可以看到 LinkedHashMap在每次插入數據，訪(fǎng)問(wèn)、修改數據時(shí)都會(huì )調整鏈表的節點(diǎn)順序。以決定迭代時(shí)輸出的順序。

下面我們來(lái)看LinkedHashMap具體是怎么實(shí)現的：

LinkedHashMap繼承了HashMap，內部靜態(tài)類(lèi)Entry繼承了HashMap的Entry，但是LinkedHashMap.Entry多了兩個(gè)字段：before和after，before表示在本節點(diǎn)之前添加到LinkedHashMap的那個(gè)節點(diǎn)，after表示在本節點(diǎn)之后添加到LinkedHashMap的那個(gè)節點(diǎn)，這里的之前和之后指時(shí)間上的先后順序。

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

同時(shí)類(lèi)里有兩個(gè)成員變量head和tail,分別指向內部雙向鏈表的表頭、表尾。

//雙向鏈表的頭結點(diǎn)
transient LinkedHashMap.Entry<K,V> head;
//雙向鏈表的尾節點(diǎn)
transient LinkedHashMap.Entry<K,V> tail;

將LinkedHashMap的accessOrder字段設置為true后，每次訪(fǎng)問(wèn)哈希表中的節點(diǎn)都將該節點(diǎn)移到鏈表的末尾，表示該節點(diǎn)是最新訪(fǎng)問(wèn)的節點(diǎn)。即循環(huán)雙向鏈表的頭部存放的是最久訪(fǎng)問(wèn)的節點(diǎn)或最先插入的節點(diǎn)，尾部為最近訪(fǎng)問(wèn)的或最近插入的節點(diǎn)。

由于增加了一個(gè)accessOrder屬性，LinkedHashMap相對HashMap來(lái)說(shuō)增加了一個(gè)構造方法用來(lái)控制迭代順序。

final boolean accessOrder;
public LinkedHashMap() {
    super();
    accessOrder = false;
}
//指定初始化時(shí)的容量，
public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}
//指定初始化時(shí)的容量，和擴容的加載因子
public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}
//指定初始化時(shí)的容量，和擴容的加載因子，以及迭代輸出節點(diǎn)的順序
public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}
//利用另一個(gè)Map 來(lái)構建
public LinkedHashMap(Map<? extends K, ? extends V> m) {
    super();
    accessOrder = false;
    //該方法上文分析過(guò)，批量插入一個(gè)map中的所有數據到 本集合中。
    putMapEntries(m, false);
}

添加元素

LinkedHashMap在添加元素的時(shí)候，依舊使用的是HashMap中的put方法。不同的是LinkedHashMap重寫(xiě)了newNode()方法在每次構建新節點(diǎn)時(shí)，通過(guò)linkNodeLast(p);將新節點(diǎn)鏈接在內部雙向鏈表的尾部。

//將新增的節點(diǎn)，連接在鏈表的尾部
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    //如果集合之前是空的
    if (last == null)
        head = p;
    else {//將新節點(diǎn)連接在鏈表的尾部
        p.before = last;
        last.after = p;
    }
}

刪除元素

LinkedHashMap并沒(méi)有重寫(xiě)HashMap的remove()方法，但是他重寫(xiě)了afterNodeRemoval()方法，這個(gè)方法的作用是在刪除一個(gè)節點(diǎn)時(shí)，同步將該節點(diǎn)從雙向鏈表中刪除。該方法將會(huì )在remove中被回調。

//在刪除節點(diǎn)e時(shí)，同步將e從雙向鏈表上刪除
void afterNodeRemoval(Node<K,V> e) { // unlink
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    //將待刪除節點(diǎn) p 的前置后置節點(diǎn)都置空
    p.before = p.after = null;
    //如果前置節點(diǎn)是null，則說(shuō)明現在的頭結點(diǎn)應該是后置節點(diǎn)a
    if (b == null)
        head = a;
    else//否則將前置節點(diǎn)b的后置節點(diǎn)指向a
        b.after = a;
    //同理如果后置節點(diǎn)時(shí)null ，則尾節點(diǎn)應是b
    if (a == null)
        tail = b;
    else//否則更新后置節點(diǎn)a的前置節點(diǎn)為b
        a.before = b;
}

刪除過(guò)程總的來(lái)說(shuō)可以分為三步：

1. 根據 hash 定位到桶位置
2. 遍歷鏈表或調用紅黑樹(shù)相關(guān)的刪除方法
3. 回調afterNodeRemoval，從 LinkedHashMap 維護的雙鏈表中移除要刪除的節點(diǎn)
   

更新元素

// 清除節點(diǎn)時(shí)要將頭尾節點(diǎn)一起清除 
public void clear() {
    super.clear();
    head = tail = null;
}

查找元素

LinkedHashMap重寫(xiě)了get()和getOrDefault()方法
默認情況下，LinkedHashMap是按插入順序維護鏈表。不過(guò)如果我們在初始化 LinkedHashMap時(shí)，指定 accessOrder參數為 true，即可讓它按訪(fǎng)問(wèn)順序維護鏈表。訪(fǎng)問(wèn)順序的原理是，當我們調用get/getOrDefault/replace等方法時(shí)，會(huì )將這些方法訪(fǎng)問(wèn)的節點(diǎn)移動(dòng)到鏈表的尾部。

public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder)  // 回調afterNodeAccess(Node<K,V> e)
        afterNodeAccess(e);  // 將節點(diǎn)e移至雙向鏈表的尾部（保證迭代順序）
    return e.value;
}
public V getOrDefault(Object key, V defaultValue) {
   Node<K,V> e;
   if ((e = getNode(hash(key), key)) == null)
       return defaultValue;
   if (accessOrder)
       afterNodeAccess(e);    // 作用同上
   return e.value;
}
void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;//原尾節點(diǎn)
    //如果accessOrder 是true ，且原尾節點(diǎn)不等于e
    if (accessOrder && (last = tail) != e) {
        //節點(diǎn)e強轉成雙向鏈表節點(diǎn)p
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        //p現在是尾節點(diǎn)， 后置節點(diǎn)一定是null
        p.after = null;
        //如果p的前置節點(diǎn)是null，則p以前是頭結點(diǎn)，所以更新現在的頭結點(diǎn)是p的后置節點(diǎn)a
        if (b == null)
            head = a;
        else//否則更新p的前直接點(diǎn)b的后置節點(diǎn)為 a
            b.after = a;
        //如果p的后置節點(diǎn)不是null，則更新后置節點(diǎn)a的前置節點(diǎn)為b
        if (a != null)
            a.before = b;
        else//如果原本p的后置節點(diǎn)是null，則p就是尾節點(diǎn)。 此時(shí) 更新last的引用為 p的前置節點(diǎn)b
            last = b;
        if (last == null) //原本尾節點(diǎn)是null  則，鏈表中就一個(gè)節點(diǎn)
            head = p;
        else {//否則 更新 當前節點(diǎn)p的前置節點(diǎn)為 原尾節點(diǎn)last， last的后置節點(diǎn)是p
            p.before = last;
            last.after = p;
        }
        //尾節點(diǎn)的引用賦值成p
        tail = p;
        //修改modCount。
        ++modCount;
    }
}
// 因為L(cháng)inkedHashMap中維護了一個(gè)雙向鏈表所以相對于HashMap中的雙重循環(huán)遍歷這個(gè)方法要優(yōu)化很多
LinkedHashMap
public boolean containsValue(Object value) {     
    for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {   // 通過(guò)雙向鏈表來(lái)遍歷
        V v = e.value;
        if (v == value || (value != null && value.equals(v)))
            return true;
    }
    return false;
}
HashMap
public boolean containsValue(Object value) {
    Node<K,V>[] tab; V v;
    if ((tab = table) != null && size > 0) {
        for (int i = 0; i < tab.length; ++i) {
            for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                if ((v = e.value) == value ||
                    (value != null && value.equals(v)))
                    return true;
            }
        }
    }
    return false;
}

其他方法

LinkedHashMap還有一個(gè)比較神奇的存在。

void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    // 根據條件判斷是否移除最近最少被訪(fǎng)問(wèn)的節點(diǎn)
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}
// 移除最近最少被訪(fǎng)問(wèn)條件之一，通過(guò)覆蓋此方法可實(shí)現不同策略的緩存
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

上面的方法一般不會(huì )被執行，但是當我們基于 LinkedHashMap 實(shí)現緩存時(shí)，通過(guò)覆寫(xiě)removeEldestEntry方法可以實(shí)現自定義策略的 LRU 緩存。比如我們可以根據節點(diǎn)數量判斷是否移除最近最少被訪(fǎng)問(wèn)的節點(diǎn)，或者根據節點(diǎn)的存活時(shí)間判斷是否移除該節點(diǎn)等。

迭代器

public Set<Map.Entry<K,V>> entrySet() {
        Set<Map.Entry<K,V>> es;
        //返回LinkedEntrySet
        return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es;
    }
    final class LinkedEntrySet extends AbstractSet<Map.Entry<K,V>> {
        public final Iterator<Map.Entry<K,V>> iterator() {
            return new LinkedEntryIterator();
        }
    }
final class LinkedEntryIterator extends LinkedHashIterator
        implements Iterator<Map.Entry<K,V>> {
        public final Map.Entry<K,V> next() { return nextNode(); }
    }
    abstract class LinkedHashIterator {
        //下一個(gè)節點(diǎn)
        LinkedHashMap.Entry<K,V> next;
        //當前節點(diǎn)
        LinkedHashMap.Entry<K,V> current;
        int expectedModCount;
        LinkedHashIterator() {
            //初始化時(shí)，next 為 LinkedHashMap內部維護的雙向鏈表的扁頭
            next = head;
            //記錄當前modCount，以滿(mǎn)足fail-fast
            expectedModCount = modCount;
            //當前節點(diǎn)為null
            current = null;
        }
        //判斷是否還有next
        public final boolean hasNext() {
            //就是判斷next是否為null，默認next是head  表頭
            return next != null;
        }
        //nextNode() 就是迭代器里的next()方法 。
        //該方法的實(shí)現可以看出，迭代LinkedHashMap，就是從內部維護的雙鏈表的表頭開(kāi)始循環(huán)輸出。
        final LinkedHashMap.Entry<K,V> nextNode() {
            //記錄要返回的e。
            LinkedHashMap.Entry<K,V> e = next;
            //判斷fail-fast
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            //如果要返回的節點(diǎn)是null，異常
            if (e == null)
                throw new NoSuchElementException();
            //更新當前節點(diǎn)為e
            current = e;
            //更新下一個(gè)節點(diǎn)是e的后置節點(diǎn)
            next = e.after;
            //返回e
            return e;
        }
        //刪除方法 最終還是調用了HashMap的removeNode方法
        public final void remove() {
            Node<K,V> p = current;
            if (p == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            current = null;
            K key = p.key;
            removeNode(hash(key), key, null, false, false);
            expectedModCount = modCount;
        }
    }

該方法的實(shí)現可以看出，迭代LinkedHashMap，就是從內部維護的雙鏈表的表頭開(kāi)始循環(huán)輸出。而雙鏈表節點(diǎn)的順序在LinkedHashMap的增、刪、改、查時(shí)都會(huì )更新。以滿(mǎn)足按照插入順序輸出，還是訪(fǎng)問(wèn)順序輸出。

總結

在日常開(kāi)發(fā)中LinkedHashMap 的使用頻率沒(méi)有HashMap高，但它也個(gè)重要的實(shí)現。
在 Java 集合框架中，HashMap、LinkedHashMap 和 TreeMap 三個(gè)映射類(lèi)基于不同的數據結構，并實(shí)現了不同的功能。
HashMap 底層基于拉鏈式的散列結構，并在 JDK 1.8 中引入紅黑樹(shù)優(yōu)化過(guò)長(cháng)鏈表的問(wèn)題?；谶@樣結構，HashMap 可提供高效的增刪改查操作。
LinkedHashMap 在其之上，通過(guò)維護一條雙向鏈表，實(shí)現了散列數據結構的有序遍歷。
TreeMap 底層基于紅黑樹(shù)實(shí)現，利用紅黑樹(shù)的性質(zhì)，實(shí)現了鍵值對排序功能。具體實(shí)現我們下次分析。

以上就是Java LinkedHashMap 底層實(shí)現原理分析的詳細內容，更多關(guān)于Java LinkedHashMap 底層實(shí)現原理的資料請關(guān)注腳本之家其它相關(guān)文章！