Java中HashMap如何解決哈希衝突問題

1. Hash演算法與Hash表

了解Hash衝突首先了解Hash演算法與Hash表

• ##Hash演算法就是把任意長度的輸入透過雜湊演算法變成固定長度的輸出，這個輸出結果就是一個雜湊值

• Hash表又叫做“散列表”，它是透過key直接存取到記憶體儲存位置的資料結構，在具體的實作上，我們透過Hash函數，把key映射到表中的某個位置，來取得這個位置的數據，從而加快資料的查找

2. Hash衝突

Hash衝突是由於雜湊演算法，被計算的數據是無限的，而計算後的結果的範圍是有限的，總是會存在不同的數據，經過計算之後得到值是一樣，那麼這個情況下就會出現所謂的哈希衝突

3. 解決Hash衝突的方法有四種

#開放定址法也稱線性探測法，就是從發生衝突的那個位置開始，按照一定次序從Hash表找到一個空閒位置然後把發生衝突的元素存入到這個位置，而在java中，ThreadLocal就用到了線性探測法來解決Hash衝突

如圖，在Hash表索引1的位置存了key=name，再向它添加key=hobby的時候，假設計算得到的索引也是1，那麼這個時候發生哈希衝突，而開放開放定址法就是按照順序向前找到一個空閒的位置，來儲存這個衝突的key

鍊式尋址法，這是一種常見的方法，簡單理解就是把存在Hash衝突的key，以單向鍊錶來進行存儲，例如HashMap

#如圖存在衝突的key直接以單向鍊錶的方式去進行存儲

再Hash法，就是透過某個Hash函數計算的key，存在衝突的時候，再用另外一個Hash函數對這個可以進行Hash，一直運算，直到不再產生衝突為止，這種方式會增加計算的一個時間,性能上呢會有一些影響

建立公共移除區，就是把Hash表分為基本表和益處表兩個部分，凡是存在衝突的元素，一律放到益處表中

4.HashMap在JDK1.8版本的最佳化

HashMap在JDK1.8版本中是透過鍊式尋址法以及紅黑樹來解決Hash衝突的問題，其中紅黑樹是為了優化Hash表的鍊錶過長導致時間複雜度增加的問題，當鍊錶長度大於等於8並且Hash表的容量大於64的時候，再向鍊錶添加元素，就會觸發鍊錶向紅黑樹的一個轉化

以上是Java中HashMap如何解決哈希衝突問題的詳細內容。更多資訊請關注PHP中文網其他相關文章！