引言: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ù)元素的集合。 第二章...