HashMap 是一種 KV 形式的數(shù)據(jù)結(jié)構(gòu)，允許有一個 key 為 null，value 允許為 null。HashMap 的存儲，使用的是哈希表，將 key 通過 Hash 函數(shù)運算之后，會獲得一個存儲鍵值對的位置。多個 key 經(jīng)過 Hash 函數(shù)之后，計算得到的存儲位置很有可能是相同的，這就叫做哈希沖突。
解決哈希沖突有多種方法，比如說開放地址發(fā)、再哈希法，以及鏈地址法。HashMap 就是采用鏈地址法來解決哈希沖突的。鏈地址法會在發(fā)生哈希沖突的時候，在數(shù)組的后面掛上一個鏈表，還有沖突就繼續(xù)增加鏈表的長度。
Java 實現(xiàn) HashMap 的時候，對鏈地址法進(jìn)行了優(yōu)化。Java8 在鏈表長度達(dá)到 8 的時候，會將鏈表轉(zhuǎn)換為紅黑樹，因為查找鏈表的時間復(fù)雜度是 O(n)，而查找紅黑樹的時間復(fù)雜度是 O(logN)。
最后，由于 HashMap 的存儲使用了數(shù)組，所以說，在其容量不足的情況下，肯定要涉及到擴容的操作。
總結(jié)，哈希表 => 鏈地址法 => 數(shù)組+鏈表/紅黑樹 => 擴容 => put()、get()、resize()。
以上。
再補充一下：HashMap 計算數(shù)組下標(biāo)的方法，總共分成了 3 步：
- 獲取 key 的 hashCode 值；
- 做移位運算，再讓高位以地位做異或操作；
- (n-1)&hash 計算出最終下標(biāo)位置。
為什么要這么做呢？其實原因是要和操作步驟反著來看的：
- HashMap 保證成倍擴容，在這個前提下，從數(shù)學(xué)上保證
(n-1)&hash等效于取余操作 - n-1是一個不大的數(shù)字，直接與 key 的 hashCode 做 & 操作，就只有 hashCode 的地位參與了運算。而我們使用 Hash 函數(shù)，希望 Hash 散列能夠盡可能地均勻。
- 所以才會加上一個移位運算
h = key.hashCode()) ^ (h >>> 16，這樣計算出來的 hash 值，是高位與地位做異或操作得到的。相當(dāng)于在做 (n-1)&hash 時，key 的高位也參與到了運算中。
