概述

LinkedHashMap是HashMap的子類，它的大部分實現(xiàn)與HashMap相同，兩者最大的區(qū)別在于，HashMap的對哈希表進行迭代時是無序的，而LinkedHashMap對哈希表迭代是有序的，LinkedHashMap默認的規(guī)則是，迭代輸出的結(jié)果保持和插入key-value pair的順序一致（當(dāng)然具體迭代規(guī)則可以修改）。LinkedHashMap除了像HashMap一樣用數(shù)組、單鏈表和紅黑樹來組織數(shù)據(jù)外，還額外維護了一個雙向鏈表，每次向linkedHashMap插入鍵值對，除了將其插入到哈希表的對應(yīng)位置之外，還要將其插入到雙向循環(huán)鏈表的尾部。

創(chuàng)新互聯(lián)建站主要從事網(wǎng)站建設(shè)、成都網(wǎng)站制作、網(wǎng)頁設(shè)計、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)海門,十載網(wǎng)站建設(shè)經(jīng)驗,價格優(yōu)惠、服務(wù)專業(yè),歡迎來電咨詢建站服務(wù):028-86922220

底層實現(xiàn)

先來看一下LinekedHashMap的定義：

public?class?LinkedHashMap
????extends?HashMap
????implements?Map

除了繼承自HashMap以外并無太多特殊之處，這里特地標注實現(xiàn)了Map接口應(yīng)該也只是為了醒目。

大家最關(guān)心的應(yīng)該是LinkedHashMap如何實現(xiàn)有序迭代，下面將逐步通過源碼來解答這一問題。

先看一下一個重要的靜態(tài)內(nèi)部類Entry：

static?class?Entry?extends?HashMap.Node?{
????Entry?before,?after;
????Entry(int?hash,?K?key,?V?value,?Node?next)?{
????????super(hash,?key,?value,?next);
????}}

該類繼承自HashMap的Node內(nèi)部類，前面已經(jīng)介紹過，Node是一個單鏈表結(jié)構(gòu)，這里Entry添加了前繼引用和后繼引用，則是一個雙向鏈表的節(jié)點。在雙向鏈表中，每個節(jié)點可以記錄自己前后插入的節(jié)點信息，以維持有序性，這也是LinkedHashMap實現(xiàn)有序迭代的關(guān)鍵。

按插入順序有序和按訪問順序有序

按插入有序

按插入有序即先添加的在前面，后添加的在后面，修改操作不影響順序。以如下代碼為例：

Map?seqMap?=?new?LinkedHashMap<>();seqMap.put("c",?100);seqMap.put("d",?200);seqMap.put("a",?500);seqMap.put("d",?300);for(Entry?entry?:?seqMap.entrySet()){
????System.out.println(entry.getKey()+"?"+entry.getValue());}運行結(jié)

運行結(jié)果是：

c?100d?300a?500

可以看到，鍵是按照”c”, “d”, “a”的順序插入的，修改”d”的值不會修改順序。

按訪問有序

按訪問有序是，序列末尾存放的是最近訪問的key-value pair，每次訪問一個key-value pair后，就會將其移動到末尾。

Map?accessMap?=?new?LinkedHashMap<>(16,?0.75f,?true);accessMap.put("c",?100);accessMap.put("d",?200);accessMap.put("a",?500);accessMap.get("c");accessMap.put("d",?300);for(Entry?entry?:?accessMap.entrySet()){
????System.out.println(entry.getKey()+"?"+entry.getValue());}

運行結(jié)果為：

a?500?
c?100?
d?300

針對不同的應(yīng)用場景，LinkedHashMap可以在這兩種排序方式中進行抉擇。

LinkedHashMap定義了三個重要的字段：

//雙鏈表的頭節(jié)點transient?LinkedHashMap.Entry?head;//雙鏈表的尾節(jié)點transient?LinkedHashMap.Entry?tail;/**?*?這個字段表示哈希表的迭代順序?*?true表示按訪問順序迭代?*?false表示按插入順序迭代?*?LinkedHashMap的構(gòu)造函數(shù)均將該值設(shè)為false，因此默認為false?*/final?boolean?accessOrder;

關(guān)于它們的具體作用已在注釋中標出。

LinkedHashMap有五個構(gòu)造方法，其中有一個可以指定accessOrder的值：

public?LinkedHashMap(int?initialCapacity,
?????????????????????float?loadFactor,
?????????????????????boolean?accessOrder)?{
????super(initialCapacity,?loadFactor);
????this.accessOrder?=?accessOrder;}

重要方法

