Java中HashMap怎么解決哈希沖突

這篇文章主要介紹“Java中HashMap怎么解決哈希沖突”，在日常操作中，相信很多人在Java中HashMap怎么解決哈希沖突問(wèn)題上存在疑惑，小編查閱了各式資料，整理出簡(jiǎn)單好用的操作方法，希望對(duì)大家解答”Java中HashMap怎么解決哈希沖突”的疑惑有所幫助！接下來(lái)，請(qǐng)跟著小編一起來(lái)學(xué)習(xí)吧！

1. Hash算法和Hash表

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

• Hash算法就是把任意長(zhǎng)度的輸入通過(guò)散列算法變成固定長(zhǎng)度的輸出，這個(gè)輸出結(jié)果就是一個(gè)散列值

• Hash表又叫做“散列表”，它是通過(guò)key直接訪問(wèn)到內(nèi)存存儲(chǔ)位置的數(shù)據(jù)結(jié)構(gòu)，在具體的實(shí)現(xiàn)上，我們通過(guò)Hash函數(shù)，把key映射到表中的某個(gè)位置，來(lái)獲取這個(gè)位置的數(shù)據(jù)，從而加快數(shù)據(jù)的查找

2. Hash沖突

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

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

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

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

鏈?zhǔn)綄ぶ贩?，這是一種常見(jiàn)的方法，簡(jiǎn)單理解就是把存在Hash沖突的key，以單向鏈表來(lái)進(jìn)行存儲(chǔ)，比如HashMap

如圖存在沖突的key直接以單向鏈表的方式去進(jìn)行存儲(chǔ)

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

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

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

HashMap在JDK1.8版本中是通過(guò)鏈?zhǔn)綄ぶ贩ㄒ约凹t黑樹(shù)來(lái)解決Hash沖突的問(wèn)題，其中紅黑樹(shù)是為了優(yōu)化Hash表的鏈表過(guò)長(zhǎng)導(dǎo)致時(shí)間復(fù)雜度增加的問(wèn)題，當(dāng)鏈表長(zhǎng)度大于等于8并且Hash表的容量大于64的時(shí)候，再向鏈表添加元素，就會(huì)觸發(fā)鏈表向紅黑樹(shù)的一個(gè)轉(zhuǎn)化

到此，關(guān)于“Java中HashMap怎么解決哈希沖突”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注億速云網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)?lái)更多實(shí)用的文章！