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

HashMap是一種基于哈希表實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)，它的底層數(shù)據(jù)結(jié)構(gòu)主要包括兩個部分：數(shù)組和鏈表，以及紅黑樹。

如下圖所示:

圖片

HashMap底層數(shù)據(jù)結(jié)構(gòu)主要包括三部分：數(shù)組、鏈表，以及紅黑樹三部分組成實(shí)現(xiàn)。

1.數(shù)組

HashMap內(nèi)部維護(hù)了一個Entry數(shù)組，用于存儲鍵值對，Entry是HashMap內(nèi)部定義的一個私有類，包含了key和value兩個屬性。

如下所示：

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


}

數(shù)組的每個元素稱為“桶”，每個桶可能存儲一個或多個Entry對象。

2.鏈表

如果多個Entry對象的hash值相同，它們會被存儲在同一個桶中，形成一個鏈表。

如下圖所示：

圖片

HashMap 底層結(jié)構(gòu) (數(shù)組 + 鏈表)
--------------------------------
Bucket 0    ->   null
Bucket 1    ->   Entry1(key1, value1) -> Entry2(key2, value2) -> null
Bucket 2    ->   null
Bucket 3    ->   Entry3(key3, value3) -> null
Bucket 4    ->   null
...

• 每個 Bucket 代表數(shù)組中的一個位置。
• Entry 是鏈表節(jié)點(diǎn)，存儲鍵值對以及下一個節(jié)點(diǎn)的引用。
• 當(dāng)多個鍵值對的哈希值相同時，它們被鏈接在同一個鏈表中。

3.紅黑樹

當(dāng)同一個桶中的Entry數(shù)量達(dá)到一定閾值（默認(rèn)為8），HashMap會將這個桶中的Entry轉(zhuǎn)化為一棵紅黑樹。

如下圖所示：

圖片

JDK 8 及之后，引入了紅黑樹，鏈表轉(zhuǎn)化為紅黑樹，提高了性能。

HashMap 底層結(jié)構(gòu) (數(shù)組 + 鏈表 + 紅黑樹)
---------------------------------------
Bucket 0    ->   null
Bucket 1    ->   Entry1(key1, value1) -> Entry2(key2, value2) -> null
Bucket 2    ->   null
Bucket 3    ->   TreeNode(key3, value3)
                 /          \
         TreeNode(key4, value4) TreeNode(key5, value5)
Bucket 4    ->   null
...

TreeNode 表示紅黑樹的節(jié)點(diǎn)，取代了長鏈表中的 Entry。

當(dāng)鏈表長度超過閾值時，鏈表會轉(zhuǎn)換為紅黑樹，優(yōu)化查找性能。

但是，這也會出現(xiàn)另外一種情況，當(dāng)鏈表中的Entry數(shù)量較少時，HashMap會將紅黑樹，會重新轉(zhuǎn)換為鏈表。

這樣設(shè)計的目的：這是為了提高查找效率，因?yàn)樵诩t黑樹中查找的時間復(fù)雜度為O(log n)，而在鏈表中查找的時間復(fù)雜度為O(n)。

簡要總結(jié)，如下：

• 數(shù)組 ：提供了快速的定位，根據(jù)鍵計算哈希值，并確定將該鍵值對存儲到數(shù)組中的哪個桶；
• 鏈表：如果多個鍵映射到相同的桶，形成鏈表，解決了哈希沖突，但在大量沖突情況下，查找性能較低；
• 紅黑樹： 則在大量沖突時，轉(zhuǎn)換為紅黑樹，提高了查找性能，時間復(fù)雜度降到 O(log n)。