建站
咨詢
售后
建站咨詢
新聞中心
HashMap的實(shí)現(xiàn)原理是什么？
HashMap是一個(gè)高頻的面試題，那么如何才能回答的比較合適呢？
一、青銅級(jí)
以下是jdk1.7與jdk1.8中hashmap的區(qū)別：
概括下可以從以下幾個(gè)方面來回答：
1、基本原理
HashMap是一個(gè)基于Hash散列技術(shù)，以鍵值對(duì)形式存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)。
2、數(shù)據(jù)存儲(chǔ)
JDK 1.8 之前的 HashMap 使用的數(shù)組+鏈表的結(jié)構(gòu)，插入時(shí)使用頭插法。
JDK 1.8 之后的 HashMap 使用的數(shù)組+鏈表/紅黑樹的結(jié)構(gòu)，插入時(shí)使用頭插法。
3、哈希沖突
JDK 1.8 之前的 HashMap 使用的是拉鏈法（Chaining）作為沖突解決策略。
JDK 1.8 引入了紅黑樹作為替代鏈表的沖突解決策略。
4、擴(kuò)容和負(fù)載因子
當(dāng)哈希表中的元素?cái)?shù)量超過一定閾值時(shí)，HashMap 會(huì)自動(dòng)進(jìn)行擴(kuò)容，以保持較低的負(fù)載因子，從而提高性能。
二、王者級(jí)
可以從以下幾個(gè)方面來回答：
1、基本原理
HashMap是一個(gè)基于Hash散列技術(shù)，以鍵值對(duì)形式存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)。
2、數(shù)據(jù)存儲(chǔ)
HashMap內(nèi)部維護(hù)一個(gè)數(shù)組，這個(gè)數(shù)組的每個(gè)位置都是一個(gè)鏈表或紅黑樹的頭節(jié)點(diǎn)。這些節(jié)點(diǎn)用于存儲(chǔ)鍵值對(duì)。
|
jdk1.8之前 |
jdk1.8之后(含1.8) | |
|
結(jié)構(gòu) |
數(shù)組+鏈表 |
數(shù)組+鏈表/紅黑樹 |
|
數(shù)組類型 |
Entry數(shù)組 |
Node數(shù)組 |
（1）JDK1.8之前
JDK1.8之前的 HashMap 由 Entry 數(shù)組組成，Entry 類是 HashMap 中存儲(chǔ)鍵值對(duì)的類。Entry 類包含 key、value 和 next 三個(gè)屬性。key 是鍵，value 是值，next 是指向下一個(gè) Entry 對(duì)象的指針，出現(xiàn) hash 沖突存放到鏈表中。具體源碼是通過 put() 方法實(shí)現(xiàn)的。
put() 方法的實(shí)現(xiàn)如下：
public V put(K key, V value) {
// 如果哈希表為空，則對(duì)其進(jìn)行申請(qǐng)數(shù)組空間
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
// 如果 key 為 null，則將其放入 null 鍵的特殊位置
if (key == null) {
return putForNullKey(value);
}
// 計(jì)算 key 的哈希值
int hash = hash(key);
// 根據(jù)哈希值和哈希表的長(zhǎng)度計(jì)算索引位置
int i = indexFor(hash, table.length);
// 遍歷索引位置上的鏈表，尋找 key
for (Entry e = table[i]; e != null; e = e.next) {
// 如果 key 相同，則更新 value 并返回舊值
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
// 如果 key 不存在，則添加一個(gè)新的鏈表成員
modCount++;
addEntry(hash, key, value, i);
return null;
} put() 方法首先計(jì)算 key 的 hash 值，然后定位到數(shù)組索引位置。如果數(shù)組索引位置上已經(jīng)存在 Entry 對(duì)象，則判斷 key 是否相同。如果相同則直接覆蓋value，否則添加到鏈表中。如果數(shù)組索引位置上不存在 Entry 對(duì)象，則直接添加到數(shù)組中。
鏈表的具體實(shí)現(xiàn)如下：
static class Entry implements Map.Entry {
final int hash;
final K key;
V value;
Entry next;
Entry(int hash, K key, V value) {
this.hash = hash;
this.key = key;
this.value = value;
}
@Override
public K getKey() {
return key;
}
@Override
public V getValue() {
return value;
}
@Override
public V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Entry entry = (Entry) o;
return hash == entry.hash &&
Objects.equals(key, entry.key) &&
Objects.equals(value, entry.value);
}
@Override
public int hashCode() {
return Objects.hash(hash, key, value);
}
@Override
public String toString() {
return key + "=" + value;
}
} 鏈表的每個(gè)元素是一個(gè) Entry 對(duì)象，Entry 對(duì)象包含 key、value、hash 和 next 四個(gè)屬性。key 是鍵，value 是值，hash 是 key 的 hash 值，next 是指向下一個(gè) Entry 對(duì)象的指針。
當(dāng) HashMap 出現(xiàn) hash 沖突時(shí)，會(huì)將新的 Entry 對(duì)象添加到鏈表的尾部。鏈表的查詢性能較差，當(dāng)鏈表長(zhǎng)度過長(zhǎng)時(shí)，會(huì)影響 HashMap 的查詢性能。
源代碼中有幾處關(guān)鍵的地方：
關(guān)鍵一：
先通過indexFor下標(biāo)定位到的數(shù)組元素位置，再遍歷這個(gè)元素(鏈表)，依次和鏈表中的key比較，如果 key 相同就直接覆蓋，不同就采用頭插法插入元素。
關(guān)鍵二：
頭插法的實(shí)現(xiàn)主要涉及到兩個(gè)方法：addEntry 和 createEntry。addEntry 方法用于判斷是否需要擴(kuò)容，并調(diào)用 createEntry 方法將鍵值對(duì)存入數(shù)組中。createEntry 方法用于創(chuàng)建一個(gè)新的節(jié)點(diǎn)，并將其 next 屬性指向原來的鏈表頭節(jié)點(diǎn)，然后將新節(jié)點(diǎn)賦值給數(shù)組對(duì)應(yīng)位置，完成頭插法。
插入元素使用createEntry，新元素會(huì)的next指向table[bucketIndex]也就是鏈表的頭節(jié)點(diǎn)。
（2）JDK1.8之后(含1.8)
JDK1.8的 HashMap 由 Node 數(shù)組組成，Node 類是 HashMap 中存儲(chǔ)鍵值對(duì)的類。Node 類包含 key、value、hash、next 和 prev 五個(gè)屬性。key 是鍵，value 是值，hash 是 key 的 hash 值，next 是指向下一個(gè) Node 對(duì)象的指針，prev 是指向前一個(gè) Node 對(duì)象的指針。
JDK1.8之后的 HashMap 由 Node 數(shù)組組成，出現(xiàn) hash 沖突存放到鏈表中同時(shí)滿足條件的情況下會(huì)生成紅黑樹。具體源碼是通過 put() 方法實(shí)現(xiàn)的。
put() 方法的實(shí)現(xiàn)如下：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// 獲取哈希表
Node[] tab = table;
// 如果哈希表為空或長(zhǎng)度為0，則進(jìn)行擴(kuò)容
if (tab == null || tab.length == 0) {
tab = resize();
}
// 計(jì)算索引位置
int n = tab.length;
int i = (n - 1) & hash;
// 如果索引位置上的節(jié)點(diǎn)為空，則添加一個(gè)新的節(jié)點(diǎn)
Node p = tab[i];
if (p == null) {
tab[i] = newNode(hash, key, value, null);
} else {
// 如果索引位置上的節(jié)點(diǎn)存在，則遍歷鏈表，尋找 key 相同的節(jié)點(diǎn)
Node e; K k;
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) {
e = p;
} else if (p instanceof TreeNode) {
// 如果索引位置上的節(jié)點(diǎn)是紅黑樹節(jié)點(diǎn)，則調(diào)用紅黑樹的 putTreeVal() 方法添加新的節(jié)點(diǎn)
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
} else {
// 如果索引位置上的節(jié)點(diǎn)是鏈表節(jié)點(diǎn)，則遍歷鏈表，尋找 key 相同的節(jié)點(diǎn)
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
// 如果沒有找到 key 相同的節(jié)點(diǎn)，則在鏈表尾部添加一個(gè)新的節(jié)點(diǎn)
p.next = newNode(hash, key, value, null);
// 如果鏈表長(zhǎng)度超過閾值，則將鏈表轉(zhuǎn)換為紅黑樹
if (binCount >= TREEIFY_THRESHOLD - 1) {
treeifyBin(tab, hash);
}
break;
}
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
// 如果找到 key 相同的節(jié)點(diǎn)，則停止遍歷
break;
}
p = e;
}
}
if (e != null) { // 找到 key 相同的節(jié)點(diǎn)
// 獲取舊值
V oldValue = e.value;
// 如果只有 key 不存在才添加新的節(jié)點(diǎn)，則僅當(dāng)舊值為 null 時(shí)才更新值
if (!onlyIfAbsent || oldValue == null) {
e.value = value;
}
// 調(diào)用 afterNodeAccess() 方法更新節(jié)點(diǎn)的訪問時(shí)間
afterNodeAccess(e);
return oldValue;
}
}
// 添加新的節(jié)點(diǎn)后，更新 HashMap 的大小和修改次數(shù)
++modCount;
if (++size > threshold) {
resize();
}
// 調(diào)用 afterNodeInsertion() 方法更新節(jié)點(diǎn)的插入狀態(tài)
afterNodeInsertion(evict);
return null;
} put() 方法在添加元素時(shí)，會(huì)先判斷數(shù)組索引位置上是否已經(jīng)存在 Node 對(duì)象。如果已經(jīng)存在，則判斷 key 是否相同。如果相同則更新 value，否則添加到鏈表中。
如果鏈表長(zhǎng)度超過閾值，則將鏈表轉(zhuǎn)換為紅黑樹。閾值的默認(rèn)值是 8。
treeifyBin() 方法的實(shí)現(xiàn)如下：
final void treeifyBin(Node[] tab, int hash) {
// 如果哈希表為空或長(zhǎng)度小于 MIN_TREEIFY_CAPACITY，則進(jìn)行擴(kuò)容
int n, index; Node e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) {
resize();
} else if ((e = tab[index = (n - 1) & hash]) != null) {
// 獲取索引位置上的節(jié)點(diǎn)
TreeNode hd = null, tl = null;
// 遍歷鏈表，將每個(gè)節(jié)點(diǎn)轉(zhuǎn)換為紅黑樹節(jié)點(diǎn)
do {
TreeNode p = replacementTreeNode(e, null);
if (tl == null) {
hd = p;
} else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
// 將轉(zhuǎn)換后的紅黑樹節(jié)點(diǎn)添加到哈希表中
if ((tab[index] = hd) != null) {
hd.treeify(tab);
}
}
} treeifyBin() 方法首先判斷鏈表的長(zhǎng)度是否超過閾值。如果超過閾值，則將鏈表的第一個(gè)元素作為紅黑樹的根節(jié)點(diǎn)。
然后，將鏈表中的所有元素添加到紅黑樹中。
最后，將紅黑樹的根節(jié)點(diǎn)添加到數(shù)組中。
這樣，當(dāng) HashMap 出現(xiàn) hash 沖突存放到鏈表中同時(shí)滿足條件的情況下，會(huì)將鏈表轉(zhuǎn)換為紅黑樹，提高查詢性能。
源代碼中有幾處關(guān)鍵的地方：
關(guān)鍵一：
當(dāng)鏈表的節(jié)點(diǎn)數(shù)量達(dá)到閾值(默認(rèn)為 8 )，執(zhí)行 treeifyBin 方法。
關(guān)鍵二：
進(jìn)入treeifyBin方法后還有一個(gè)邏輯就是當(dāng)數(shù)組長(zhǎng)度大于或者等于 64 的情況下，才會(huì)執(zhí)行轉(zhuǎn)換紅黑樹操作，以減少搜索時(shí)間。否則，就是只是對(duì)數(shù)組擴(kuò)容。所以鏈表長(zhǎng)度大于閾值不是轉(zhuǎn)為紅黑樹的唯一條件。
關(guān)鍵三：
區(qū)別于jdk1.7，jdk1.8已經(jīng)使用了尾插法實(shí)現(xiàn)鏈表元素的插入。
問題：為什么jdk1.8后改為尾插法？
主要是因?yàn)轭^插法在多線程擴(kuò)容情況下會(huì)引起鏈表環(huán)。那什么是鏈表環(huán)呢？
線程1，第一節(jié)點(diǎn)為A，第二節(jié)點(diǎn)為B后面就沒有了，遍歷過程為A->B然后B沒有后面節(jié)點(diǎn)即遍歷結(jié)束。
這時(shí)線程1掛起。線程2引發(fā)擴(kuò)容，擴(kuò)容后為B->A。這時(shí)線程1遍歷就會(huì)發(fā)現(xiàn)A的下一節(jié)點(diǎn)是B，會(huì)發(fā)現(xiàn)遍歷B時(shí)B還有后續(xù)的節(jié)點(diǎn)為A，這樣就出樣鏈表環(huán)了。
（3）Node 與Entry區(qū)別
在 Java 的 HashMap 中，Node 和 Entry 都是用于表示鍵值對(duì)的數(shù)據(jù)結(jié)構(gòu)，但它們?cè)诓煌姹镜?HashMap 中有一些區(qū)別：
Node：
- Node 是在 JDK 1.8 之后的版本中引入的，用于存儲(chǔ)鍵值對(duì)。
- Node 主要用于存儲(chǔ)在哈希沖突的情況下，將鍵值對(duì)以鏈表或紅黑樹的方式組織起來的數(shù)據(jù)結(jié)構(gòu)。
- Node 是 TreeNode 和 LinkedNode 的父類，這兩個(gè)子類分別用于表示紅黑樹節(jié)點(diǎn)和鏈表節(jié)點(diǎn)。
- Node 中包含了鍵、值、哈希碼、下一個(gè)節(jié)點(diǎn)引用等信息。
Entry：
- Entry 是在 JDK 1.7 及之前的版本中用于存儲(chǔ)鍵值對(duì)的數(shù)據(jù)結(jié)構(gòu)。
- Entry 是 HashMap 內(nèi)部的靜態(tài)內(nèi)部類，用于表示鍵值對(duì)。
- Entry 主要用于存儲(chǔ)在哈希沖突的情況下，將鍵值對(duì)以鏈表的方式組織起來的數(shù)據(jù)結(jié)構(gòu)。
- Entry 中包含了鍵、值、下一個(gè) Entry 的引用等信息。
Node 和 Entry 都用于表示鍵值對(duì)，但它們的命名和實(shí)現(xiàn)方式在不同的 Java 版本中有所不同。Node 主要用于 JDK 1.8 及之后的 HashMap，而 Entry 主要用于 JDK 1.7 及之前的 HashMap。Node 進(jìn)一步改進(jìn)了哈希沖突的處理方式，引入了紅黑樹來提高性能。
3、哈希沖突
JDK 1.8 之前的 HashMap 使用的是拉鏈法（Chaining）作為沖突解決策略。
HashMap 通過 key 的 hashCode 經(jīng)過擾動(dòng)函數(shù)處理過后得到 hash 值，然后通過 (n - 1) & hash 判斷當(dāng)前元素存放的位置，如果當(dāng)前位置存在元素的話，就判斷該元素與要存入的元素的 hash 值以及 key 是否相同，如果相同的話，直接覆蓋，不相同就通過拉鏈法解決沖突。以下就是JDK1.7中的hashcode擾動(dòng)函數(shù)。
JDK 1.8 中，HashMap 使用了拉鏈法和紅黑樹兩種沖突解決策略。當(dāng)鏈表長(zhǎng)度超過一定閾值時(shí)，會(huì)將鏈表轉(zhuǎn)換為紅黑樹。紅黑樹是一種自平衡二叉樹，具有較高的查詢性能。以下就是JDK1.8中的hashcode擾動(dòng)函數(shù)。
JDK1.8 中的 HashMap 在查詢性能上比 JDK1.7 中的 HashMap 有一定的提升。
以下是 JDK1.7 和 JDK1.8 中 HashMap 解決哈希沖突方法的具體對(duì)比：
JDK1.8 中的 HashMap 解決哈希沖突的方法更加靈活，可以適應(yīng)不同的場(chǎng)景。
4、擴(kuò)容和負(fù)載因子
當(dāng)哈希表中的元素?cái)?shù)量超過一定閾值時(shí)，HashMap 會(huì)自動(dòng)進(jìn)行擴(kuò)容，以保持較低的負(fù)載因子，從而提高性能。
Java HashMap 使用負(fù)載因子來控制擴(kuò)容。負(fù)載因子是指 HashMap 中鍵值對(duì)數(shù)與 HashMap 容量的比值。
HashMap 的初始容量為 16，負(fù)載因子為 0.75。這意味著，當(dāng) HashMap 中鍵值對(duì)數(shù)達(dá)到 16 * 0.75 = 12 時(shí)，HashMap 就會(huì)進(jìn)行擴(kuò)容。
HashMap 的擴(kuò)容方式是將容量擴(kuò)大為原來的 2 倍。例如，當(dāng) HashMap 的容量為 16 時(shí)，擴(kuò)容后容量為 32。
HashMap 擴(kuò)容的原因是，當(dāng) HashMap 的負(fù)載因子達(dá)到一定值時(shí)，HashMap 的查詢性能會(huì)下降。這是因?yàn)?，?dāng) HashMap 的容量較小，并且鍵值對(duì)數(shù)較多時(shí)，會(huì)導(dǎo)致哈希沖突的概率增加。
因此，HashMap 會(huì)在負(fù)載因子達(dá)到一定值時(shí)進(jìn)行擴(kuò)容，以提高查詢性能。
以下是 HashMap 擴(kuò)容的具體步驟：
- 創(chuàng)建一個(gè)新的 HashMap，容量為原來的 2 倍。
- 將原 HashMap 中的所有鍵值對(duì)復(fù)制到新 HashMap 中。
- 將原 HashMap 置為空。
網(wǎng)站欄目：HashMap高頻面試題，讓你掌握青銅回答與王者級(jí)回答，你值得擁有
新聞來源：http://m.5511xx.com/article/dhseddj.html
