引言：hash沖突作為常見的面試題之一鸠天，是我們所有程序員必須掌握的知識點鼠证；下面是自己學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)時做的一些簡單筆記
1：開放地址法
發(fā)生沖突時使用某種探測技術(shù)在散列表中形成一個探查序列饮睬；沿著這個序列逐個單元的尋找铡原，直到找到給定的關(guān)鍵字沈跨，或者碰到一個開放的地址（即該地址為null時）如果要插入元素則在探測到開發(fā)地址時由捎，直接將內(nèi)容插入就好；查找時探測到開放地址則表明表中沒有待查關(guān)鍵字谒出，查找失斢绶；
①線性探查法(Linear Probing)
該方法的基本思想是：
將散列表T[0..m-1]看成是一個循環(huán)向量笤喳，若初始探查的地址為d(即h(key)=d)为居，則最長的探查序列為：
d，d+l杀狡，d+2忧饭，…导盅，m-1，0，1纱皆，…，d-1
即:探查時從地址d開始揭绑，首先探查T[d]坦报，然后依次探查T[d+1]，…休玩，直到T[m-1]著淆，此后又循環(huán)到T[0]，T[1]拴疤，…永部，直到探查到T[d-1]為止。
②二次探查法(Quadratic Probing)
二次探查法的探查序列是：
hi=(h(key)+ii)％m 0≤i≤m-1 //即di=i2
即探查序列為d=h(key)呐矾，d+12苔埋，d+22，…蜒犯，等组橄。
該方法的缺陷是不易探查到整個散列空間荞膘。
③雙重散列法(Double Hashing)
該方法是開放定址法中最好的方法之一，它的探查序列是：
hi=(h(key)+ih1(key))％m 0≤i≤m-1 //即di=i*h1(key)
即探查序列為：
d=h(key)晨炕，(d+h1(key))％m衫画，(d+2h1(key))％m，…瓮栗，等削罩。
該方法使用了兩個散列函數(shù)h(key)和h1(key)，故也稱為雙散列函數(shù)探查法费奸。
2：拉鏈法
這種方法的基本思想是將所有哈希地址為i的元素構(gòu)成一個稱為同義詞鏈的單鏈表并將單鏈表的頭指針存在哈希表的第i個單元中弥激，因而查找、插入和刪除主要在同義詞鏈中進(jìn)行愿阐。鏈地址法適用于經(jīng)常進(jìn)行插入和刪除的情況微服。
拉鏈法的優(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é)點即可飞蛹。
拉鏈法的缺點
拉鏈法的缺點是：指針需要額外的空間须肆，故當(dāng)結(jié)點規(guī)模較小時，開放定址法較為節(jié)省空間桩皿，而若將節(jié)省的指針空間用來擴大散列表的規(guī)模，可使裝填因子變小幢炸，這又減少了開放定址法中的沖突泄隔，從而提高平均查找速度。
3：再哈希法
這種方法是同時構(gòu)造多個不同的哈希函數(shù)：
Hi=RH1（key） i=1宛徊，2佛嬉，…逻澳，k
當(dāng)哈希地址Hi=RH1（key）發(fā)生沖突時，再計算Hi=RH2（key）……暖呕，直到?jīng)_突不再產(chǎn)生斜做。這種方法不易產(chǎn)生聚集，但增加了計算時間
4：建立公共溢出區(qū)
這種方法的基本思想是：將哈希表分為基本表和溢出表兩部分湾揽，凡是和基本表發(fā)生沖突的元素瓤逼，一律填入溢出表
參考文獻(xiàn)：
http://blog.csdn.net/u012104435/article/details/47951357
http://blog.sina.com.cn/s/blog_6fd335bb0100v1ks.html
處理hash沖突的方法
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
- 文/潘曉璐 我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來潜必，“玉大人靴姿，你說我怎么就攤上這事」伪悖” “怎么了空猜？”我有些...
- 文/不壞的土叔 我叫張陵，是天一觀的道長恨旱。 經(jīng)常有香客問我辈毯，道長，這世上最難降的妖魔是什么搜贤？ 我笑而不...
- 正文 為了忘掉前任谆沃，我火速辦了婚禮，結(jié)果婚禮上仪芒，老公的妹妹穿的比我還像新娘唁影。我一直安慰自己，他們只是感情好掂名，可當(dāng)我...
- 文/花漫 我一把揭開白布据沈。 她就那樣靜靜地躺著，像睡著了一般饺蔑。 火紅的嫁衣襯著肌膚如雪锌介。 梳的紋絲不亂的頭發(fā)上，一...
- 文/蒼蘭香墨 我猛地睜開眼惶室，長吁一口氣：“原來是場噩夢啊……” “哼温自！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起拇涤，我...
- 正文 年R本政府宣布，位于F島的核電站侣集，受9級特大地震影響键俱，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜世分，卻給世界環(huán)境...
- 文/蒙蒙 一编振、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧臭埋，春花似錦踪央、人聲如沸。這莊子的主人今日做“春日...
- 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至荣恐，卻和暖如春魁莉，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背。 一陣腳步聲響...
推薦閱讀更多精彩內(nèi)容
- 一、散列的概念 散列方法的主要思想是根據(jù)結(jié)點的關(guān)鍵碼值來確定其存儲地址：以關(guān)鍵碼值K為自變量论巍，通過一定的函數(shù)關(guān)系h...
- 因為之前就復(fù)習(xí)完數(shù)據(jù)結(jié)構(gòu)了烛谊，所以為了保持記憶，整理了一份復(fù)習(xí)綱要嘉汰，復(fù)習(xí)的時候可以看著綱要想具體內(nèi)容丹禀。 樹 樹的基本...
- 最近在復(fù)習(xí)算法和數(shù)據(jù)結(jié)構(gòu) ，這章把hash表的概念和相關(guān)題目進(jìn)行匯總鞋怀。 一双泪、前言 1.1、哈希表和數(shù)組...
- 個人博客地址 http://dandanlove.com/ 在平時工作和源碼學(xué)習(xí)的過程中經(jīng)常遇到哈希相關(guān)的問題密似，每...
- 第一章 緒論 什么是數(shù)據(jù)結(jié)構(gòu)焙矛？ 數(shù)據(jù)結(jié)構(gòu)的定義：數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。 第二章...
