快捷導(dǎo)航

Java中HashMap如何解決哈希沖突

更新時(shí)間：2022年05月27日 09:18:46 作者：請(qǐng)叫我黃同學(xué)

本文主要介紹了Java中HashMap如何解決哈希沖突，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(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沖突的方法有四種

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

在這里插入圖片描述

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

鏈?zhǔ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黑樹來(lái)解決Hash沖突的問(wèn)題，其中紅黑樹是為了優(yōu)化Hash表的鏈表過(guò)長(zhǎng)導(dǎo)致時(shí)間復(fù)雜度增加的問(wèn)題，當(dāng)鏈表長(zhǎng)度大于等于8并且Hash表的容量大于64的時(shí)候，再向鏈表添加元素，就會(huì)觸發(fā)鏈表向紅黑樹的一個(gè)轉(zhuǎn)化

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

您可能感興趣的文章: