一、前言

??在Java 7及之前的版本中，HashMap的底層數據結構主要是數組加鏈表，在Java 8中，HashMap的底層數據結構是數組+鏈表+紅黑樹的組合。

二、底層數據結構

1. 數組

??初始化和擴容：HashMap首先會初始化一個指定長度的數組，作為存儲數據的基本結構。當哈希表中的條目數超出了加載因子（默認為0.75）與當前容量的乘積時，會進行擴容操作，數組長度會擴展為大于原長度2倍的最近的2的n次方的值。
存儲位置：通過哈希函數計算鍵的哈希碼，然后使用哈希碼來確定鍵值對在數組中的存儲位置（即數組的下標）。

2. 鏈表

??哈希沖突：當不同的鍵通過哈希函數計算后得到相同的數組下標時，即發生了哈希沖突。此時，這些鍵值對會形成一個鏈表，存儲在同一個數組元素（桶）中。

??鏈表長度：在Java 8之前，鏈表是處理哈希沖突的唯一方式。而在Java 8中，當鏈表長度較短時（默認閾值為8之前），仍然使用鏈表來存儲沖突的鍵值對。

3. 紅黑樹

??鏈表過長時的優化：在Java 8中，當鏈表中的元素數量超過一定閾值（默認為8）時，并且數組的長度大于或等于64，鏈表會轉換為紅黑樹。這是為了優化在鏈表較長時的查找效率，因為紅黑樹在查找、插入和刪除操作上的性能通常優于鏈表。

??保持性能：紅黑樹的引入使得HashMap在處理大量數據和高哈希沖突時，仍然能夠保持較高的性能。

三、java8之前版本的區別

??性能優化：在Java 8之前，當哈希沖突較多時，鏈表會越來越長，導致查找效率下降。而在Java 8中，當鏈表長度超過閾值時，會自動轉換為紅黑樹，從而保持較高的查找效率。

??空間復雜度：引入紅黑樹雖然提高了性能，但也增加了空間復雜度。因為紅黑樹節點需要額外的空間來存儲父節點指針、顏色標記等信息。然而，這種空間上的開銷通常是可以接受的，因為它帶來了性能上的顯著提升。

??擴容邏輯：無論是Java 8之前還是之后，HashMap的擴容邏輯都是類似的。當哈希表中的條目數超出了加載因子（默認為0.75）與當前容量的乘積時，會進行擴容操作。擴容時，數組長度會擴展為大于原長度2倍的最近的2的n次方的值。

??哈希沖突解決：無論是鏈表還是紅黑樹，都是HashMap解決哈希沖突的方法。在Java 8之前，只使用鏈表；而在Java 8及以后版本中，當鏈表長度過長時，會轉換為紅黑樹以提高性能。

??綜上所述，Java 8中HashMap的底層數據結構通過引入紅黑樹來優化性能，特別是在處理大量數據和高并發場景時表現更為出色。這種設計使得HashMap在保持靈活性和易用性的同時，也具備了較高的性能和可擴展性。