Java集合之LinkedHashMap源碼解析

QiShare 發(fā)布于2019-08-16 12:35 / 1011人閱讀

摘要：底層基于拉鏈?zhǔn)降纳⒘薪Y(jié)構(gòu)，并在中引入紅黑樹優(yōu)化過長(zhǎng)鏈表的問題。在其之上，通過維護(hù)一條雙向鏈表，實(shí)現(xiàn)了散列數(shù)據(jù)結(jié)構(gòu)的有序遍歷。

原文地址

LinkedHashMap

LinkedHashMap繼承自HashMap實(shí)現(xiàn)了Map接口?；緦?shí)現(xiàn)同HashMap一樣，不同之處在于LinkedHashMap保證了迭代的有序性。其內(nèi)部維護(hù)了一個(gè)雙向鏈表，解決了 HashMap不能隨時(shí)保持遍歷順序和插入順序一致的問題。
除此之外，LinkedHashMap對(duì)訪問順序也提供了相關(guān)支持。在一些場(chǎng)景下，該特性很有用，比如緩存。

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

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

這里我們只討論LinkedHashMap和HashMap的不同之處，LinkedHashMap的其他操作和特性具體請(qǐng)參考HashMap的實(shí)現(xiàn)

我們先來看下兩者的區(qū)別：

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 map = new LinkedHashMap();
        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 map1 = new LinkedHashMap(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 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ù)，訪問、修改數(shù)據(jù)時(shí)都會(huì)調(diào)整鏈表的節(jié)點(diǎn)順序。以決定迭代時(shí)輸出的順序。

下面我們來看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 extends HashMap.Node {
    Entry before, after;
    Entry(int hash, K key, V value, Node next) {
        super(hash, key, value, next);
    }
}

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

//雙向鏈表的頭結(jié)點(diǎn)
transient LinkedHashMap.Entry head;

//雙向鏈表的尾節(jié)點(diǎn)
transient LinkedHashMap.Entry tail;

我們通過兩張圖來看下LinkedHashMap的存儲(chǔ)結(jié)構(gòu)

圖片來自：coolblog

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

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

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 來構(gòu)建
public LinkedHashMap(Map m) {
    super();
    accessOrder = false;
    //該方法上文分析過，批量插入一個(gè)map中的所有數(shù)據(jù)到 本集合中。
    putMapEntries(m, false);
}

添加元素

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

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

刪除元素

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

//在刪除節(jié)點(diǎn)e時(shí)，同步將e從雙向鏈表上刪除
void afterNodeRemoval(Node e) { // unlink
    LinkedHashMap.Entry p =
        (LinkedHashMap.Entry)e, b = p.before, a = p.after;
    //將待刪除節(jié)點(diǎn) p 的前置后置節(jié)點(diǎn)都置空
    p.before = p.after = null;
    //如果前置節(jié)點(diǎn)是null，則說明現(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;
}

刪除過程總的來說可以分為三步：

根據(jù) hash 定位到桶位置

遍歷鏈表或調(diào)用紅黑樹相關(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重寫了get()和getOrDefault()方法

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

public V get(Object key) {
    Node e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder)  // 回調(diào)afterNodeAccess(Node e)
        afterNodeAccess(e);  // 將節(jié)點(diǎn)e移至雙向鏈表的尾部（保證迭代順序）
    return e.value;
}
public V getOrDefault(Object key, V defaultValue) {
   Node e;
   if ((e = getNode(hash(key), key)) == null)
       return defaultValue;
   if (accessOrder)
       afterNodeAccess(e);    // 作用同上
   return e.value;
}

void afterNodeAccess(Node e) { // move node to last
    LinkedHashMap.Entry 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 p =
            (LinkedHashMap.Entry)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 e = head; e != null; e = e.after) {   // 通過雙向鏈表來遍歷
        V v = e.value;
        if (v == value || (value != null && value.equals(v)))
            return true;
    }
    return false;
}