在HashMap中定義了幾個“鉤子”方法（關(guān)于鉤子的詳細內(nèi)容，請參考筆者的博客設(shè)計模式(9)——模板方法模式），這里特地列出其中的三個：

• afterNodeRemoval(e)

• afterNodeInsertion

• afterNodeInsertion

它們與迭代有序性的實現(xiàn)息息相關(guān)。

此外還有兩個重要的APIget和containsValue，這里也分析一下它們的源碼實現(xiàn)，至于put方法，LinkedHashMap并沒有覆寫該方法，因此其實現(xiàn)與HashMap相同。

afterNodeRemoval(e)方法

void?afterNodeRemoval(Node?e)?{?//?unlink????LinkedHashMap.Entry?p?=
????????(LinkedHashMap.Entry)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;}

在HashMap的removeNode方法中調(diào)用了該鉤子方法，對于LinkedHashMap，在執(zhí)行完對哈希桶中單鏈表或紅黑樹節(jié)點的刪除操作后，還需要調(diào)用該方法將雙向鏈表中對應(yīng)的Entry刪除。

afterNodeInsertion方法

void?afterNodeInsertion(boolean?evict)?{?//?possibly?remove?eldest????LinkedHashMap.Entry?first;
????if?(evict?&&?(first?=?head)?!=?null?&&?removeEldestEntry(first)){
????????K?key?=?first.key;
????????removeNode(hash(key),?key,?null,?false,?true);
????}}

在HashMap的putVal方法中調(diào)用了該方法，可以看出，在判斷條件成立的情況下，該方法會刪除雙鏈表中的頭節(jié)點（當(dāng)然是在哈希桶和雙向鏈表中同步刪除該節(jié)點）。判斷條件涉及了一個removeEldestEntry(first)方法，它的源碼如下：

protected?boolean?removeEldestEntry(Map.Entry?eldest)?{
????return?false;}

可以看到，它默認是返回false的，即不刪除頭節(jié)點。如果需要定義是否需要刪除頭節(jié)點的規(guī)則，只需覆蓋該方法并提供相關(guān)實現(xiàn)即可。該方法的作用在于，它提供了當(dāng)一個新的entry被添加到linkedHashMap中，刪除頭節(jié)點的機會。這是非常有意義的，可以通過刪除頭節(jié)點來減少內(nèi)存消耗，避免內(nèi)存溢出。

afterNodeAccess(e)方法

void?afterNodeAccess(Node?e)?{?//?move?node?to?last????LinkedHashMap.Entry?last;
????if?(accessOrder?&&?(last?=?tail)?!=?e)?{
????????LinkedHashMap.Entry?p?=
????????????(LinkedHashMap.Entry)e,?b?=?p.before,?a?=?p.after;
????????p.after?=?null;
????????if?(b?==?null)
????????????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;
????????++modCount;
????}}

該方法在HashMap的putVal方法、LinkedHashMap的get方法中都被調(diào)用，它的作用是：如果accessOrder返回值為true（即按照訪問順序迭代），則將最近訪問的節(jié)點調(diào)整至雙向隊列的隊尾，這也就保證了按照訪問順序迭代時Entry的有序性。

get(key)方法

public?V?get(Object?key)?{
????Node?e;
????if?((e?=?getNode(hash(key),?key))?==?null)
????????return?null;
????if?(accessOrder)
????????afterNodeAccess(e);
????return?e.value;}

該方法增加了按訪問順序或插入順序進行排序的選擇功能，會根據(jù)AccessOrder的值調(diào)整雙向鏈表中節(jié)點的順序，獲取節(jié)點的過程與HashMap中一致。

containsValue(value)方法

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

由于LinkedHashMap維護了一個雙向鏈表，因此它的containsValue(value)方法直接遍歷雙向鏈表查找對應(yīng)的Entry即可，而無需去遍歷哈希桶。

LinkedHashMap與HashMap

LinkedHashMap是HashMap的子類，它們最大的區(qū)別是，HashMap的迭代是無序的，而LinkedHashMap是有序的，并且有按插入順序和按訪問順序兩種方式。為了實現(xiàn)有序迭代，LinkedHashMap相比HashMap，額外維護了一個雙向鏈表，因此一般情況下，遍歷HashMap比LinkedHashMap效率要高，在沒有按序訪問key-value pair的情況下，一般建議使用HashMap（當(dāng)然也有例外，當(dāng)HashMap容量很大，實際數(shù)據(jù)較少時，遍歷起來可能會比 LinkedHashMap慢，因為LinkedHashMap的遍歷速度只和實際數(shù)據(jù)有關(guān)，和容量無關(guān)，而HashMap的遍歷速度和他的容量有關(guān)）。