Hash碰撞沖突的解決方法-創(chuàng)新互聯(lián)
Hash碰撞沖突的解決方法？很多新手對此不是很清楚，為了幫助大家解決這個難題，下面小編將為大家詳細(xì)講解，有這方面需求的人可以來學(xué)習(xí)下，希望你能有所收獲。
Hash碰撞沖突
我們知道，對象Hash的前提是實現(xiàn)equals()和hashCode()兩個方法，那么HashCode()的作用就是保證對象返回唯一hash值，但當(dāng)兩個對象計算值一樣時，這就發(fā)生了碰撞沖突。如下將介紹如何處理沖突，當(dāng)然其前提是一致性hash。
1.開放地址法
開放地執(zhí)法有一個公式:Hi=(H(key)+di) MOD m i=1,2,…,k(k<=m-1)
其中，m為哈希表的表長。di 是產(chǎn)生沖突的時候的增量序列。如果di值可能為1,2,3,…m-1，稱線性探測再散列。
如果di取1，則每次沖突之后，向后移動1個位置.如果di取值可能為1,-1,2,-2,4,-4,9,-9,16,-16,…k*k,-k*k(k<=m/2)，稱二次探測再散列。
如果di取值可能為偽隨機(jī)數(shù)列。稱偽隨機(jī)探測再散列。
2.再哈希法
當(dāng)發(fā)生沖突時，使用第二個、第三個、哈希函數(shù)計算地址，直到無沖突時。缺點：計算時間增加。
比如上面第一次按照姓首字母進(jìn)行哈希，如果產(chǎn)生沖突可以按照姓字母首字母第二位進(jìn)行哈希，再沖突，第三位，直到不沖突為止
3.鏈地址法（拉鏈法）
將所有關(guān)鍵字為同義詞的記錄存儲在同一線性鏈表中。如下：
因此這種方法，可以近似的認(rèn)為是筒子里面套筒子
4.建立一個公共溢出區(qū)
假設(shè)哈希函數(shù)的值域為[0,m-1],則設(shè)向量HashTable[0..m-1]為基本表，另外設(shè)立存儲空間向量OverTable[0..v]用以存儲發(fā)生沖突的記錄。
拉鏈法的優(yōu)缺點：
優(yōu)點：
①拉鏈法處理沖突簡單，且無堆積現(xiàn)象，即非同義詞決不會發(fā)生沖突，因此平均查找長度較短；
②由于拉鏈法中各鏈表上的結(jié)點空間是動態(tài)申請的，故它更適合于造表前無法確定表長的情況；
③開放定址法為減少沖突，要求裝填因子α較小，故當(dāng)結(jié)點規(guī)模較大時會浪費很多空間。而拉鏈法中可取α≥1，且結(jié)點較大時，拉鏈法中增加的指針域可忽略不計，因此節(jié)省空間；
④在用拉鏈法構(gòu)造的散列表中，刪除結(jié)點的操作易于實現(xiàn)。只要簡單地刪去鏈表上相應(yīng)的結(jié)點即可。而對開放地址法構(gòu)造的散列表，刪除結(jié)點不能簡單地將被刪結(jié) 點的空間置為空，否則將截斷在它之后填人散列表的同義詞結(jié)點的查找路徑。這是因為各種開放地址法中，空地址單元(即開放地址)都是查找失敗的條件。因此在 用開放地址法處理沖突的散列表上執(zhí)行刪除操作，只能在被刪結(jié)點上做刪除標(biāo)記，而不能真正刪除結(jié)點。
缺點：
指針需要額外的空間，故當(dāng)結(jié)點規(guī)模較小時，開放定址法較為節(jié)省空間，而若將節(jié)省的指針空間用來擴(kuò)大散列表的規(guī)模，可使裝填因子變小，這又減少了開放定址法中的沖突，從而提高平均查找速度。
補(bǔ)充知識：java的hashmap如何處理hash碰撞
核心的概念
map是entry的集合，一個key、value就是一個entry
圖解
Java在處理hash沖突的時候使用了鏈表
圖中的0到10號 的方塊就是entry（鍵值對），如果發(fā)生hashcode的沖突，就會像4號方塊那樣，開始向后追加，注意看4號方塊的next的屬性，那個屬性不是null，而是指向了一個方塊
看完上述內(nèi)容是否對您有幫助呢？如果還想對相關(guān)知識有進(jìn)一步的了解或閱讀更多相關(guān)文章，請關(guān)注創(chuàng)新互聯(lián)-成都網(wǎng)站建設(shè)公司行業(yè)資訊頻道，感謝您對創(chuàng)新互聯(lián)的支持。
網(wǎng)站名稱：Hash碰撞沖突的解決方法-創(chuàng)新互聯(lián)
分享URL：http://m.jiaotiyi.com/article/epchj.html