HashMap
public boolean containsValue(Object value) {
    Node[] tab; V v;
    if ((tab = table) != null && size > 0) {
        for (int i = 0; i < tab.length; ++i) {
            for (Node 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 first;
    // 根據(jù)條件判斷是否移除最近最少被訪問的節(jié)點(diǎn)
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

// 移除最近最少被訪問條件之一，通過覆蓋此方法可實(shí)現(xiàn)不同策略的緩存
protected boolean removeEldestEntry(Map.Entry eldest) {
    return false;
}

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

　迭代器

public Set> entrySet() {
        Set> es;
        //返回LinkedEntrySet
        return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es;
    }
    final class LinkedEntrySet extends AbstractSet> {
        public final Iterator> iterator() {
            return new LinkedEntryIterator();
        }
    }
final class LinkedEntryIterator extends LinkedHashIterator
        implements Iterator> {
        public final Map.Entry next() { return nextNode(); }
    }

    abstract class LinkedHashIterator {
        //下一個(gè)節(jié)點(diǎn)
        LinkedHashMap.Entry next;
        //當(dāng)前節(jié)點(diǎn)
        LinkedHashMap.Entry 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ù)的雙鏈表的表頭開始循環(huán)輸出。
        final LinkedHashMap.Entry nextNode() {
            //記錄要返回的e。
            LinkedHashMap.Entry 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 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ù)的雙鏈表的表頭開始循環(huán)輸出。而雙鏈表節(jié)點(diǎn)的順序在LinkedHashMap的增、刪、改、查時(shí)都會(huì)更新。以滿足按照插入順序輸出，還是訪問順序輸出。

總結(jié)

總結(jié)：

在日常開發(fā)中LinkedHashMap 的使用頻率沒有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 中引入紅黑樹優(yōu)化過長(zhǎng)鏈表的問題?；谶@樣結(jié)構(gòu)，HashMap 可提供高效的增刪改查操作。

LinkedHashMap 在其之上，通過維護(hù)一條雙向鏈表，實(shí)現(xiàn)了散列數(shù)據(jù)結(jié)構(gòu)的有序遍歷。

TreeMap 底層基于紅黑樹實(shí)現(xiàn)，利用紅黑樹的性質(zhì)，實(shí)現(xiàn)了鍵值對(duì)排序功能。具體實(shí)現(xiàn)我們下次分析。

云服務(wù)器 GPU云服務(wù)器 java集合源碼分析源碼中文說明之 linkedhashmap java 集合

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/71355.html

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

QiShare

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章

#11.11#ZJI：自營(yíng)香港/阿里云專線服務(wù)器全部55折優(yōu)惠，999元可獲得1100元余額

閱讀 1394·2021-11-08 13:14
HostDare：洛杉磯CN2 GIA VPS;1核/756MB內(nèi)存/35GB硬盤/600GB流量/

閱讀 747·2021-09-23 11:31
SaltyfishTech：$15.91/季/1GB內(nèi)存/10GB SSD空間/600GB流量/30

閱讀 1038·2021-07-29 13:48
用vue和node寫的簡(jiǎn)易購(gòu)物車

閱讀 2781·2019-08-29 12:29
css基礎(chǔ)知識(shí)整理篇

閱讀 3371·2019-08-29 11:24
React Native 更新實(shí)踐（非熱更新）

閱讀 1899·2019-08-26 12:02
小程序·云開發(fā)實(shí)戰(zhàn) - 校園約拍小程序

閱讀 3688·2019-08-26 10:34
CSS動(dòng)畫優(yōu)雅降級(jí)的簡(jiǎn)單總結(jié)

閱讀 3435·2019-08-23 17:07

国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來選購(gòu)！

Java集合之LinkedHashMap源碼解析

相關(guān)文章

**[學(xué)習(xí)筆記-Java集合-5]Map - LinkedHashMap源碼分析**

java源碼

Java相關(guān)

后臺(tái)開發(fā)常問面試題集錦（問題搬運(yùn)工，附鏈接）

發(fā)表評(píng)論

0條評(píng)論

QiShare

男|高級(jí)講師

TA的文章

#11.11#ZJI：自營(yíng)香港/阿里云專線服務(wù)器全部55折優(yōu)惠，999元可獲得1100元余額

HostDare：洛杉磯CN2 GIA VPS;1核/756MB內(nèi)存/35GB硬盤/600GB流量/

SaltyfishTech：$15.91/季/1GB內(nèi)存/10GB SSD空間/600GB流量/30

用vue和node寫的簡(jiǎn)易購(gòu)物車

css基礎(chǔ)知識(shí)整理篇

React Native 更新實(shí)踐（非熱更新）

小程序·云開發(fā)實(shí)戰(zhàn) - 校園約拍小程序

CSS動(dòng)畫優(yōu)雅降級(jí)的簡(jiǎn)單總結(jié)

最新活動(dòng)

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來選購(gòu)！

Java集合之LinkedHashMap源碼解析

相關(guān)文章

發(fā)表評(píng)論

0條評(píng)論

男|高級(jí)講師

TA的文章

最新活動(dòng)

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來選購(gòu)！