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

更新時(shí)間：2021年05月21日 09:57:11 作者：yanliang

LinkedHashMap繼承自HashMap實(shí)現(xiàn)了Map接口?；緦?shí)現(xiàn)同HashMap一樣，不同之處在于LinkedHashMap保證了迭代的有序性。其內(nèi)部維護(hù)了一個(gè)雙向鏈表，解決了 HashMap不能隨時(shí)保持遍歷順序和插入順序一致的問(wèn)題。

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在每次插入數(shù)據(jù)，訪問(wèn)、修改數(shù)據(jù)時(shí)都會(huì)調(diào)整鏈表的節(jié)點(diǎn)順序。以決定迭代時(shí)輸出的順序。

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

LinkedHashMap繼承了HashMap，內(nèi)部靜態(tài)類Entry繼承了HashMap的Entry，但是LinkedHashMap.Entry多了兩個(gè)字段：before和after，before表示在本節(jié)點(diǎn)之前添加到LinkedHashMap的那個(gè)節(jié)點(diǎn)，after表示在本節(jié)點(diǎn)之后添加到LinkedHashMap的那個(gè)節(jié)點(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í)類里有兩個(gè)成員變量head和tail,分別指向內(nèi)部雙向鏈表的表頭、表尾。

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

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

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

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

添加元素

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

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

刪除元素

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

//在刪除節(jié)點(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;
    //將待刪除節(jié)點(diǎn) p 的前置后置節(jié)點(diǎn)都置空
    p.before = p.after = null;
    //如果前置節(jié)點(diǎn)是null，則說(shuō)明現(xiàn)在的頭結(jié)點(diǎn)應(yīng)該是后置節(jié)點(diǎn)a
    if (b == null)
        head = a;
    else//否則將前置節(jié)點(diǎn)b的后置節(jié)點(diǎn)指向a
        b.after = a;
    //同理如果后置節(jié)點(diǎn)時(shí)null ，則尾節(jié)點(diǎn)應(yīng)是b
    if (a == null)
        tail = b;
    else//否則更新后置節(jié)點(diǎn)a的前置節(jié)點(diǎn)為b
        a.before = b;
}

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

根據(jù) hash 定位到桶位置
遍歷鏈表或調(diào)用紅黑樹(shù)相關(guān)的刪除方法
回調(diào)afterNodeRemoval，從 LinkedHashMap 維護(hù)的雙鏈表中移除要?jiǎng)h除的節(jié)點(diǎn)

更新元素

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

查找元素

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

public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder)  // 回調(diào)afterNodeAccess(Node<K,V> e)
        afterNodeAccess(e);  // 將節(jié)點(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;//原尾節(jié)點(diǎn)
    //如果accessOrder 是true ，且原尾節(jié)點(diǎn)不等于e
    if (accessOrder && (last = tail) != e) {
        //節(jié)點(diǎn)e強(qiáng)轉(zhuǎn)成雙向鏈表節(jié)點(diǎn)p
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        //p現(xiàn)在是尾節(jié)點(diǎn)， 后置節(jié)點(diǎn)一定是null
        p.after = null;
        //如果p的前置節(jié)點(diǎn)是null，則p以前是頭結(jié)點(diǎn)，所以更新現(xiàn)在的頭結(jié)點(diǎn)是p的后置節(jié)點(diǎn)a
        if (b == null)
            head = a;
        else//否則更新p的前直接點(diǎn)b的后置節(jié)點(diǎn)為 a
            b.after = a;
        //如果p的后置節(jié)點(diǎn)不是null，則更新后置節(jié)點(diǎn)a的前置節(jié)點(diǎn)為b
        if (a != null)
            a.before = b;
        else//如果原本p的后置節(jié)點(diǎn)是null，則p就是尾節(jié)點(diǎn)。 此時(shí) 更新last的引用為 p的前置節(jié)點(diǎn)b
            last = b;
        if (last == null) //原本尾節(jié)點(diǎn)是null  則，鏈表中就一個(gè)節(jié)點(diǎn)
            head = p;
        else {//否則 更新 當(dāng)前節(jié)點(diǎn)p的前置節(jié)點(diǎn)為 原尾節(jié)點(diǎn)last， last的后置節(jié)點(diǎn)是p
            p.before = last;
            last.after = p;
        }
        //尾節(jié)點(diǎn)的引用賦值成p
        tail = p;
        //修改modCount。
        ++modCount;
    }
}
// 因?yàn)長(zhǎng)inkedHashMap中維護(hù)了一個(gè)雙向鏈表所以相對(duì)于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;
    // 根據(jù)條件判斷是否移除最近最少被訪問(wèn)的節(jié)點(diǎn)
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}
// 移除最近最少被訪問(wèn)條件之一，通過(guò)覆蓋此方法可實(shí)現(xiàn)不同策略的緩存
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

上面的方法一般不會(huì)被執(zhí)行，但是當(dāng)我們基于 LinkedHashMap 實(shí)現(xiàn)緩存時(shí)，通過(guò)覆寫(xiě)removeEldestEntry方法可以實(shí)現(xiàn)自定義策略的 LRU 緩存。比如我們可以根據(jù)節(jié)點(diǎn)數(shù)量判斷是否移除最近最少被訪問(wèn)的節(jié)點(diǎn)，或者根據(jù)節(jié)點(diǎn)的存活時(shí)間判斷是否移除該節(jié)點(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è)節(jié)點(diǎn)
        LinkedHashMap.Entry<K,V> next;
        //當(dāng)前節(jié)點(diǎn)
        LinkedHashMap.Entry<K,V> current;
        int expectedModCount;
        LinkedHashIterator() {
            //初始化時(shí)，next 為 LinkedHashMap內(nèi)部維護(hù)的雙向鏈表的扁頭
            next = head;
            //記錄當(dāng)前modCount，以滿足fail-fast
            expectedModCount = modCount;
            //當(dāng)前節(jié)點(diǎn)為null
            current = null;
        }
        //判斷是否還有next
        public final boolean hasNext() {
            //就是判斷next是否為null，默認(rèn)next是head  表頭
            return next != null;
        }
        //nextNode() 就是迭代器里的next()方法 。
        //該方法的實(shí)現(xiàn)可以看出，迭代LinkedHashMap，就是從內(nèi)部維護(hù)的雙鏈表的表頭開(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();
            //如果要返回的節(jié)點(diǎn)是null，異常
            if (e == null)
                throw new NoSuchElementException();
            //更新當(dāng)前節(jié)點(diǎn)為e
            current = e;
            //更新下一個(gè)節(jié)點(diǎn)是e的后置節(jié)點(diǎn)
            next = e.after;
            //返回e
            return e;
        }
        //刪除方法 最終還是調(diào)用了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í)現(xiàn)可以看出，迭代LinkedHashMap，就是從內(nèi)部維護(hù)的雙鏈表的表頭開(kāi)始循環(huán)輸出。而雙鏈表節(jié)點(diǎn)的順序在LinkedHashMap的增、刪、改、查時(shí)都會(huì)更新。以滿足按照插入順序輸出，還是訪問(wèn)順序輸出。

總結(jié)

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

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

您可能感興趣的文章: