別眨眼網

前言

這次我和大家一起學習

HashMap

，

HashMap

我們在工作中經常會使用，而且面試中也很頻繁會問到，因為它裡面蘊含著很多知識點，可以很好的考察個人基礎。但一個這麼重要的東西，我為什麼沒有在一開始就去學習它呢，因為它是由多種基礎的資料結構和一些程式碼設計思想組成的。我們要學習了這些基礎，再學習

HashMap

，這樣我們才能更好的去理解它。古人云：無慾速，無見小利。欲速則不達，見小利則大事不成。

HashMap

其實就是

ArrayList

和

LinkedList

的資料結構加上

hashCode

和

equals

方法的思想設計出來的。沒有理解上述說的知識點的同學可以翻開我過往的文章記錄。

下面我就以面試問答的形式學習我們的——

HashMap

（原始碼分析基於JDK8，輔以JDK7），問答內容只是對

HashMap

的一個總結歸納。

問答內容

1。問：

HashMap

有用過嗎？您能給我說說他的主要用途嗎？

答：

HashMap

是基於

Map

介面實現的一種鍵-值對

的儲存結構，允許

null

值，同時非有序，非同步（即執行緒不安全）。

HashMap

的底層實現是陣列 + 連結串列 + 紅黑樹（JDK1。8增加了紅黑樹部分）。它儲存和查詢資料時，是根據鍵

key

的

hashCode

的值計算出具體的儲存位置。

HashMap

最多隻允許一條記錄的鍵

key

為

null

，

HashMap

增刪改查等常規操作都有不錯的執行效率，是

ArrayList

和

LinkedList

等資料結構的一種折中實現。

示例程式碼：

// 建立一個HashMap，如果沒有指定初始大小，預設底層hash表陣列的大小為16 HashMap hashMap = new HashMap（）； // 往容器裡面新增元素 hashMap。put（“小明”， “好帥”）； hashMap。put（“老王”， “坑爹貨”）； hashMap。put（“老鐵”， “沒毛病”）； hashMap。put（“掘金”， “好地方”）； hashMap。put（“王五”， “別搞事”）； // 獲取key為小明的元素 好帥 String element = hashMap。get（“小明”）； // value ： 好帥 System。out。println（element）； // 移除key為王五的元素 String removeElement = hashMap。remove（“王五”）； // value ： 別搞事 System。out。println（removeElement）； // 修改key為小明的元素的值value 為 其實有點醜 hashMap。replace（“小明”， “其實有點醜”）； // {老鐵=沒毛病， 小明=其實有點醜， 老王=坑爹貨， 掘金=好地方} System。out。println（hashMap）； // 透過put方法也可以達到修改對應元素的值的效果 hashMap。put（“小明”， “其實還可以啦，開玩笑的”）； // {老鐵=沒毛病， 小明=其實還可以啦，開玩笑的， 老王=坑爹貨， 掘金=好地方} System。out。println（hashMap）； // 判斷key為老王的元素是否存在（捉姦老王） boolean isExist = hashMap。containsKey（“老王”）； // true ， 老王竟然來搞事 System。out。println（isExist）； // 判斷是否有 value = “坑爹貨” 的人 boolean isHasSomeOne = hashMap。containsValue（“坑爹貨”）； // true 老王是坑爹貨 System。out。println（isHasSomeOne）； // 檢視這個容器裡面還有幾個傢伙 value ： 4 System。out。println（hashMap。size（））；

HashMap的底層實現是陣列 + 連結串列 + 紅黑樹（JDK1。8增加了紅黑樹部分），核心組成元素有：

int size；用於記錄

HashMap

實際儲存元素的個數；

float loadFactor；

負載因子（預設是0。75，此屬性後面詳細解釋）。

int threshold；

下一次擴容時的閾值，達到閾值便會觸發擴容機制

resize

（閾值 threshold = 容器容量 capacity * 負載因子 load factor）。也就是說，在容器定義好容量之後，負載因子越大，所能容納的鍵值對元素個數就越多。

Node［］ table；

底層陣列，充當雜湊表的作用，用於儲存對應hash位置的元素

Node

，此陣列長度總是2的N次冪。（具體原因後面詳細解釋）

示例程式碼：

public class HashMap extends AbstractMap implements Map， Cloneable， Serializable {····· /* ———————— Fields ———————— */ /** * 雜湊表，在第一次使用到時進行初始化，重置大小是必要的操作， * 當分配容量時，長度總是2的N次冪。 */ transient Node［］ table； /** * 實際儲存的key - value 鍵值對 個數 */ transient int size； /** * 下一次擴容時的閾值 * （閾值 threshold = 容器容量 capacity * 負載因子 load factor）。 * @serial */ int threshold； /** * 雜湊表的負載因子 * * @serial */ final float loadFactor；·····}

其中

Node［］ table；

雜湊表儲存的核心元素是

Node

，

Node

包含：

final int hash；元素的雜湊值，決定元素儲存在

Node［］ table；

雜湊表中的位置。由

final

修飾可知，當

hash

的值確定後，就不能再修改。

final K key

鍵，由

final

修飾可知，當

key

的值確定後，就不能再修改。

V value；

值

Node next；

記錄下一個元素結點（單鏈表結構，用於解決hash衝突）

示例程式碼：

/** * 定義HashMap儲存元素結點的底層實現 */ static class Node implements Map。Entry { final int hash；//元素的雜湊值 由final修飾可知，當hash的值確定後，就不能再修改 final K key；// 鍵，由final修飾可知，當key的值確定後，就不能再修改 V value； // 值 Node next； // 記錄下一個元素結點（單鏈表結構，用於解決hash衝突） /** * Node結點構造方法 */ Node（int hash， K key， V value， Node next） { this。hash = hash；//元素的雜湊值 this。key = key；// 鍵 this。value = value； // 值 this。next = next；// 記錄下一個元素結點 } public final K getKey（） { return key； } public final V getValue（） { return value； } public final String toString（） { return key + “=” + value； } /** * 為Node重寫hashCode方法，值為：key的hashCode 異或 value的hashCode * 運算作用就是將2個hashCode的二進位制中，同一位置相同的值為0，不同的為1。 */ public final int hashCode（） { return Objects。hashCode（key） ^ Objects。hashCode（value）； } /** * 修改某一元素的值 */ public final V setValue（V newValue） { V oldValue = value； value = newValue； return oldValue； } /** * 為Node重寫equals方法 */ public final boolean equals（Object o） { if （o == this） return true； if （o instanceof Map。Entry） { Map。Entry<？，？> e = （Map。Entry<？，？>）o； if （Objects。equals（key， e。getKey（）） && Objects。equals（value， e。getValue（））） return true； } return false； } }

hashMap記憶體結構圖

2。

問：您能說說

HashMap

常用操作的底層實現原理嗎？如儲存

put（K key， V value）

，查詢

get（Object key）

，刪除

remove（Object key）

，修改

replace（K key， V value）

等操作。

答：

呼叫

put（K key， V value）

操作新增

key-value

鍵值對時，進行了如下操作：

判斷雜湊表

Node［］ table

是否為空或者

null

，是則執行

resize（）

方法進行擴容。

根據插入的鍵值

key

的

hash

值，透過

（n - 1） & hash

當前元素的

hash

值 &

hash

表長度 - 1（實際就是

hash

值 %

hash

表長度） 計算出儲存位置

table［i］

。如果儲存位置沒有元素存放，則將新增結點儲存在此位置

table［i］

。

如果儲存位置已經有鍵值對元素存在，則判斷該位置元素的

hash

值和

key

值是否和當前操作元素一致，一致則證明是修改

value

操作，覆蓋

value

即可。

當前儲存位置即有元素，又不和當前操作元素一致，則證明此位置

table［i］

已經發生了hash衝突，則透過判斷頭結點是否是

treeNode

，如果是

treeNode

則證明此位置的結構是紅黑樹，已紅黑樹的方式新增結點。

如果不是紅黑樹，則證明是單鏈表，將新增結點插入至連結串列的最後位置，隨後判斷當前連結串列長度是否 大於等於 8，是則將當前儲存位置的連結串列轉化為紅黑樹。遍歷過程中如果發現

key

已經存在，則直接覆蓋

value

。

插入成功後，判斷當前儲存鍵值對的數量 大於 閾值

threshold

是則擴容。

hashMap put方法執行流程圖

示例程式碼：

/** * 新增key-value鍵值對 * * @param key 鍵 * @param value 值 * @return 如果原本存在此key，則返回舊的value值，如果是新增的key- * value，則返回nulll */ public V put（K key， V value） { //實際呼叫putVal方法進行新增 key-value 鍵值對操作 return putVal（hash（key）， key， value， false， true）； } /** * 根據key 鍵 的 hashCode 透過 “擾動函式” 生成對應的 hash值 * 經過此操作後，使每一個key對應的hash值生成的更均勻， * 減少元素之間的碰撞機率（後面詳細說明） */ static final int hash（Object key） { int h； return （key == null） ？ 0 ： （h = key。hashCode（）） ^ （h >>> 16）； } /** * 新增key-value鍵值對的實際呼叫方法（重點） * * @param hash key 鍵的hash值 * @param key 鍵 * @param value 值 * @param onlyIfAbsent 此值如果是true， 則如果此key已存在value，則不執 * 行修改操作 * @param evict 此值如果是false，雜湊表是在初始化模式 * @return 返回原本的舊值， 如果是新增，則返回null */ final V putVal（int hash， K key， V value， boolean onlyIfAbsent， boolean evict） { // 用於記錄當前的hash表 Node［］ tab； // 用於記錄當前的連結串列結點 Node p； // n用於記錄hash表的長度，i用於記錄當前操作索引index int n， i； // 當前hash表為空 if （（tab = table） == null || （n = tab。length） == 0） // 初始化hash表，並把初始化後的hash表長度值賦值給n n = （tab = resize（））。length； // 1）透過 （n - 1） & hash 當前元素的hash值 & hash表長度 - 1 // 2）確定當前元素的儲存位置，此運算等價於 當前元素的hash值 % hash表的長度 // 3）計算出的儲存位置沒有元素存在 if （（p = tab［i = （n - 1） & hash］） == null） // 4） 則新建一個Node結點，在該位置儲存此元素 tab［i］ = newNode（hash， key， value， null）； else { // 當前儲存位置已經有元素存在了（不考慮是修改的情況的話，就代表發生hash衝突了） // 用於存放新增結點 Node e； // 用於臨時存在某個key值 K k； // 1）如果當前位置已存在元素的hash值和新增元素的hash值相等 // 2）並且key也相等，則證明是同一個key元素，想執行修改value操作 if （p。hash == hash && （（k = p。key） == key || （key ！= null && key。equals（k）））） e = p；// 將當前結點引用賦值給e else if （p instanceof TreeNode） // 如果當前結點是樹結點 // 則證明當前位置的連結串列已變成紅黑樹結構，則已紅黑樹結點結構新增元素 e = （（TreeNode）p）。putTreeVal（this， tab， hash， key， value）； else {// 排除上述情況，則證明已發生hash衝突，並hash衝突位置現時的結構是單鏈表結構 for （int binCount = 0； ； ++binCount） { //遍歷單鏈表，將新元素結點放置此連結串列的最後一位 if （（e = p。next） == null） { // 將新元素結點放在此連結串列的最後一位 p。next = newNode（hash， key， value， null）； // 新增結點後，當前結點數量是否大於等於 閾值 8 if （binCount >= TREEIFY_THRESHOLD - 1） // -1 for 1st // 大於等於8則將連結串列轉換成紅黑樹 treeifyBin（tab， hash）； break； } // 如果連結串列中已經存在對應的key，則覆蓋value if （e。hash == hash && （（k = e。key） == key || （key ！= null && key。equals（k）））） break； p = e； } } if （e ！= null） { // 已存在對應key V oldValue = e。value； if （！onlyIfAbsent || oldValue == null） //如果允許修改，則修改value為新值 e。value = value； afterNodeAccess（e）； return oldValue； } } ++modCount； // 當前儲存鍵值對的數量 大於 閾值 是則擴容 if （++size > threshold） // 重置hash大小，將舊hash表的資料逐一複製到新的hash表中（後面詳細講解） resize（）； afterNodeInsertion（evict）； // 返回null，則證明是新增操作，而不是修改操作 return null； }

呼叫

get（Object key）

操作根據鍵

key

查詢對應的

key-value

鍵值對時，進行了如下操作：

先呼叫

hash（key）

方法計算出

key

的

hash

值

根據查詢的鍵值

key

的

hash

值，透過

（n - 1） & hash

當前元素的

hash

值 &

hash

表長度 - 1（實際就是

hash

值 %

hash

表長度）計算出儲存位置

table［i］

，判斷儲存位置是否有元素存在 。

如果儲存位置有元素存放，但是頭結點元素不是要查詢的元素，則需要遍歷該位置進行查詢。

先判斷頭結點是否是

treeNode

，如果是

treeNode

則證明此位置的結構是紅黑樹，以紅色樹的方式遍歷查詢該結點，沒有則返回

null

。

如果不是紅黑樹，則證明是單鏈表。遍歷單鏈表，逐一比較連結串列結點，連結串列結點的

key

的

hash

值和要獲取的

key

的

hash

值相等，並且 連結串列結點的

key

本身和要獲取的

key

相等，則返回該結點，遍歷結束仍未找到對應

key

的結點，則返回

null

。

示例程式碼：

/** * 返回指定 key 所對映的 value 值 * 或者 返回 null 如果容器裡不存在對應的key * * 更確切地講，如果此對映包含一個滿足 （key==null ？ k==null ：key。equals（k）） * 的從 k 鍵到 v 值的對映關係， * 則此方法返回 v；否則返回 null。（最多隻能有一個這樣的對映關係。） * * 返回 null 值並不一定 表明該對映不包含該鍵的對映關係； * 也可能該對映將該鍵顯示地對映為 null。可使用containsKey操作來區分這兩種情況。 * * @see #put（Object， Object） */ public V get（Object key） { Node e； // 1。先呼叫 hash（key）方法計算出 key 的 hash值 // 2。隨後呼叫getNode方法獲取對應key所對映的value值 return （e = getNode（hash（key）， key）） == null ？ null ： e。value； } /** * 獲取雜湊表結點的方法實現 * * @param hash key 鍵的hash值 * @param key 鍵 * @return 返回對應的結點，如果結點不存在，則返回null */ final Node getNode（int hash， Object key） { // 用於記錄當前的hash表 Node［］ tab； // first用於記錄對應hash位置的第一個結點，e充當工作結點的作用 Node first， e； // n用於記錄hash表的長度 int n； // 用於臨時存放Key K k； // 透過 （n - 1） & hash 當前元素的hash值 & hash表長度 - 1 // 判斷當前元素的儲存位置是否有元素存在 if （（tab = table） ！= null && （n = tab。length） > 0 && （first = tab［（n - 1） & hash］） ！= null） {//元素存在的情況 // 如果頭結點的key的hash值 和 要獲取的key的hash值相等 // 並且 頭結點的key本身 和要獲取的 key 相等 if （first。hash == hash && // always check first node 總是檢查頭結點 （（k = first。key） == key || （key ！= null && key。equals（k）））） // 返回該位置的頭結點 return first； if （（e = first。next） ！= null） {// 頭結點不相等 if （first instanceof TreeNode） // 如果當前結點是樹結點 // 則證明當前位置的連結串列已變成紅黑樹結構 // 透過紅黑樹結點的方式獲取對應key結點 return （（TreeNode）first）。getTreeNode（hash， key）； do {// 當前位置不是紅黑樹，則證明是單鏈表 // 遍歷單鏈表，逐一比較連結串列結點 // 連結串列結點的key的hash值 和 要獲取的key的hash值相等 // 並且 連結串列結點的key本身 和要獲取的 key 相等 if （e。hash == hash && （（k = e。key） == key || （key ！= null && key。equals（k）））） // 找到對應的結點則返回 return e； } while （（e = e。next） ！= null）； } } // 透過上述查詢均無找到，則返回null return null； }

呼叫

remove（Object key）

操作根據鍵

key

刪除對應的

key-value

鍵值對時，進行了如下操作：

先呼叫

hash（key）

方法計算出

key

的

hash

值

根據查詢的鍵值

key

的

hash

值，透過

（n - 1） & hash

當前元素的

hash

值 &

hash

表長度 - 1（實際就是

hash

值 %

hash

表長度） 計算出儲存位置

table［i］

，判斷儲存位置是否有元素存在 。

如果儲存位置有元素存放，但是頭結點元素不是要刪除的元素，則需要遍歷該位置進行查詢。

先判斷頭結點是否是

treeNode

，如果是

treeNode

則證明此位置的結構是紅黑樹，以紅色樹的方式遍歷查詢並刪除該結點，沒有則返回

null

。

如果不是紅黑樹，則證明是單鏈表。遍歷單鏈表，逐一比較連結串列結點，連結串列結點的

key

的

hash

值和要獲取的

key

的

hash

值相等，並且連結串列結點的

key

本身和要獲取的

key

相等，則此為要刪除的結點，記錄此結點至變數

node

中，遍歷結束仍未找到對應

key

的結點，則返回

null

。

如果找到要刪除的結點

node

，則判斷是否需要比較

value

也是否一致，如果

value

值一致或者不需要比較

value

值，則執行刪除結點操作，刪除操作根據不同的情況與結構進行不同的處理。

如果當前結點是樹結點，則證明當前位置的連結串列已變成紅黑樹結構，透過紅黑樹結點的方式刪除對應結點。

如果不是紅黑樹，則證明是單鏈表。如果要刪除的是頭結點，則當前儲存位置

table［i］

的頭結點指向刪除結點的下一個結點。

如果要刪除的結點不是頭結點，則將要刪除的結點的後繼結點

node。next

賦值給要刪除結點的前驅結點的

next

域，即

p。next = node。next；

。

7。

HashMap

當前儲存鍵值對的數量 - 1，並返回刪除結點。

示例程式碼：

/** * 從此對映中移除指定鍵的對映關係（如果存在）。 * * @param key 其對映關係要從對映中移除的鍵 * @return 與 key 關聯的舊值；如果 key 沒有任何對映關係，則返回 null。 * （返回 null 還可能表示該對映之前將 null 與 key 關聯。） */ public V remove（Object key） { Node e； // 1。先呼叫 hash（key）方法計算出 key 的 hash值 // 2。隨後呼叫removeNode方法刪除對應key所對映的結點 return （e = removeNode（hash（key）， key， null， false， true）） == null ？ null ： e。value； } /** * 刪除雜湊表結點的方法實現 * * @param hash 鍵的hash值 * @param key 鍵 * @param value 用於比較的value值，當matchValue 是 true時才有效， 否則忽略 * @param matchValue 如果是 true 只有當value相等時才會移除 * @param movable 如果是 false當執行移除操作時，不刪除其他結點 * @return 返回刪除結點node，不存在則返回null */ final Node removeNode（int hash， Object key， Object value， boolean matchValue， boolean movable） { // 用於記錄當前的hash表 Node［］ tab； // 用於記錄當前的連結串列結點 Node p； // n用於記錄hash表的長度，index用於記錄當前操作索引index int n， index； // 透過 （n - 1） & hash 當前元素的hash值 & hash表長度 - 1 // 判斷當前元素的儲存位置是否有元素存在 if （（tab = table） ！= null && （n = tab。length） > 0 && （p = tab［index = （n - 1） & hash］） ！= null） {// 元素存在的情況 // node 用於記錄找到的結點，e為工作結點 Node node = null， e； K k； V v； // 如果頭結點的key的hash值 和 要獲取的key的hash值相等 // 並且 頭結點的key本身 和要獲取的 key 相等 // 則證明此頭結點就是要刪除的結點 if （p。hash == hash && （（k = p。key） == key || （key ！= null && key。equals（k）））） // 記錄要刪除的結點的引用地址至node中 node = p； else if （（e = p。next） ！= null） {// 頭結點不相等 if （p instanceof TreeNode）// 如果當前結點是樹結點 // 則證明當前位置的連結串列已變成紅黑樹結構 // 透過紅黑樹結點的方式獲取對應key結點 // 記錄要刪除的結點的引用地址至node中 node = （（TreeNode）p）。getTreeNode（hash， key）； else {// 當前位置不是紅黑樹，則證明是單鏈表 do { // 遍歷單鏈表，逐一比較連結串列結點 // 連結串列結點的key的hash值 和 要獲取的key的hash值相等 // 並且 連結串列結點的key本身 和要獲取的 key 相等 if （e。hash == hash && （（k = e。key） == key || （key ！= null && key。equals（k）））） { // 找到則記錄要刪除的結點的引用地址至node中，中斷遍歷 node = e； break； } p = e； } while （（e = e。next） ！= null）； } } // 如果找到要刪除的結點，則判斷是否需要比較value也是否一致 if （node ！= null && （！matchValue || （v = node。value） == value || （value ！= null && value。equals（v）））） { // value值一致或者不需要比較value值，則執行刪除結點操作 if （node instanceof TreeNode） // 如果當前結點是樹結點 // 則證明當前位置的連結串列已變成紅黑樹結構 // 透過紅黑樹結點的方式刪除對應結點 （（TreeNode）node）。removeTreeNode（this， tab， movable）； else if （node == p） // node 和 p相等，則證明刪除的是頭結點 // 當前儲存位置的頭結點指向刪除結點的下一個結點 tab［index］ = node。next； else // 刪除的不是頭結點 // p是刪除結點node的前驅結點，p的next改為記錄要刪除結點node的後繼結點 p。next = node。next； ++modCount； // 當前儲存鍵值對的數量 - 1 ——size； afterNodeRemoval（node）； // 返回刪除結點 return node； } } // 不存在要刪除的結點，則返回null return null； }

呼叫

replace（K key， V value）

操作根據鍵

key

查詢對應的

key-value

鍵值對，隨後替換對應的值

value

，進行了如下操作：

先呼叫

hash（key）

方法計算出

key

的

hash

值

隨後呼叫

getNode

方法獲取對應

key

所對映的

value

值 。

記錄元素舊值，將新值賦值給元素，返回元素舊值，如果沒有找到元素，則返回

null

。

示例程式碼：

/** * 替換指定 key 所對映的 value 值 * * @param key 對應要替換value值元素的key鍵 * @param value 要替換對應元素的新value值 * @return 返回原本的舊值，如果沒有找到key對應的元素，則返回null * @since 1。8 JDK1。8新增方法 */ public V replace（K key， V value） { Node e； // 1。先呼叫 hash（key）方法計算出 key 的 hash值 // 2。隨後呼叫getNode方法獲取對應key所對映的value值 if （（e = getNode（hash（key）， key）） ！= null） {// 如果找到對應的元素 // 元素舊值 V oldValue = e。value； // 將新值賦值給元素 e。value = value； afterNodeAccess（e）； // 返回元素舊值 return oldValue； } // 沒有找到元素，則返回null return null； }

3。

問 1：您上面說，存放一個元素時，先計算它的hash值確定它的儲存位置，然後再把這個元素放到對應的位置上，那萬一這個位置上面已經有元素存在呢，新增的這個元素怎麼辦？

問 2：

hash

衝突（或者叫

hash

碰撞）是什麼？為什麼會出現這種現象，如何解決

hash

衝突？

答：

hash衝突： 當我們呼叫

put（K key， V value）

操作新增

key-value

鍵值對，這個

key-value

鍵值對存放在的位置是透過擾動函式

（key == null） ？ 0 ： （h = key。hashCode（）） ^ （h >>> 16）

計算鍵

key

的

hash

值。隨後將這個

hash

值%模上雜湊表

Node［］ table

的長度得到具體的存放位置。所以

put（K key， V value）

多個元素，是有可能計算出相同的存放位置。此現象就是

hash

衝突或者叫

hash

碰撞。

例子如下：

元素A的

hash

值為 9，元素B的

hash

值為17。雜湊表

Node［］ table

的長度為8。則元素 A 的存放位置為

9 % 8 = 1

，元素 B 的存放位置為

17 % 8 = 1

。兩個元素的存放位置均為

table［1］

，發生了

hash

衝突。

hash

衝突的避免：既然會發生

hash

衝突，我們就應該想辦法避免此現象的發生，解決這個問題最關鍵就是如果生成元素的

hash

值。Java是使用“擾動函式”生成元素的

hash

值。

示例程式碼：

/** * JDK 7 的 hash方法 */ final int hash（int h） { h ^= k。hashCode（）； h ^= （h >>> 20） ^ （h >>> 12）； return h ^ （h >>> 7） ^ （h >>> 4）； } /** * JDK 8 的 hash方法 */ static final int hash（Object key） { int h； return （key == null） ？ 0 ： （h = key。hashCode（）） ^ （h >>> 16）； }

Java7做了4次16位右位移異或混合，Java 8中這步已經簡化了，只做一次16位右位移異或混合，而不是四次，但原理是不變的。例子如下：

擾動函式執行例子

右位移16位，正好是32bit的一半，自己的高半區和低半區做異或，就是為了混合原始雜湊碼的高位和低位，以此來加大低位的隨機性。而且混合後的低位摻雜了高位的部分特徵，這樣高位的資訊也被變相保留下來。

上述擾動函式的解釋參考自：JDK 原始碼中 HashMap 的 hash 方法原理是什麼？

hash衝突解決：解決

hash

衝突的方法有很多，常見的有：開發定址法，再雜湊法，鏈地址法，公共溢位區法（詳細說明請檢視我的文章JAVA基礎-自問自答學hashCode和equals）。

HashMap

是使用鏈地址法解決

hash

衝突的，當有衝突元素放進來時，會將此元素插入至此位置連結串列的最後一位，形成單鏈表。但是由於是單鏈表的緣故，每當透過

hash % length

找到該位置的元素時，均需要從頭遍歷連結串列，透過逐一比較

hash

值，找到對應元素。如果此位置元素過多，造成連結串列過長，遍歷時間會大大增加，最壞情況下的時間複雜度為

O（N）

，造成查詢效率過低。所以當存在位置的連結串列長度 大於等於 8 時，

HashMap

會將連結串列 轉變為 紅黑樹，紅黑樹最壞情況下的時間複雜度為

O（logn）

。以此提高查詢效率。

4。

問：

HashMap

的容量為什麼一定要是2的n次方？

答：

因為呼叫

put（K key， V value）

操作新增

key-value

鍵值對時，具體確定此元素的位置是透過

hash

值%模上雜湊表

Node［］ table

的長度

hash % length

計算的。但是“模”運算的消耗相對較大，透過位運算

h & （length-1）

也可以得到取模後的存放位置，而位運算的執行效率高，但只有

length

的長度是2的n次方時，

h & （length-1）

才等價於

h % length

。

而且當陣列長度為2的n次冪的時候，不同的key算出的index相同的機率較小，那麼資料在陣列上分佈就比較均勻，也就是說碰撞的機率小，相對的，查詢的時候就不用遍歷某個位置上的連結串列，這樣查詢效率也就較高了。

例子：

hash & （length-1）運算過程

上圖中，左邊兩組的陣列長度是16（2的4次方），右邊兩組的陣列長度是15。兩組的

hash

值均為8和9。

當陣列長度是15時，當它們和

1110

進行

&

與運算（相同為1，不同為0）時，計算的結果都是

1000

，所以他們都會存放在相同的位置

table［8］

中，這樣就發生了

hash

衝突，那麼查詢時就要遍歷連結串列，逐一比較

hash

值，降低了查詢的效率。

同時，我們可以發現，當陣列長度為15的時候，

hash

值均會與

14（1110）

進行

&

與運算，那麼最後一位永遠是0，而

0001

，

0011

，

0101

，

1001

，

1011

，

0111

，

1101

這幾個位置永遠都不能存放元素了，空間浪費相當大，更糟的是這種情況中，陣列可以使用的位置比陣列長度小了很多，這意味著進一步增加了碰撞的機率，減慢了查詢的效率。

所以，

HashMap

的容量是2的n次方，有利於提高計算元素存放位置時的效率，也降低了

hash

衝突的機率。因此，我們使用

HashMap

儲存大量資料的時候，最好先預先指定容器的大小為2的n次方，即使我們不指定為2的n次方，

HashMap

也會把容器的大小設定成最接近設定數的2的n次方，如，設定

HashMap

的大小為 7 ，則

HashMap

會將容器大小設定成最接近7的一個2的n次方數，此值為 8 。

示例程式碼：

/** * 返回一個比指定數cap大的，並且大小是2的n次方的數 * Returns a power of two size for the given target capacity。 */ static final int tableSizeFor（int cap） { int n = cap - 1； n |= n >>> 1； n |= n >>> 2； n |= n >>> 4； n |= n >>> 8； n |= n >>> 16； return （n < 0） ？ 1 ： （n >= MAXIMUM_CAPACITY） ？ MAXIMUM_CAPACITY ： n + 1； }

5。

問：

HashMap

的負載因子是什麼，有什麼作用？

答：負載因子表示雜湊表空間的使用程度（或者說是雜湊表空間的利用率）。

例子如下：

底層雜湊表

Node［］ table

的容量大小

capacity

為16，負載因子

load factor

為0。75，則當儲存的元素個數

size = capacity 16 * load factor 0。75

等於 12 時，則會觸發

HashMap

的擴容機制，呼叫

resize（）

方法進行擴容。

當負載因子越大，則

HashMap

的裝載程度就越高。也就是能容納更多的元素，元素多了，發生

hash

碰撞的機率就會加大，從而連結串列就會拉長，此時的查詢效率就會降低。

當負載因子越小，則連結串列中的資料量就越稀疏，此時會對空間造成浪費，但是此時查詢效率高。

我們可以在建立

HashMap

時根據實際需要適當地調整

load factor

的值；如果程式比較關心空間開銷、記憶體比較緊張，可以適當地增加負載因子；如果程式比較關心時間開銷，記憶體比較寬裕則可以適當的減少負載因子。通常情況下，預設負載因子 （0。75） 在時間和空間成本上尋求一種折衷，程式設計師無需改變負載因子的值。

因此，如果我們在初始化

HashMap

時，就預估知道需要裝載

key-value

鍵值對的容量

size

，我們可以透過

size / load factor

計算出我們需要初始化的容量大小

initialCapacity

，這樣就可以避免

HashMap

因為存放的元素達到閾值

threshold

而頻繁呼叫

resize（）

方法進行擴容。從而保證了較好的效能。

6。

問：您能說說

HashMap

和

HashTable

的區別嗎？

答：

HashMap

和

HashTable

有如下區別：

1）容器整體結構：

2） 容量設定與擴容機制：

3） 雜湊分佈方式（計算儲存位置）：

HashMap是先將

key

鍵的

hashCode

經過擾動函式擾動後得到

hash

值，然後再利用

hash & （length - 1）

的方式代替取模，得到元素的儲存位置。

Hashtable

則是除留餘數法進行計算儲存位置的（因為其預設容量也不是2的n次方。所以也無法用位運算替代模運算），

int index = （hash & 0x7FFFFFFF） % tab。length；

。

由於

HashMap

的容器容量一定是2的n次方，所以能使用

hash & （length - 1）

的方式代替取模的方式計算元素的位置提高運算效率，但

Hashtable

的容器容量不一定是2的n次方，所以不能使用此運算方式代替。

4）執行緒安全（最重要）：

HashMap不是執行緒安全，如果想執行緒安全，可以透過呼叫

synchronizedMap（Map m）

使其執行緒安全。但是使用時的執行效率會下降，所以建議使用

ConcurrentHashMap

容器以此達到執行緒安全。

Hashtable

則是執行緒安全的，每個操作方法前都有

synchronized

修飾使其同步，但執行效率也不高，所以還是建議使用容器以此達到執行緒安全。

因此，

Hashtable

是一個遺留容器，如果我們不需要執行緒同步，則建議使用

HashMap

，如果需要執行緒同步，則建議使用

ConcurrentHashMap

。

7。

問：您說

HashMap

不是執行緒安全的，那如果多執行緒下，它是如何處理的？並且什麼情況下會發生執行緒不安全的情況？

答：

HashMap不是執行緒安全的，如果多個執行緒同時對同一個

HashMap

更改資料的話，會導致資料不一致或者資料汙染。如果出現執行緒不安全的操作時，

HashMap

會盡可能的丟擲

ConcurrentModificationException

防止資料異常，當我們在對一個

HashMap

進行遍歷時，在遍歷期間，我們是不能對

HashMap

進行新增，刪除等更改資料的操作的，否則也會丟擲

ConcurrentModificationException

異常，此為fail-fast（快速失敗）機制。從原始碼上分析，我們在

put，remove

等更改

HashMap

資料時，都會導致modCount的改變，當

expectedModCount ！= modCount

時，則丟擲

ConcurrentModificationException

。如果想要執行緒安全，可以考慮使用

ConcurrentHashMap

。

而且，在多執行緒下操作

HashMap

，由於存在擴容機制，當

HashMap

呼叫

resize（）

進行自動擴容時，可能會導致死迴圈的發生。限於篇幅，我暫不帶著大家一起去分析

resize（）

方法導致死迴圈發生的現象造成原因了，遲點有空我會再補充上去，請見諒，大家可以參考如下文章：

8。

問：我們在使用

HashMap

時，選取什麼物件作為

key

鍵比較好，為什麼？

答：

可變物件：指建立後自身狀態能改變的物件。換句話說，可變物件是該物件在建立後它的雜湊值可能被改變。

我們在使用

HashMap

時，最好選擇不可變物件作為

key

。例如

String

，

Integer

等不可變型別作為

key

是非常明智的。如果

key

物件是可變的，那麼

key

的雜湊值就可能改變。在

HashMap

中可變物件作為Key會造成資料丟失。因為我們再進行

hash & （length - 1）

取模運算計算位置查詢對應元素時，位置可能已經發生改變，導致資料丟失。

總結

HashMap是基於

Map

介面實現的一種鍵-值對

的儲存結構，允許

null

值，同時非有序，非同步（即執行緒不安全）。

HashMap

的底層實現是陣列 + 連結串列 + 紅黑樹（JDK1。8增加了紅黑樹部分）。

HashMap

定位元素位置是透過鍵

key

經過擾動函式擾動後得到

hash

值，然後再透過

hash & （length - 1）

代替取模的方式進行元素定位的。

HashMap

是使用鏈地址法解決

hash

衝突的，當有衝突元素放進來時，會將此元素插入至此位置連結串列的最後一位，形成單鏈表。當存在位置的連結串列長度 大於等於 8 時，

HashMap

會將連結串列 轉變為 紅黑樹，以此提高查詢效率。

HashMap

的容量是2的n次方，有利於提高計算元素存放位置時的效率，也降低了

hash

衝突的機率。因此，我們使用

HashMap

。儲存大量資料的時候，最好先預先指定容器的大小為2的n次方，即使我們不指定為2的n次方，

HashMap

也會把容器的大小設定成最接近設定數的2的n次方，如，設定

HashMap

的大小為 7 ，則

HashMap

會將容器大小設定成最接近7的一個2的n次方數，此值為 8 。

HashMap

的負載因子表示雜湊表空間的使用程度（或者說是雜湊表空間的利用率）。當負載因子越大，則

HashMap

的裝載程度就越高。也就是能容納更多的元素，元素多了，發生

hash

碰撞的機率就會加大，從而連結串列就會拉長，此時的查詢效率就會降低。當負載因子越小，則連結串列中的資料量就越稀疏，此時會對空間造成浪費，但是此時查詢效率高。

HashMap

不是執行緒安全的，

Hashtable

則是執行緒安全的。但

Hashtable

是一個遺留容器，如果我們不需要執行緒同步，則建議使用

HashMap

，如果需要執行緒同步，則建議使用

ConcurrentHashMap

。

在多執行緒下操作

HashMap

，由於存在擴容機制，當

HashMap

呼叫

resize（）

進行自動擴容時，可能會導致死迴圈的發生。

我們在使用

HashMap

時，最好選擇不可變物件作為

key

。例如

String

，

Integer

等不可變型別作為

key

是非常明智的。

由於最近工作較忙，也有拖延症發作的問題，所以文章遲遲未能完成釋出，現時完成的文章其實對我而言，也不算太好，但還是打算先發出來讓大家看看，一起學習學習，看有什麼不好的地方，我再慢慢改進，如果此文對你有幫助，請給個贊，謝謝大家。