以下是我自己的理解，歡迎討論，寫的不輕松。
HashMap中的數據結構是哈希表，也稱為散列表。這裏我將簡單介紹壹下散列表。在此之前，我們需要回顧壹下數組和鏈表的優缺點。
數組和鏈表的優缺點取決於它們在內存中各自的存儲方式，即直接使用順序存儲還是鏈式存儲。數組和鏈表都有明顯的缺點。在實際業務中，我們經常希望數據結構具有良好的尋址、刪除和插入性能。Hashtable就是這樣壹種結構，它巧妙地結合了數組和鏈表的優點，並削弱（而不是完全消除）了其缺點。
哈希表是將鍵映射到數組的壹個下標，訪問時通過鍵獲取索引，然後直接通過索引訪問。它速度極快，將鍵映射到下標需要使用哈希函數，也稱為哈希函數。說到hash函數，可能有人想到了如何將key映射到數組的下標。
以下兩個函數用於計算圖中的下標:
值得註意的是，下標不是由hash函數直接獲得的，需要通過index（）處理來計算下標。
Ps:在哈希表中，數組的網格稱為桶，下標稱為桶號，桶可以包含壹個鍵值對。為了方便理解，這兩個名詞以後就不用了。
以下是與哈希沖突相關的描述:
以下是下標沖突的描述:
很多人認為哈希值的沖突和下標的沖突是壹回事，其實不然。它們的正確關系是這樣的:如果hashCode沖突，下標必然沖突；當下標沖突時，hashCode不壹定會沖突。
如上所述，在jdk1.8之前，HashMap的實現是哈希表=數組+鏈表，但到目前為止我們還沒有看到鏈表的功能。事實上，HashMap引入鏈表的目的是為了解決下標沖突。
下圖是引入鏈表後的哈希表:
如上圖所示，左邊的豎線是壹個大小為16的數組，存儲的是鏈表的頭節點。我們知道，帶有鏈表的頭節點可以訪問整個鏈表，所以我們認為這個數組中的每個下標都存儲了壹個鏈表。具體來說，如果發現下標沖突，則以鏈表的形式將插入的節點追加到前壹個節點。
這種使用鏈表解決沖突的方法稱為拉鏈法（也稱為鏈地址法）。HashMap使用zipper方法，這是沖突後的解決方案。
問:使用拉鏈方法，妳不用擔心沖突嗎？
答:不盡然！因為沖突節點會不斷追加到鏈表中，大量的沖突會導致單個鏈表過長，從而降低查詢性能。因此，壹個好的哈希表的實現應該從源頭上減少沖突的可能性。沖突的概率與散列函數返回值的壹致性直接相關。哈希值越統壹，沖突的可能性就越小。為了使哈希值更加統壹，HashMap單獨實現了hash（）方法。
以上是哈希表的存儲結構，但應用於HashMap時還有其他需要註意的地方，這裏會詳細說明。
現在我們知道了哈希表的存儲結構，細心的人應該發現了壹個問題:Java中數組的長度是固定的。無論哈希函數是否統壹，隨著哈希表中插入數據的增加，在數組長度不變的情況下，鏈表的長度都會不斷增加。這將導致哈希表中鏈表的查詢性能較差的缺點，從而使哈希表失去其原始意義。為了解決這個問題，HashMap引入了擴展和負載因子。
以下是與擴展相關的壹些概念和解釋:
Ps:下標應該為擴展、擴展和擴展重新計算，因為下標的計算與數組長度有關，如果長度發生變化，下標應該重新計算。
在1.8及以上的jdk版本中，HashMap引入了紅黑樹。
引入紅黑樹來代替鏈表。如上所述，如果沖突太多，鏈表就會太長，查詢性能就會降低。統壹哈希函數可以有效緩解過多的沖突，但無法完全避免。因此，HashMap增加了另壹種解決方案。在向鏈表中添加節點時，如果鏈表的長度達到8，就會將鏈表變成紅黑樹，從而提高查詢性能。