一、容器之Map集合

集合體系的源碼中，Map中的HashMap的設(shè)計堪稱最經(jīng)典，涉及數(shù)據(jù)結(jié)構(gòu)、編程思想、哈希計算等等，在日常開發(fā)中對于一些源碼的思想進行參考借鑒還是很有必要的。

• 基礎(chǔ)：元素增查刪、容器信息；
• 進階：存儲結(jié)構(gòu)、容量、哈希；

API體系

在整個Map和Set的API體系中，最重要的就是HashMap的實現(xiàn)原理：

• HashMap：基于哈希表管理元素；
• LinkedHashMap：基于HashMap和雙向鏈表；
• HashSet：底層維護HashMap結(jié)構(gòu)；
• LinkedHashSet：繼承HashSet，雙向鏈表；

所以Map和Set的系列中，除特殊API之外，基本原理都依賴HashMap，只是在各自具體實現(xiàn)時，適用于不同特點的元素管理。

二、數(shù)據(jù)結(jié)構(gòu)

在看HashMap之前，先理解一種數(shù)據(jù)結(jié)構(gòu)：數(shù)組+鏈表的結(jié)構(gòu)。

基于數(shù)組管理元素的位置，元素的存儲形成鏈表結(jié)構(gòu)，既然是鏈表那么就可以是單雙向的結(jié)構(gòu)，這需要針對具體的API去分析，通過這個結(jié)構(gòu)可以得到幾個關(guān)鍵信息：

• 擴容：基于數(shù)組則面對擴容問題；
• 鏈表：形成鏈表結(jié)構(gòu)的機制；
• 哈希：哈希值計算與沖突處理；

三、HashMap詳解

1、結(jié)構(gòu)封裝

既然上面簡單描述了數(shù)組+鏈表的結(jié)構(gòu)，那么從源碼角度看看是如何封裝的：

transient Node<K,V>[] table;

在HashMap中數(shù)組結(jié)構(gòu)的變量命名為table（表），并且是基于Node<K,V>的節(jié)點：

static class Node<K,V> implements Map.Entry<K,V> {final int hash;final K key;V value;Node<K,V> next; }

實現(xiàn)Map.Entry接口，并定義節(jié)點的結(jié)構(gòu)變量，和節(jié)點自身的相關(guān)方法。

2、構(gòu)造方法

在知道HashMap中的基礎(chǔ)結(jié)構(gòu)后，可以看其相關(guān)的構(gòu)造方法，初始化哪些變量：

無參構(gòu)造

public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; }

• float DEFAULT_LOAD_FACTOR = 0.75f;
• this.loadFactor = DEFAULT_LOAD_FACTOR;

實際上還要關(guān)注一個核心參數(shù)：

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16

即數(shù)組默認的初始化容量DEFAULT_INITIAL_CAPACITY為16，擴容的閾值loadFactor為0.75，即表示當(dāng)數(shù)組中元素達到12個便會進行擴容操作。

有參構(gòu)造

當(dāng)然也可以通過有參構(gòu)造方法去設(shè)置兩個參數(shù)：即容量和擴容的閾值：

public HashMap(int initialCapacity, float loadFactor) ;

通過兩個構(gòu)造方法的源碼可知：當(dāng)直接創(chuàng)建新的HashMap的時候，不會立即對哈希數(shù)組進行初始化，但是可以對關(guān)鍵變量做自定義設(shè)置。

3、裝載元素

順著HashMap的使用方法，看元素添加：

public V put(K key, V value) {return putVal(hash(key), key, value, false, true); }

在put的時候并沒有做過多直接操作，而是調(diào)用兩個關(guān)鍵方法：

• hash()：計算key的hash值；
• putVal()：元素添加過程；

這里必須看一個關(guān)鍵方法，哈希值的計算：

static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

并不是直接獲取Object中hashCode的返回值，計算key對應(yīng)的hashCode值，和hashCode值右移16位的值，并對兩個結(jié)果進行異或運算，以此拉低哈希沖突發(fā)生的概率。

再看putVal()方法，這里的操作就相當(dāng)精彩：

核心步驟總結(jié)：

• 首次執(zhí)行判斷并初始化底層數(shù)組；
• 基于哈希值計算結(jié)果添加元素；
• 根據(jù)添加元素后的容量來判斷是否擴容；

這里還需要說明一個問題：

HashMap基于紅黑樹來處理哈希沖突問題，如果hash沖突過多，對O(n)的查詢性能的影響非常大，當(dāng)沖突節(jié)點鏈表的沖突元素數(shù)量到達8時，并且數(shù)組的長度到達64時，會使用紅黑樹結(jié)構(gòu)代替鏈表來處理哈希沖突的查詢性能問題，關(guān)于樹結(jié)構(gòu)可以移步之前的相關(guān)文章。

4、自動化擴容

容器在一定邊界內(nèi)可以不斷添加元素，其核心的機制就是擴容，HashMap的擴容遵循最小可用原則，當(dāng)然容量到達閾值，便會觸發(fā)自動擴容機制。

閾值：threshold=capacity*loadFactor，默認即 16*0.75=12。

核心方法：resize；

核心步驟總結(jié)：

• 判斷擴容的邊界參數(shù)：threshold；
• 核心參數(shù)計算：容量和閾值；
• 基于新參數(shù)創(chuàng)建一個新的空數(shù)組；
• 原數(shù)組為null則過程可以理解為初始化；
• 原數(shù)組不為null則擴容并遷移數(shù)據(jù)；

很顯然如果涉及數(shù)組擴容則會很影響效率，所以在日常開發(fā)中，可以在使用HashMap的時候預(yù)先估計好HashMap的大小，保證閾值大于存儲的元素數(shù)量，盡可能避免進行多次擴容操作。

5、查詢元素

getNode查找方法，通過hash值的計算，然后依次經(jīng)過數(shù)組、紅黑樹、鏈表進行遍歷查詢：

6、刪除元素

removeNode刪除方法，首先通過hash值的計算，找到要刪除的節(jié)點，然后判斷索引位置是紅黑樹還是鏈表結(jié)構(gòu)，分別執(zhí)行各自的刪除流程：

7、補充說明

這里對兩個方法做個簡單的說明：hashCode()與equals()，通常來說重寫equals方法的時候需要重寫hashCode方法。

這兩個方法都可以用來比較兩個對象是否相等，但是hash值有存在沖突的情況，可能存在兩個對象的hash值沖突，這時候可以通過equals判斷對象值是否相同，==判斷值對象，地址判斷引用對象。

在HashMap的結(jié)構(gòu)中，鏈表上的hash值相同情況還要通過equals方法來判斷具體值是否相同，才能找到相應(yīng)的對象。

四、源代碼地址

GitHub·地址 https://github.com/cicadasmile/java-base-parent GitEE·地址 https://gitee.com/cicadasmile/java-base-parent

閱讀標(biāo)簽

【Java基礎(chǔ)】【設(shè)計模式】【結(jié)構(gòu)與算法】【Linux系統(tǒng)】【數(shù)據(jù)庫】

【分布式架構(gòu)】【微服務(wù)】【大數(shù)據(jù)組件】【SpringBoot進階】【Spring&Boot基礎(chǔ)】

【數(shù)據(jù)分析】【技術(shù)導(dǎo)圖】【 職場】

總結(jié)

以上是生活随笔為你收集整理的Java容器 | 基于源码分析Map集合体系的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。