建站
咨詢(xún)
售后
建站咨詢(xún)
新聞中心
前言
今天來(lái)分享一道比較好的面試題，“HashMap 是怎么解決哈希沖突的？”對(duì)于這個(gè)問(wèn)題，我們一起看看考察點(diǎn)和比較好的回答吧！
目前創(chuàng)新互聯(lián)建站已為上1000+的企業(yè)提供了網(wǎng)站建設(shè)、域名、網(wǎng)絡(luò)空間、綿陽(yáng)服務(wù)器托管、企業(yè)網(wǎng)站設(shè)計(jì)、朔城網(wǎng)站維護(hù)等服務(wù)，公司將堅(jiān)持客戶(hù)導(dǎo)向、應(yīng)用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶(hù)和合作伙伴齊心協(xié)力一起成長(zhǎng)，共同發(fā)展。
考察點(diǎn)
現(xiàn)在的企業(yè)級(jí)開(kāi)發(fā)中HashMap幾乎是最常用到的容器，了解HashMap 是怎么解決哈希沖突的，有助于我們開(kāi)發(fā)出更加優(yōu)秀的代碼。那么這個(gè)問(wèn)題就是面試官想考察我們是不是平日里善于積累，仔細(xì)思考這方面的知識(shí)！
回答
關(guān)于這個(gè)問(wèn)題，我從三個(gè)方面來(lái)回答：
1.hash沖突的基礎(chǔ)就是hash算法和hash表這種數(shù)據(jù)結(jié)構(gòu)。先講講hash算法和hash表。
①Hash 算法，就是通過(guò)散列算法，把任意長(zhǎng)度的輸入變成固定長(zhǎng)度的輸出。這個(gè)輸出就是散列值。
hashValue1 = hash(inputStr1);
hashValue2 = hash(inputStr2);
hashValue1和hashValue2的長(zhǎng)度一樣②Hash 表又叫做“散列表”，其本質(zhì)是通過(guò)key，可以直接訪(fǎng)問(wèn)在內(nèi)存存儲(chǔ)位置的數(shù)據(jù)結(jié)構(gòu)。因此在表現(xiàn)上，我們可以通過(guò)hash函數(shù)把key映射到散列表中的某個(gè)位置，進(jìn)而獲取這個(gè)位置的數(shù)據(jù)，這樣能夠加快查找速度。
③那么我們所說(shuō)的hash 沖突，因?yàn)楣Ｋ惴ㄓ?jì)算的數(shù)據(jù)是無(wú)窮的，而計(jì)算的結(jié)果范圍是有限的，這樣就會(huì)造成不同的輸入得到的結(jié)果確實(shí)一樣的情況。也就是說(shuō)發(fā)生了沖突。如圖所示：
2.如何結(jié)果hash沖突呢？這里講一下常用的4中方法。
①開(kāi)放定址法，也被稱(chēng)為線(xiàn)性探測(cè)法，其原理是這樣的，從發(fā)生沖突的那個(gè)位置開(kāi)始，通過(guò)一定的次序從hash表里面找一個(gè)空閑的位置。之后將發(fā)生沖突的元素存入到這個(gè)空閑位置中。在應(yīng)用上面，我們常見(jiàn)的ThreadLocal就是用到了線(xiàn)性探測(cè)法來(lái)解決hash沖突。如圖，在 hash 表索引 1 的位置存了一個(gè) key=name，當(dāng)再次添加key=hobby 時(shí)hash 計(jì)算得到的索引也是 1，這個(gè)就是 hash 沖突。而開(kāi)放定址法，就是按順序向前找到一個(gè)空閑的位置來(lái)存儲(chǔ)沖突的 key。
②鏈?zhǔn)綄ぶ贩ǎ@是一種非常常見(jiàn)的方法，簡(jiǎn)單理解就是把存在 hash 沖突的 key，以單向鏈表的方式來(lái)存儲(chǔ)，比如 HashMap 就是采用鏈?zhǔn)綄ぶ贩▉?lái)實(shí)現(xiàn)的。向這樣一種情況（如圖），存在沖突的 key 直接以單向鏈表的方式進(jìn)行存儲(chǔ)。
③再 hash 法，就是當(dāng)通過(guò)某個(gè) hash 函數(shù)計(jì)算的 key 存在沖突時(shí)，再用另外一個(gè) hash 函數(shù)對(duì)這個(gè) key 做 hash，一直運(yùn)算直到不再產(chǎn)生沖突。這種方式會(huì)增加計(jì)算時(shí)間，性能影響較大。
④. 建立公共溢出區(qū)， 就是把 hash 表分為基本表和溢出表兩個(gè)部分，凡是存在沖突的元素，一律放入到溢出表中。
3.HashMap 在 JDK1.8 版本中，通過(guò)鏈?zhǔn)綄ぶ贩?紅黑樹(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ā)轉(zhuǎn)化。
以上就是我對(duì)于這個(gè)問(wèn)題的理解。
本文轉(zhuǎn)載自微信公眾號(hào)「程序員的故事」，可以通過(guò)以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系程序員的故事公眾號(hào)。程序員的故事原創(chuàng)文章，遵循CC 4.0 BY-SA版權(quán)協(xié)議。
網(wǎng)站題目：面試題：HashMap是怎么解決哈希沖突的？
文章URL：http://www.5511xx.com/article/djcjpod.html
