當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

看完这篇 HashMap ，和面试官扯皮就没问题了

發布時間：2024/8/23 编程问答 44 豆豆

生活随笔收集整理的這篇文章主要介紹了看完这篇 HashMap ，和面试官扯皮就没问题了小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

來源 | Java?建設者

責編 | Carol

封圖 | CSDN 下載自視覺中國

（如果你沒有時間細摳本文，可以直接看 HashMap 概述，能讓你對 HashMap 有個大致的了解）

HashMap 是 Map 接口的實現，HashMap 允許空的 key-value 鍵值對，HashMap 被認為是 Hashtable 的增強版，HashMap 是一個非線程安全的容器，如果想構造線程安全的 Map 考慮使用 ConcurrentHashMap。HashMap 是無序的，因為 HashMap 無法保證內部存儲的鍵值對的有序性。

HashMap 的底層數據結構是數組 + 鏈表的集合體，數組在 HashMap 中又被稱為桶(bucket)。遍歷 HashMap 需要的時間損耗為 HashMap 實例桶的數量 + (key - value 映射) 的數量。因此，如果遍歷元素很重要的話，不要把初始容量設置的太高或者負載因子設置的太低。

HashMap 實例有兩個很重要的因素，初始容量和負載因子，初始容量指的就是 hash 表桶的數量，負載因子是一種衡量哈希表填充程度的標準，當哈希表中存在足夠數量的 entry，以至于超過了負載因子和當前容量，這個哈希表會進行 rehash 操作，內部的數據結構重新 rebuilt。

注意 HashMap 不是線程安全的，如果多個線程同時影響了 HashMap ，并且至少一個線程修改了 HashMap 的結構，那么必須對 HashMap 進行同步操作。可以使用?Collections.synchronizedMap(new HashMap)?來創建一個線程安全的 Map。

HashMap 會導致除了迭代器本身的 remove 外，外部 remove 方法都可能會導致 fail-fast 機制，因此盡量要用迭代器自己的 remove 方法。如果在迭代器創建的過程中修改了 map 的結構，就會拋出?ConcurrentModificationException?異常。

下面就來聊一聊 HashMap 的細節問題。我們還是從面試題入手來分析 HashMap 。

HashMap 和 HashTable 的區別

我們上面介紹了一下 HashMap ，現在來介紹一下 HashTable。

相同點

HashMap 和 HashTable 都是基于哈希表實現的，其內部每個元素都是?key-value?鍵值對，HashMap 和 HashTable 都實現了 Map、Cloneable、Serializable 接口。

不同點

父類不同：HashMap 繼承了?AbstractMap?類，而 HashTable 繼承了?Dictionary?類

空值不同：HashMap 允許空的 key 和 value 值，HashTable 不允許空的 key 和 value 值。HashMap 會把 Null key 當做普通的 key 對待。不允許 null key 重復。

線程安全性：HashMap 不是線程安全的，如果多個外部操作同時修改 HashMap 的數據結構比如 add 或者是 delete，必須進行同步操作，僅僅對 key 或者 value 的修改不是改變數據結構的操作。可以選擇構造線程安全的 Map 比如?Collections.synchronizedMap?或者是?ConcurrentHashMap。而 HashTable 本身就是線程安全的容器。
性能方面：雖然 HashMap 和 HashTable 都是基于單鏈表的，但是 HashMap 進行 put 或者 get???? 操作，可以達到常數時間的性能；而 HashTable 的 put 和 get 操作都是加了?synchronized?鎖的，所以效率很差。

初始容量不同：HashTable 的初始長度是11，之后每次擴充容量變為之前的 2n+1（n為上一次的長度）
而 HashMap 的初始長度為16，之后每次擴充變為原來的兩倍。創建時，如果給定了容量初始值，那么HashTable 會直接使用你給定的大小，而 HashMap 會將其擴充為2的冪次方大小。

HashMap 和 HashSet 的區別

也經常會問到 HashMap 和 HashSet 的區別

HashSet 繼承于 AbstractSet 接口，實現了 Set、Cloneable,、java.io.Serializable 接口。HashSet 不允許集合中出現重復的值。HashSet 底層其實就是 HashMap，所有對 HashSet 的操作其實就是對 HashMap 的操作。所以 HashSet 也不保證集合的順序。

HashMap 底層結構

要了解一個類，先要了解這個類的結構，先來看一下 HashMap 的結構：

最主要的三個類(接口)就是?HashMap,AbstractMap和?Map?了，HashMap 我們上面已經在概述中簡單介紹了一下，下面來介紹一下 AbstractMap。

AbstractMap 類

這個抽象類是 Map 接口的骨干實現，以求最大化的減少實現類的工作量。為了實現不可修改的 map，程序員僅需要繼承這個類并且提供 entrySet 方法的實現即可。它將會返回一組 map 映射的某一段。通常，返回的集合將在AbstractSet 之上實現。這個set不應該支持 add 或者 remove 方法，并且它的迭代器也不支持 remove 方法。

