處理hash沖突的方法

引言: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)+i
h1(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

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市库物,隨后出現(xiàn)的幾起案子霸旗,更是在濱河造成了極大的恐慌,老刑警劉巖戚揭,帶你破解...
    沈念sama閱讀 223,126評論 6 520
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件诱告,死亡現(xiàn)場離奇詭異,居然都是意外死亡民晒,警方通過查閱死者的電腦和手機精居,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,421評論 3 400
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來潜必,“玉大人靴姿,你說我怎么就攤上這事」伪悖” “怎么了空猜?”我有些...
    開封第一講書人閱讀 169,941評論 0 366
  • 文/不壞的土叔 我叫張陵,是天一觀的道長恨旱。 經(jīng)常有香客問我辈毯,道長,這世上最難降的妖魔是什么搜贤? 我笑而不...
    開封第一講書人閱讀 60,294評論 1 300
  • 正文 為了忘掉前任谆沃,我火速辦了婚禮,結(jié)果婚禮上仪芒,老公的妹妹穿的比我還像新娘唁影。我一直安慰自己,他們只是感情好掂名,可當(dāng)我...
    茶點故事閱讀 69,295評論 6 398
  • 文/花漫 我一把揭開白布据沈。 她就那樣靜靜地躺著,像睡著了一般饺蔑。 火紅的嫁衣襯著肌膚如雪锌介。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,874評論 1 314
  • 那天,我揣著相機與錄音孔祸,去河邊找鬼隆敢。 笑死,一個胖子當(dāng)著我的面吹牛崔慧,可吹牛的內(nèi)容都是我干的拂蝎。 我是一名探鬼主播,決...
    沈念sama閱讀 41,285評論 3 424
  • 文/蒼蘭香墨 我猛地睜開眼惶室,長吁一口氣:“原來是場噩夢啊……” “哼温自!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起拇涤,我...
    開封第一講書人閱讀 40,249評論 0 277
  • 序言:老撾萬榮一對情侶失蹤捣作,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后鹅士,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體券躁,經(jīng)...
    沈念sama閱讀 46,760評論 1 321
  • 正文 獨居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,840評論 3 343
  • 正文 我和宋清朗相戀三年掉盅,在試婚紗的時候發(fā)現(xiàn)自己被綠了也拜。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點故事閱讀 40,973評論 1 354
  • 序言:一個原本活蹦亂跳的男人離奇死亡趾痘,死狀恐怖慢哈,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情永票,我是刑警寧澤卵贱,帶...
    沈念sama閱讀 36,631評論 5 351
  • 正文 年R本政府宣布,位于F島的核電站侣集,受9級特大地震影響键俱,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜世分,卻給世界環(huán)境...
    茶點故事閱讀 42,315評論 3 336
  • 文/蒙蒙 一编振、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧臭埋,春花似錦踪央、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,797評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至荣恐,卻和暖如春魁莉,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,926評論 1 275
  • 我被黑心中介騙來泰國打工旗唁, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人痹束。 一個月前我還...
    沈念sama閱讀 49,431評論 3 379
  • 正文 我出身青樓检疫,卻偏偏與公主長得像,于是被迫代替她去往敵國和親祷嘶。 傳聞我的和親對象是個殘疾皇子屎媳,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 45,982評論 2 361

推薦閱讀更多精彩內(nèi)容

  • 一、散列的概念 散列方法的主要思想是根據(jù)結(jié)點的關(guān)鍵碼值來確定其存儲地址:以關(guān)鍵碼值K為自變量论巍,通過一定的函數(shù)關(guān)系h...
    SeanMa閱讀 64,193評論 1 30
  • 因為之前就復(fù)習(xí)完數(shù)據(jù)結(jié)構(gòu)了烛谊,所以為了保持記憶,整理了一份復(fù)習(xí)綱要嘉汰,復(fù)習(xí)的時候可以看著綱要想具體內(nèi)容丹禀。 樹 樹的基本...
    牛富貴兒閱讀 6,914評論 3 10
  • 最近在復(fù)習(xí)算法和數(shù)據(jù)結(jié)構(gòu) ,這章把hash表的概念和相關(guān)題目進(jìn)行匯總鞋怀。 一双泪、前言 1.1、哈希表和數(shù)組...
    泥孩兒0107閱讀 1,409評論 0 1
  • 個人博客地址 http://dandanlove.com/ 在平時工作和源碼學(xué)習(xí)的過程中經(jīng)常遇到哈希相關(guān)的問題密似,每...
    靜默加載閱讀 1,062評論 0 3
  • 第一章 緒論 什么是數(shù)據(jù)結(jié)構(gòu)焙矛? 數(shù)據(jù)結(jié)構(gòu)的定義:數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。 第二章...
    SeanCheney閱讀 5,787評論 0 19