HashMap數據結構

HashMap是一種基于哈希表實現的數據結構，它的底層數據結構主要包括兩個部分：數組和鏈表，以及紅黑樹。

如下圖所示:

圖片

HashMap底層數據結構主要包括三部分：數組、鏈表，以及紅黑樹三部分組成實現。

1.數組

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

如下所示：

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


}

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

2.鏈表

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

如下圖所示：

圖片

HashMap 底層結構 (數組 + 鏈表)
--------------------------------
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 代表數組中的一個位置。
• Entry 是鏈表節(jié)點，存儲鍵值對以及下一個節(jié)點的引用。
• 當多個鍵值對的哈希值相同時，它們被鏈接在同一個鏈表中。

3.紅黑樹

當同一個桶中的Entry數量達到一定閾值（默認為8），HashMap會將這個桶中的Entry轉化為一棵紅黑樹。

如下圖所示：

圖片

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

HashMap 底層結構 (數組 + 鏈表 + 紅黑樹)
---------------------------------------
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é)點，取代了長鏈表中的 Entry。

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

但是，這也會出現另外一種情況，當鏈表中的Entry數量較少時，HashMap會將紅黑樹，會重新轉換為鏈表。

這樣設計的目的：這是為了提高查找效率，因為在紅黑樹中查找的時間復雜度為O(log n)，而在鏈表中查找的時間復雜度為O(n)。

簡要總結，如下：

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