為了實現可修改的 map，程序員必須額外重寫這個類的 put 方法(否則就會拋出UnsupportedOperationException)，并且 entrySet.iterator() 返回的 iterator 必須實現 remove() 方法。

Map 接口

Map 接口定義了 key-value 鍵值對的標準。一個對象支持 key-value 存儲。Map不能包含重復的 key，每個鍵最多映射一個值。這個接口代替了Dictionary 類，Dictionary是一個抽象類而不是接口。

Map 接口提供了三個集合的構造器，它允許將 map 的內容視為一組鍵，值集合或一組鍵值映射。map的順序定義為map映射集合上的迭代器返回其元素的順序。一些map實現，像是TreeMap類，保證了map的有序性；其他的實現，像是HashMap，則沒有保證。

重要內部類和接口

Node 接口

Node節點是用來存儲HashMap的一個個實例，它實現了?Map.Entry接口，我們先來看一下 Map中的內部接口 Entry 接口的定義

Map.Entry

//?一個map?的entry?鏈，這個Map.entrySet()方法返回一個集合的視圖，包含類中的元素， //?這個唯一的方式是從集合的視圖進行迭代，獲取一個map的entry鏈。這些Map.Entry鏈只在 //?迭代期間有效。 interface?Entry<K,V>?{K?getKey();V?getValue();V?setValue(V?value);boolean?equals(Object?o);int?hashCode(); }

Node 節點會存儲四個屬性，hash值，key，value，指向下一個Node節點的引用

?//?hash值 final?int?hash; //?鍵 final?K?key; //?值 V?value; //?指向下一個Node節點的Node類型 Node<K,V>?next;

因為Map.Entry 是一條條entry 鏈連接在一起的，所以Node節點也是一條條entry鏈。構造一個新的HashMap實例的時候，會把這四個屬性值分為傳入

Node(int?hash,?K?key,?V?value,?Node<K,V>?next)?{this.hash?=?hash;this.key?=?key;this.value?=?value;this.next?=?next; }

實現了 Map.Entry 接口所以必須實現其中的方法，所以 Node 節點中也包括上面的五個方法

KeySet 內部類

keySet 類繼承于 AbstractSet 抽象類，它是由 HashMap 中的?keyset()?方法來創建 KeySet 實例的，旨在對HashMap 中的key鍵進行操作，看一個代碼示例

圖中把「1, 2, 3」這三個key 放在了HashMap中，然后使用 lambda 表達式循環遍歷 key 值，可以看到，map.keySet() 其實是返回了一個 Set 接口，KeySet() 是在 Map 接口中進行定義的，不過是被HashMap 進行了實現操作，來看一下源碼就明白了

//?返回一個set視圖，這個視圖中包含了map中的key。 public?Set<K>?keySet()?{//?//?keySet?指向的是?AbstractMap?中的?keysetSet<K>?ks?=?keySet;if?(ks?==?null)?{//?如果?ks?為空，就創建一個?KeySet?對象//?并對 ks 賦值。ks?=?new?KeySet();keySet?=?ks;}return?ks; }

所以 KeySet 類中都是對 Map中的 Key 進行操作的：

Values 內部類

Values 類的創建其實是和 KeySet 類很相似，不過 KeySet 旨在對 Map中的鍵進行操作，Values 旨在對key-value?鍵值對中的 value 值進行使用，看一下代碼示例：

循環遍歷 Map中的 values值，看一下 values() 方法最終創建的是什么：

