面試官:Hash 碰撞是什么?如何解決?被問懵了……
Hash如何存數(shù)據(jù)
hash表的本質(zhì)其實就是數(shù)組，hash表中通常存放的是鍵值對Entry。
如下圖:
這里的學(xué)號是個key，哈希表就是根據(jù)key值來通過哈希函數(shù)計算得到一個值，這個值就是下標(biāo)值，用來確定這個Entry要存放在哈希表中哪個位置。
Hash碰撞
hash碰撞指的是，兩個不同的值（比如張三、李四的學(xué)號）經(jīng)過hash計算后，得到的hash值相同，后來的李四要放到原來的張三的位置，但是數(shù)組的位置已經(jīng)被張三占了，導(dǎo)致沖突。
解決方法
hash碰撞的解決方式是開放尋址法和拉鏈法。
開放尋址法指的是，當(dāng)前數(shù)組位置1被占用了，就放到下一個位置2上去，如果2也被占用了，就繼續(xù)往下找，直到找到空位置。
拉鏈法采用的是鏈表的方式，這個時候位置1就不單單存放的是Entry了，此時的Entry還要額外保存一個next指針，指向數(shù)組外的另一個位置，將李四安排在這里，張三那個Entry中的next指針就指向李四的這個位置，也就是保存的這個位置的內(nèi)存地址。
如果還有沖突，就把又沖突的那個Entry放到一個新位置上，然后李四的Entry指向它，這樣就形成一個鏈表。
總結(jié)起來：開放尋址法和拉鏈法都是想辦法找到下一個空位置來存發(fā)生沖突的值。
來源：blog.csdn.net/zsyoung/article/details/114505480
-End-
最近有一些小伙伴，讓我?guī)兔φ乙恍?面試題?資料，于是我翻遍了收藏的 5T 資料后，匯總整理出來，可以說是程序員面試必備！所有資料都整理到網(wǎng)盤了，歡迎下載！
面試題】即可獲取
在看點這里
好文分享給更多人↓↓