hashMap的數據結構

在jdk8中，HashMap是用了數組和鏈表以及紅黑樹這三種數據結構

首先，在hashmap類中，都有一個table數組，我們在存儲數據時，對這個數據的hash值進行一系列的計算 計算出它在Table中的位置(下標)，並將它存放進去

然而，我們在hashmap是什麼中提到，不同的對象的Hash值可能相同，那麼相同的Hash值會導致不同的數據在數組中有相同的存儲位置，我們雖然創造了一系列的解決辦法，但並不能完全的避免這種衝突，那麼，當產生衝突時，hashmap是怎樣解決的呢？

當產生衝突時，如data1和data2 ,我們把data2放在data1後的列表中，這樣就不會因為哈希值的衝突而對數據產生影響。

1.時間複雜度

我們知道，當某條鏈表的長度大於8時，就會將其轉換為紅黑樹。遍歷一條鏈表的時間複雜度O(n),當一條鏈表過長時，遍歷這條鏈表可能會花很長時間，而遍歷一顆紅黑樹的時間複雜度為O（logn）,從而減少了插入或查找的時間

2.紅黑樹

簡單總結下紅黑樹是什麼：一種二叉查找樹，但在每個結點上增加一個存儲位表示結點的顏色，可以是Red或Black。通過對任何一條從根到葉子的路徑上各個結點著色方式的限制，紅黑樹確保沒有一條路徑會比其他路徑長出倆倍，因而是接近平衡的。

也就是說，紅黑樹是一種相對平衡的查找二叉樹，這使他不僅便於查找，也便於插入和刪除，這對於既需要插入也需要查找的HashMap是非常有利的

下一節：數據哈希值的計算和在table中的存儲位置