public?Collection<V>?values()?{//?values?其實是?AbstractMap?中的?valuesCollection<V>?vs?=?values;if?(vs?==?null)?{vs?=?new?Values();values?=?vs;}return?vs; }

所有的 values 其實都存儲在 AbstractMap 中，而 Values 類其實也是實現了 Map 中的 Values 接口，看一下對 values 的操作都有哪些方法

其實是和 key 的操作差不多

EntrySet 內部類

上面提到了HashMap中分別有對 key、value 進行操作的，其實還有對?key-value?鍵值對進行操作的內部類，它就是 EntrySet，來看一下EntrySet 的創建過程：

點進去 entrySet() 會發現這個方法也是在 Map 接口中定義的，HashMap對它進行了重寫

//?返回一個?set?視圖，此視圖包含了?map?中的key-value?鍵值對 public?Set<Map.Entry<K,V>>?entrySet()?{Set<Map.Entry<K,V>>?es;return?(es?=?entrySet)?==?null???(entrySet?=?new?EntrySet())?:?es; }

如果 es 為空創建一個新的 EntrySet 實例，EntrySet 主要包括了對key-value 鍵值對映射的方法，如下

HashMap 1.7 的底層結構

JDK1.7 中，HashMap 采用位桶 + 鏈表的實現，即使用鏈表來處理沖突，同一 hash 值的鏈表都存儲在一個數組中。但是當位于一個桶中的元素較多，即 hash 值相等的元素較多時，通過 key 值依次查找的效率較低。它的數據結構如下

HashMap 大致結構

HashMap 底層數據結構就是一個 Entry 數組，Entry 是 HashMap 的基本組成單元，每個 Entry 中包含一個 key-value 鍵值對。

transient?Entry<K,V>[]?table?=?(Entry<K,V>[])?EMPTY_TABLE;

而每個 Entry 中包含?「hash, key ,value」?屬性，它是 HashMap 的一個內部類

static?class?Entry<K,V>?implements?Map.Entry<K,V>?{final?K?key;V?value;Entry<K,V>?next;int?hash;Entry(int?h,?K?k,?V?v,?Entry<K,V>?n)?{value?=?v;next?=?n;key?=?k;hash?=?h;}... }

所以，HashMap 的整體結構就像下面這樣

HashMap 1.8 的底層結構

與 JDK 1.7 相比，1.8 在底層結構方面做了一些改變，當每個桶中元素大于 8 的時候，會轉變為紅黑樹，目的就是優化查詢效率，JDK 1.8 重寫了?resize()?方法。

HashMap 重要屬性

「初始容量」

HashMap 的默認初始容量是由?DEFAULT_INITIAL_CAPACITY?屬性管理的。

static?final?int?DEFAULT_INITIAL_CAPACITY?=?1?<<?4;

HashMap 的默認初始容量是 1 << 4 = 16， << 是一個左移操作，它相當于是

「最大容量」

HashMap 的最大容量是

static?final?int?MAXIMUM_CAPACITY?=?1?<<?30;

這里是不是有個疑問？int 占用四個字節，按說最大容量應該是左移 31 位，為什么 HashMap 最大容量是左移 30 位呢？因為在數值計算中，最高位也就是最左位的位?是代表著符號為，0 -> 正數，1 -> 負數，容量不可能是負數，所以 HashMap 最高位只能移位到 2 ^ 30 次冪。

「默認負載因子」

HashMap 的默認負載因子是

static?final?float?DEFAULT_LOAD_FACTOR?=?0.75f;

float 類型所以用?.f?為單位，負載因子是和擴容機制有關，這里大致提一下，后面會細說。擴容機制的原則是當 HashMap 中存儲的數量 > HashMap 容量 * 負載因子時，就會把 HashMap 的容量擴大為原來的二倍。

HashMap 的第一次擴容就在 DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR = 12 時進行。

「樹化閾值」

HashMap 的樹化閾值是

static?final?int?TREEIFY_THRESHOLD?=?8;

在進行添加元素時，當一個桶中存儲元素的數量 > 8 時，會自動轉換為紅黑樹（JDK1.8 特性）。

「鏈表閾值」

HashMap 的鏈表閾值是

static?final?int?UNTREEIFY_THRESHOLD?=?6;

在進行刪除元素時，如果一個桶中存儲元素數量 < 6 后，會自動轉換為鏈表

「擴容臨界值」

static?final?int?MIN_TREEIFY_CAPACITY?=?64;

這個值表示的是當桶數組容量小于該值時，優先進行擴容，而不是樹化

「節點數組」

HashMap 中的節點數組就是 Entry 數組，它代表的就是 HashMap 中?「數組 + 鏈表」?數據結構中的數組。

transient?Node<K,V>[]?table;

Node 數組在第一次使用的時候進行初始化操作，在必要的時候進行?resize，resize 后數組的長度擴容為原來的二倍。

「鍵值對數量」

在 HashMap 中，使用?size?來表示 HashMap 中鍵值對的數量。

「修改次數」

在 HashMap 中，使用?modCount?來表示修改次數，主要用于做并發修改 HashMap 時的快速失敗 - fail-fast 機制。

「擴容閾值」

在 HashMap 中，使用?threshold?表示擴容的閾值，也就是初始容量 * 負載因子的值。

threshold 涉及到一個擴容的閾值問題，這個問題是由?tableSizeFor?源碼解決的。我們先看一下它的源碼再來解釋

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

代碼中涉及一個運算符?|=?，它表示的是按位或，啥意思呢？你一定知道?「a+=b 的意思是 a=a+b」，那么同理：a |= b 就是 a = a | b，也就是雙方都轉換為二進制，來進行與操作。如下圖所示

我們上面采用了一個比較大的數字進行擴容，由上圖可知 2^29 次方的數組經過一系列的或操作后，會算出來結果是 2^30 次方。

所以擴容后的數組長度是原來的 2 倍。

「負載因子」

loadFactor?表示負載因子，它表示的是 HashMap 中的密集程度。

HashMap 構造函數

在 HashMap 源碼中，有四種構造函數，分別來介紹一下

帶有初始容量 initialCapacity?和?負載因子 loadFactor?的構造函數

public?HashMap(int?initialCapacity,?float?loadFactor)?{if?(initialCapacity?<?0)throw?new?IllegalArgumentException("Illegal?initial?capacity:?"?+initialCapacity);if?(initialCapacity?>?MAXIMUM_CAPACITY)initialCapacity?=?MAXIMUM_CAPACITY;if?(loadFactor?<=?0?||?Float.isNaN(loadFactor))throw?new?IllegalArgumentException("Illegal?load?factor:?"?+loadFactor);this.loadFactor?=?loadFactor;//?擴容的閾值this.threshold?=?tableSizeFor(initialCapacity); }

初始容量不能為負，所以當傳遞初始容量 < 0 的時候，會直接拋出?IllegalArgumentException?異常。如果傳遞進來的初始容量 > 最大容量時，初始容量 = 最大容量。負載因子也不能小于 0 。然后進行數組的擴容，這個擴容機制也非常重要，我們后面進行探討

只帶有 initialCapacity 的構造函數

public?HashMap(int?initialCapacity)?{this(initialCapacity,?DEFAULT_LOAD_FACTOR); }

最終也會調用到上面的構造函數，不過這個默認的負載因子就是 HashMap 的默認負載因子也就是?0.75f

無參數的構造函數

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

默認的負載因子也就是 0.75f

帶有 map 的構造函數

public?HashMap(Map<??extends?K,???extends?V>?m)?{this.loadFactor?=?DEFAULT_LOAD_FACTOR;putMapEntries(m,?false); }

帶有 Map 的構造函數，會直接把外部元素批量放入 HashMap 中。

講一講 HashMap put 的全過程

我記得剛畢業一年去北京面試，一家公司問我 HashMap put 過程的時候，我支支吾吾答不上來，后面痛下決心好好整。以 JDK 1.8 為基準進行分析，后面也是。先貼出整段代碼，后面會逐行進行分析。

final?V?putVal(int?hash,?K?key,?V?value,?boolean?onlyIfAbsent,boolean?evict)?{Node<K,V>[]?tab;?Node<K,V>?p;?int?n,?i;//?如果table?為null?或者沒有為?table?分配內存，就resize一次if?((tab?=?table)?==?null?||?(n?=?tab.length)?==?0)n?=?(tab?=?resize()).length;//?指定hash值節點為空則直接插入，這個(n?-?1)?&?hash才是表中真正的哈希if?((p?=?tab[i?=?(n?-?1)?&?hash])?==?null)tab[i]?=?newNode(hash,?key,?value,?null);//?如果不為空else?{Node<K,V>?e;?K?k;//?計算表中的這個真正的哈希值與要插入的key.hash相比if?(p.hash?==?hash?&&((k?=?p.key)?==?key?||?(key?!=?null?&&?key.equals(k))))e?=?p;//?若不同的話，并且當前節點已經在?TreeNode?上了else?if?(p?instanceof?TreeNode)//?采用紅黑樹存儲方式e?=?((TreeNode<K,V>)p).putTreeVal(this,?tab,?hash,?key,?value);//?key.hash?不同并且也不再?TreeNode?上，在鏈表上找到?p.next==nullelse?{for?(int?binCount?=?0;?;?++binCount)?{if?((e?=?p.next)?==?null)?{//?在表尾插入p.next?=?newNode(hash,?key,?value,?null);//?新增節點后如果節點個數到達閾值，則進入?treeifyBin()?進行再次判斷if?(binCount?>=?TREEIFY_THRESHOLD?-?1)?//?-1?for?1sttreeifyBin(tab,?hash);break;}//?如果找到了同?hash、key?的節點，那么直接退出循環if?(e.hash?==?hash?&&((k?=?e.key)?==?key?||?(key?!=?null?&&?key.equals(k))))break;//?更新?p?指向下一節點p?=?e;}}//?map中含有舊值，返回舊值if?(e?!=?null)?{?//?existing?mapping?for?keyV?oldValue?=?e.value;if?(!onlyIfAbsent?||?oldValue?==?null)e.value?=?value;afterNodeAccess(e);return?oldValue;}}//?map調整次數?+?1++modCount;//?鍵值對的數量達到閾值，需要擴容if?(++size?>?threshold)resize();afterNodeInsertion(evict);return?null; }

首先看一下?putVal?方法，這個方法是 final 的，如果你自已定義 HashMap 繼承的話，是不允許你自己重寫 put 方法的，然后這個方法涉及五個參數

hash -> put 放在桶中的位置，在 put 之前，會進行 hash 函數的計算。
key -> 參數的 key 值
value -> 參數的 value 值
onlyIfAbsent -> 是否改變已經存在的值，也就是是否進行 value 值的替換標志
evict -> 是否是剛創建 HashMap 的標志

在調用到 putVal 方法時，首先會進行 hash 函數計算應該插入的位置

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

哈希函數的源碼如下

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

首先先來理解一下 hash 函數的計算規則

Hash 函數

hash 函數會根據你傳遞的 key 值進行計算，首先計算 key 的?hashCode?值，然后再對 hashcode 進行無符號右移操作，最后再和 hashCode 進行異或 ^?操作。

>>>: 無符號右移操作，它指的是?「無符號右移，也叫邏輯右移，即若該數為正，則高位補0，而若該數為負數，則右移后高位同樣補0」?，也就是不管是正數還是負數，右移都會在空缺位補 0 。

在得到 hash 值后，就會進行 put 過程。

首先會判斷 HashMap 中的 Node 數組是否為 null，如果第一次創建 HashMap 并進行第一次插入元素，首先會進行數組的 resize，也就是重新分配，這里還涉及到一個?resize()?擴容機制源碼分析，我們后面會介紹。擴容完畢后，會計算出 HashMap 的存放位置，通過使用?「( n - 1 ) & hash」?進行計算得出。

然后會把這個位置作為數組的下標作為存放元素的位置。如果不為空，那么計算表中的這個真正的哈希值與要插入的 key.hash 相比。如果哈希值相同，key-value 不一樣，再判斷是否是樹的實例，如果是的話，那么就把它插入到樹上。如果不是，就執行尾插法在 entry 鏈尾進行插入。

會根據桶中元素的數量判斷是鏈表還是紅黑樹。然后判斷鍵值對數量是否大于閾值，大于的話則進行擴容。

擴容機制

在 Java 中，數組的長度是固定的，這意味著數組只能存儲固定量的數據。但在開發的過程中，很多時候我們無法知道該建多大的數組合適。好在 HashMap 是一種自動擴容的數據結構，在這種基于變長的數據結構中，擴容機制是非常重要的。

在 HashMap 中，閾值大小為桶數組長度與負載因子的乘積。當 HashMap 中的鍵值對數量超過閾值時，進行擴容。HashMap 中的擴容機制是由?resize()?方法來實現的，下面我們就來一次認識下。（貼出中文注釋，便于復制）

final?Node<K,V>[]?resize()?{Node<K,V>[]?oldTab?=?table;//?存儲old?table?的大小int?oldCap?=?(oldTab?==?null)???0?:?oldTab.length;//?存儲擴容閾值int?oldThr?=?threshold;int?newCap,?newThr?=?0;if?(oldCap?>?0)?{//?如果old?table數據已達最大，那么threshold也被設置成最大if?(oldCap?>=?MAXIMUM_CAPACITY)?{threshold?=?Integer.MAX_VALUE;return?oldTab;}//?左移擴大二倍,else?if?((newCap?=?oldCap?<<?1)?<?MAXIMUM_CAPACITY?&&oldCap?>=?DEFAULT_INITIAL_CAPACITY)//?擴容成原來二倍newThr?=?oldThr?<<?1;?//?double?threshold}//?如果oldThr???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????!>?0else?if?(oldThr?>?0)?//?initial?capacity?was?placed?in?thresholdnewCap?=?oldThr;//?如果old?table?<=?0?并且?存儲的閾值?<=?0else?{???????????????//?zero?initial?threshold?signifies?using?defaultsnewCap?=?DEFAULT_INITIAL_CAPACITY;newThr?=?(int)(DEFAULT_LOAD_FACTOR?*?DEFAULT_INITIAL_CAPACITY);}//?如果擴充閾值為0if?(newThr?==?0)?{//?擴容閾值為?初始容量*負載因子float?ft?=?(float)newCap?*?loadFactor;newThr?=?(newCap?<?MAXIMUM_CAPACITY?&&?ft?<?(float)MAXIMUM_CAPACITY??(int)ft?:?Integer.MAX_VALUE);}//?重新給負載因子賦值threshold?=?newThr;//?獲取擴容后的數組@SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[]?newTab?=?(Node<K,V>[])new?Node[newCap];table?=?newTab;//?如果第一次進行table?初始化不會走下面的代碼//?擴容之后需要重新把節點放在新擴容的數組中if?(oldTab?!=?null)?{for?(int?j?=?0;?j?<?oldCap;?++j)?{Node<K,V>?e;if?((e?=?oldTab[j])?!=?null)?{oldTab[j]?=?null;if?(e.next?==?null)newTab[e.hash?&?(newCap?-?1)]?=?e;else?if?(e?instanceof?TreeNode)//?重新映射時，需要對紅黑樹進行拆分((TreeNode<K,V>)e).split(this,?newTab,?j,?oldCap);else?{?//?preserve?orderNode<K,V>?loHead?=?null,?loTail?=?null;Node<K,V>?hiHead?=?null,?hiTail?=?null;Node<K,V>?next;//?遍歷鏈表，并將鏈表節點按原順序進行分組do?{next?=?e.next;if?((e.hash?&?oldCap)?==?0)?{if?(loTail?==?null)loHead?=?e;elseloTail.next?=?e;loTail?=?e;}else?{if?(hiTail?==?null)hiHead?=?e;elsehiTail.next?=?e;hiTail?=?e;}}?while?((e?=?next)?!=?null);//?將分組后的鏈表映射到新桶中if?(loTail?!=?null)?{loTail.next?=?null;newTab[j]?=?loHead;}if?(hiTail?!=?null)?{hiTail.next?=?null;newTab[j?+?oldCap]?=?hiHead;}}}}}return?newTab; }

擴容機制源碼比較長，我們耐心點進行拆分

我們以 if...else if...else 邏輯進行拆分，上面代碼主要做了這幾個事情

判斷 HashMap 中的數組的長度，也就是?(Node<K,V>[])oldTab.length()?，再判斷數組的長度是否比最大的的長度也就是 2^30 次冪要大，大的話直接取最大長度，否則利用位運算?<<擴容為原來的兩倍

如果數組長度不大于0 ，再判斷擴容閾值?threshold?是否大于 0 ，也就是看有無外部指定的擴容閾值，若有則使用，這里需要說明一下 threshold 何時是?oldThr > 0，因為 oldThr = threshold ，這里其實比較的就是 threshold，因為 HashMap 中的每個構造方法都會調用?HashMap(initCapacity,loadFactor)?這個構造方法，所以如果沒有外部指定 initialCapacity，初始容量使用的就是 16，然后根據?this.threshold = tableSizeFor(initialCapacity);?求得 threshold 的值。

否則，直接使用默認的初始容量和擴容閾值，走 else 的邏輯是在 table 剛剛初始化的時候。

然后會判斷 newThr 是否為 0 ，筆者在剛開始研究時發現?newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);?一直以為這是常量做乘法，怎么會為 0 ，其實不是這部分的問題，在于上面邏輯判斷中的擴容操作，可能會導致位溢出。

導致位溢出的示例：oldCap = 2^28 次冪，threshold > 2 的三次方整數次冪。在進入到?float ft = (float)newCap * loadFactor;?這個方法是 2^28 * 2^(3+n) 會直接 > 2^31 次冪，導致全部歸零。

「在擴容后需要把節點放在新擴容的數組中，這里也涉及到三個步驟」

循環桶中的每個 Node 節點，判斷 Node[i] 是否為空，為空直接返回，不為空則遍歷桶數組，并將鍵值對映射到新的桶數組中。
如果不為空，再判斷是否是樹形結構，如果是樹形結構則按照樹形結構進行拆分，拆分方法在?split?方法中。
如果不是樹形結構，則遍歷鏈表，并將鏈表節點按原順序進行分組。

講一講 get 方法全過程

我們上面講了 HashMap 中的 put 方法全過程，下面我們來看一下?get?方法的過程，

public?V?get(Object?key)?{Node<K,V>?e;return?(e?=?getNode(hash(key),?key))?==?null???null?:?e.value; }final?Node<K,V>?getNode(int?hash,?Object?key)?{Node<K,V>[]?tab;?Node<K,V>?first,?e;?int?n;?K?k;//?找到真實的元素位置if?((tab?=?table)?!=?null?&&?(n?=?tab.length)?>?0?&&(first?=?tab[(n?-?1)?&?hash])?!=?null)?{//?總是會check?一下第一個元素if?(first.hash?==?hash?&&?//?always?check?first?node((k?=?first.key)?==?key?||?(key?!=?null?&&?key.equals(k))))return?first;//?如果不是第一個元素，并且下一個元素不是空的if?((e?=?first.next)?!=?null)?{//?判斷是否屬于?TreeNode，如果是?TreeNode?實例，直接從?TreeNode.getTreeNode?取if?(first?instanceof?TreeNode)return?((TreeNode<K,V>)first).getTreeNode(hash,?key);//?如果還不是?TreeNode?實例，就直接循環數組元素，直到找到指定元素位置do?{if?(e.hash?==?hash?&&((k?=?e.key)?==?key?||?(key?!=?null?&&?key.equals(k))))return?e;}?while?((e?=?e.next)?!=?null);}}return?null; }

來簡單介紹下吧，首先會檢查 table 中的元素是否為空，然后根據 hash 算出指定 key 的位置。然后檢查鏈表的第一個元素是否為空，如果不為空，是否匹配，如果匹配，直接返回這條記錄；如果匹配，再判斷下一個元素的值是否為 null，為空直接返回，如果不為空，再判斷是否是?TreeNode?實例，如果是 TreeNode 實例，則直接使用?TreeNode.getTreeNode?取出元素，否則執行循環，直到下一個元素為 null 位置。

getNode?方法有一個比較重要的過程就是?「(n - 1) & hash」，這段代碼是確定需要查找的桶的位置的，那么，為什么要 (n - 1) & hash 呢？

n 就是 HashMap 中桶的數量，這句話的意思也就是說 (n - 1) & hash 就是 (桶的容量 - 1) & hash

//?為什么?HashMap?的檢索位置是?(table.size?-?1)?&?hash public?static?void?main(String[]?args)?{Map<String,Object>?map?=?new?HashMap<>();//?debug?得知?1?的?hash?值算出來是?49map.put("1","cxuan");//?debug?得知?1?的?hash?值算出來是?50map.put("2","cxuan");//?debug?得知?1?的?hash?值算出來是?51map.put("3","cxuan");}

那么每次算完之后的 (n - 1) & hash ，依次為

也就是?「tab[(n - 1) & hash]」?算出的具體位置。

HashMap 的遍歷方式

HashMap 的遍歷，也是一個使用頻次特別高的操作

HashMap 遍歷的基類是?HashIterator，它是一個 Hash 迭代器，它是一個 HashMap 內部的抽象類，它的構造比較簡單，只有三種方法，「hasNext 、 remove 和 nextNode」?方法，其中 nextNode 方法是由三種迭代器實現的

這三種迭代器就就是

KeyIterator?，對 key 進行遍歷
ValueIterator，對 value 進行遍歷
EntryIterator，對 Entry 鏈進行遍歷

雖然說看著迭代器比較多，但其實他們的遍歷順序都是一樣的，構造也非常簡單，都是使用?HashIterator?中的?nextNode?方法進行遍歷

final?class?KeyIterator?extends?HashIteratorimplements?Iterator<K>?{public?final?K?next()?{?return?nextNode().key;?}}final?class?ValueIterator?extends?HashIteratorimplements?Iterator<V>?{public?final?V?next()?{?return?nextNode().value;?} }final?class?EntryIterator?extends?HashIteratorimplements?Iterator<Map.Entry<K,V>>?{public?final?Map.Entry<K,V>?next()?{?return?nextNode();?} }

HashIterator 中的遍歷方式

abstract?class?HashIterator?{Node<K,V>?next;????????//?下一個?entry?節點Node<K,V>?current;?????//?當前?entry?節點int?expectedModCount;??//?fail-fast?的判斷標識int?index;?????????????//?當前槽HashIterator()?{expectedModCount?=?modCount;Node<K,V>[]?t?=?table;current?=?next?=?null;index?=?0;if?(t?!=?null?&&?size?>?0)?{?//?advance?to?first?entrydo?{}?while?(index?<?t.length?&&?(next?=?t[index++])?==?null);}}public?final?boolean?hasNext()?{return?next?!=?null;}final?Node<K,V>?nextNode()?{Node<K,V>[]?t;Node<K,V>?e?=?next;if?(modCount?!=?expectedModCount)throw?new?ConcurrentModificationException();if?(e?==?null)throw?new?NoSuchElementException();if?((next?=?(current?=?e).next)?==?null?&&?(t?=?table)?!=?null)?{do?{}?while?(index?<?t.length?&&?(next?=?t[index++])?==?null);}return?e;}public?final?void?remove()?{...} }

next 和 current 分別表示下一個 Node 節點和當前的 Node 節點，HashIterator 在初始化時會遍歷所有的節點。下面我們用圖來表示一下他們的遍歷順序

你會發現?nextNode()?方法的遍歷方式和 HashIterator 的遍歷方式一樣，只不過判斷條件不一樣，構造 HashIterator 的時候判斷條件是有沒有鏈表，桶是否為 null，而遍歷 nextNode 的判斷條件變為下一個 node 節點是不是 null ，并且桶是不是為 null。

HashMap 中的移除方法

HashMap 中的移除方法也比較簡單了，源碼如下

public?V?remove(Object?key)?{Node<K,V>?e;return?(e?=?removeNode(hash(key),?key,?null,?false,?true))?==?null??null?:?e.value; }final?Node<K,V>?removeNode(int?hash,?Object?key,?Object?value,boolean?matchValue,?boolean?movable)?{Node<K,V>[]?tab;?Node<K,V>?p;?int?n,?index;if?((tab?=?table)?!=?null?&&?(n?=?tab.length)?>?0?&&(p?=?tab[index?=?(n?-?1)?&?hash])?!=?null)?{Node<K,V>?node?=?null,?e;?K?k;?V?v;if?(p.hash?==?hash?&&((k?=?p.key)?==?key?||?(key?!=?null?&&?key.equals(k))))node?=?p;else?if?((e?=?p.next)?!=?null)?{if?(p?instanceof?TreeNode)node?=?((TreeNode<K,V>)p).getTreeNode(hash,?key);else?{do?{if?(e.hash?==?hash?&&((k?=?e.key)?==?key?||(key?!=?null?&&?key.equals(k))))?{node?=?e;break;}p?=?e;}?while?((e?=?e.next)?!=?null);}}if?(node?!=?null?&&?(!matchValue?||?(v?=?node.value)?==?value?||(value?!=?null?&&?value.equals(v))))?{if?(node?instanceof?TreeNode)((TreeNode<K,V>)node).removeTreeNode(this,?tab,?movable);else?if?(node?==?p)tab[index]?=?node.next;elsep.next?=?node.next;++modCount;--size;afterNodeRemoval(node);return?node;}}return?null; }

remove 方法有很多，最終都會調用到 removeNode 方法，只不過傳遞的參數值不同，我們拿 remove(object) 來演示一下。

首先會通過 hash 來找到對應的 bucket，然后通過遍歷鏈表，找到鍵值相等的節點，然后把對應的節點進行刪除。

關于 HashMap 的面試題

HashMap 的數據結構

JDK1.7 中，HashMap 采用位桶 + 鏈表的實現，即使用鏈表來處理沖突，同一 hash 值的鏈表都存儲在一個數組中。但是當位于一個桶中的元素較多，即 hash 值相等的元素較多時，通過 key 值依次查找的效率較低。

所以，與 JDK 1.7 相比，JDK 1.8 在底層結構方面做了一些改變，當每個桶中元素大于 8 的時候，會轉變為紅黑樹，目的就是優化查詢效率。

HashMap 的 put 過程

大致過程如下，首先會使用 hash 方法計算對象的哈希碼，根據哈希碼來確定在 bucket 中存放的位置，如果 bucket 中沒有 Node 節點則直接進行 put，如果對應 bucket 已經有 Node 節點，會對鏈表長度進行分析，判斷長度是否大于 8，如果鏈表長度小于 8 ，在 JDK1.7 前會使用頭插法，在 JDK1.8 之后更改為尾插法。如果鏈表長度大于 8 會進行樹化操作，把鏈表轉換為紅黑樹，在紅黑樹上進行存儲。

HashMap 為啥線程不安全

HashMap 不是一個線程安全的容器，不安全性體現在多線程并發對 HashMap 進行 put 操作上。如果有兩個線程 A 和 B ，首先 A 希望插入一個鍵值對到 HashMap 中，在決定好桶的位置進行 put 時，此時 A 的時間片正好用完了，輪到 B 運行，B 運行后執行和 A 一樣的操作，只不過 B 成功把鍵值對插入進去了。如果 A 和 B 插入的位置（桶）是一樣的，那么線程 A 繼續執行后就會覆蓋 B 的記錄，造成了數據不一致問題。

還有一點在于 HashMap 在擴容時，因 resize 方法會形成環，造成死循環，導致 CPU 飆高。

HashMap 是如何處理哈希碰撞的

HashMap 底層是使用位桶 + 鏈表實現的，位桶決定元素的插入位置，位桶是由 hash 方法決定的，當多個元素的 hash 計算得到相同的哈希值后，HashMap 會把多個 Node 元素都放在對應的位桶中，形成鏈表，這種處理哈希碰撞的方式被稱為鏈地址法。

其他處理 hash 碰撞的方式還有?「開放地址法、rehash 方法、建立一個公共溢出區」這幾種方法。

HashMap 是如何 get 元素的

首先會檢查 table 中的元素是否為空，然后根據 hash 算出指定 key 的位置。然后檢查鏈表的第一個元素是否為空，如果不為空，是否匹配，如果匹配，直接返回這條記錄；如果匹配，再判斷下一個元素的值是否為 null，為空直接返回，如果不為空，再判斷是否是?TreeNode?實例，如果是 TreeNode 實例，則直接使用?TreeNode.getTreeNode?取出元素，否則執行循環，直到下一個元素為 null 位置。

HashMap 和 HashTable 有什么區別

見上

HashMap 和 HashSet 的區別

見上

HashMap 是如何擴容的

HashMap 中有兩個非常重要的變量，一個是?loadFactor?，一個是?threshold?，loadFactor 表示的就是負載因子，threshold 表示的是下一次要擴容的閾值，當 threshold = loadFactor * 數組長度時，數組長度擴大位原來的兩倍，來重新調整 map 的大小，并將原來的對象放入新的 bucket 數組中。

HashMap 的長度為什么是 2 的冪次方

這道題我想了幾天，之前和群里小伙伴們探討每日一題的時候，問他們為什么 length%hash == (n - 1) & hash，它們說相等的前提是 length 的長度 2 的冪次方，然后我回了一句難道 length 還能不是 2 的冪次方嗎？其實是我沒有搞懂因果關系，因為 HashMap 的長度是 2 的冪次方，所以使用余數來判斷在桶中的下標。如果 length 的長度不是 2 的冪次方，小伙伴們可以舉個例子來試試。

例如長度為 9 時候，3 & (9-1) = 0，2 & (9-1) = 0 ，都在 0 上，碰撞了；

這樣會增大 HashMap 碰撞的幾率。

HashMap 線程安全的實現有哪些

因為 HashMap 不是一個線程安全的容器，所以并發場景下推薦使用?ConcurrentHashMap?，或者使用線程安全的 HashMap，使用?Collections?包下的線程安全的容器，比如說

Collections.synchronizedMap(new?HashMap());

還可以使用 HashTable ，它也是線程安全的容器，基于 key-value 存儲，經常用 HashMap 和 HashTable 做比較就是因為 HashTable 的數據結構和 HashMap 相同。

上面效率最高的就是 ConcurrentHashMap。

文章并沒有敘述太多關于紅黑樹的構造、包含添加、刪除、樹化等過程，一方面是自己能力還達不到，一方面是關于紅黑樹的描述太過于占據篇幅，紅黑樹又是很大的一部分內容，所以會考慮放在后續的紅黑樹進行講解。

總結

以上是生活随笔為你收集整理的看完这篇 HashMap ，和面试官扯皮就没问题了的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

上一篇：数据中台 VS 传统大数据平台，这 8
下一篇：【我想进大厂】Redis夺命连环11问