哈希表的簡單介紹

• 哈希表是一種集合結構 包含map和set
• 如果只有key，沒有伴隨數據value，可以使用HashSet結構(C++? stl set)
• 如果擁有key，擁有伴隨數據value，可以使用HashMap結構(C++ stl map)
• 有無伴隨數據是Hashmap和Hashset的唯一區別，底層的實際結構都是一回事，都是使用的紅黑樹

哈希沖突的解決辦法

1，開放尋址法：如果指定位置上存在元素，那么就在存儲在指定位置的下一個元素，如果仍然被占用，繼續移動。以此類推，直到找到一個合適的位置。尋址的方式有很多，這僅僅是一個簡單的例子。Java里面的ThreadLocal就是開放尋址法

2，鏈表法：Java里面的HashMap，每一個元素不僅是是一個Entry對象，還是一個鏈表的頭部節點。每一個Entry對象通過指針指向他的下一個Entry節點。當新來的Entry映射到與之沖突的數組位置時，只需要插入對應的鏈表中即可

散列表擴容

1，多次元素的插入，單列表達到一定的飽和度時候，key映射位置時發生的沖突的概率會逐漸提高；這樣大量的元素會擁擠在相同的數組的下標的位置，會形成很長的鏈表，對后續的插入和查詢操作的性能有很大的影響

對于JDK中的HashMap而言，影響擴容的因素有兩個：1，capacity：即當前的長度；2，loadfactor：負載因子，默認數值為0.75f

衡量HashMap需要擴容的條件是：HashMap.size >= Capacity * LoadFactor

擴容操作 具體干了什么事清呢？

1，擴容，創建一個新的Entry空的數組，長度是先前的2倍

2，重新Hash，遍歷先前的Entry數組，將所有的元素重新進行Hash到新的數組中，這是因為長度擴大之后，Hash的規則也會隨之改變，將先前的Entry重新得到了盡可能均勻的分配

* 當多個Entry被Hash到同一個數組下標的位置時，為了提升插入和查找的效率，HashMap會把Entry鏈表轉化為紅黑樹的結構

?

?

?