1. Hash算法和Hash表

了解Hash沖突首先了解Hash算法和Hash表

• Hash算法就是把任意長度的輸入通過散列算法變成固定長度的輸出，這個輸出結(jié)果就是一個散列值
• Hash表又叫做“散列表”，它是通過key直接訪問到內(nèi)存存儲位置的數(shù)據(jù)結(jié)構(gòu)，在具體的實現(xiàn)上，我們通過Hash函數(shù)，把key映射到表中的某個位置，來獲取這個位置的數(shù)據(jù)，從而加快數(shù)據(jù)的查找

2. Hash沖突

Hash沖突是由于哈希算法，被計算的數(shù)據(jù)是無限的，而計算后的結(jié)果的范圍是有限的，總會存在不同的數(shù)據(jù)，經(jīng)過計算之后得到值是一樣，那么這個情況下就會出現(xiàn)所謂的哈希沖突

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

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

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

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

如圖存在沖突的key直接以單向鏈表的方式去進行存儲

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

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

4.HashMap在JDK1.8版本的優(yōu)化

HashMap在JDK1.8版本中是通過鏈式尋址法以及紅黑樹來解決Hash沖突的問題，其中紅黑樹是為了優(yōu)化Hash表的鏈表過長導致時間復雜度增加的問題，當鏈表長度大于等于8并且Hash表的容量大于64的時候，再向鏈表添加元素，就會觸發(fā)鏈表向紅黑樹的一個轉(zhuǎn)化

到此這篇關于Java中HashMap如何解決哈希沖突的文章就介紹到這了,更多相關Java HashMap哈希沖突內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論