數(shù)據(jù)結(jié)構(gòu)與算法-散列表(Hash Table)

特點(diǎn)

? ??散列表用的是數(shù)組支持按照下標(biāo)隨機(jī)訪問(wèn)數(shù)據(jù)的特性环戈,是數(shù)組的一種擴(kuò)展黍特,由數(shù)組演化而來(lái)

? ? 關(guān)鍵詞

? ??????鍵(key)或者關(guān)鍵字

? ??????散列函數(shù)(或“哈希函數(shù)”): Key轉(zhuǎn)化為數(shù)組下標(biāo)的映射方法

? ??????散列函數(shù)(或“哈希函數(shù)”): 散列函數(shù)計(jì)算得到的值

關(guān)鍵詞介紹

? ? 散列函數(shù)

? ??????它是一個(gè)函數(shù)吃沪,可以把它定義成hash(key)????

????????其中key表示元素的鍵值犀呼,hash(key)的值表示經(jīng)過(guò)散列函數(shù)計(jì)算得到的散列值

? ??????散列函數(shù)設(shè)計(jì)的基本要求

? ??????????1.散列函數(shù)計(jì)算得到的散列值是一個(gè)非負(fù)整數(shù)抡驼;(因?yàn)閿?shù)組下標(biāo)是從0開(kāi)始的)

????????????2.如果key1 = key2争占,那hash(key1) == hash(key2);

????????????3.如果key1 ≠ key2闷袒,那hash(key1) ≠ hash(key2)坑律。

? ??????散列沖突

? ??????????常用的散列沖突解決方法:??

? ? ? ? ? ? 1.開(kāi)放尋址法(open addressing)

? ??????????????核心思想: 如果出現(xiàn)了散列沖突,我們就重新探測(cè)一個(gè)空閑位置囊骤,將其插入

? ??????????????那如何重新探測(cè)新的位置?

????????????????線性探測(cè)(Linear Probing)

? ? ? ? ? ? ? ? ? ? 往散列表插入數(shù)據(jù)時(shí)晃择,如果某個(gè)數(shù)據(jù)經(jīng)過(guò)散列函數(shù)散列后,存儲(chǔ)位置已經(jīng)被占用

? ? ? ? ? ? ? ? ? ? 我們就從當(dāng)前位置開(kāi)始也物,依次往后查找宫屠,看是否有空閑位置,直到找到為止

? ??????????示例: ?色色塊表示空閑位置滑蚯,橙色色塊表示已經(jīng)存儲(chǔ)數(shù)據(jù)浪蹂,往散列表插入X如下:

線性探測(cè)

? ??????????散列表中查找元素過(guò)程

? ? ? ? ? ? ? ? 通過(guò)散列函數(shù)求出要查找元素的鍵值對(duì)應(yīng)的散列值,

????????????????然后比較數(shù)組中下標(biāo)為散列值的元素和要查找的元素告材。

????????????????如果相等坤次,則說(shuō)明就是我們要找的元素;否則就順序往后依次查找斥赋。

????????????????如果遍歷到數(shù)組中的空閑位置缰猴,還沒(méi)有找到,就說(shuō)明要查找的元素并沒(méi)有在散列表中

? ? ? ? ? ? 散列表中刪除元素過(guò)程

? ??????????????不能把要?jiǎng)h除的元素設(shè)為空(如這個(gè)空閑位置是后來(lái)刪除的疤剑,導(dǎo)致原來(lái)查找算法失效)

????????????????我們可以將刪除的元素滑绒,特殊標(biāo)記為deleted胰舆。

????????????????當(dāng)線性探測(cè)查找時(shí),遇到標(biāo)記為deleted的空間蹬挤,并不是停下來(lái),而是繼續(xù)往下探測(cè)

? ? ? ? ? ? 缺陷

? ??????????????當(dāng)散列表中插入的數(shù)據(jù)越來(lái)越多時(shí)棘幸,散列沖突發(fā)生的可能性就會(huì)越來(lái)越大焰扳,

????????????????空閑位置會(huì)越來(lái)越少,線性探測(cè)的時(shí)間就會(huì)越來(lái)越久误续,

? ??????????????極端情況下吨悍,我們可能需要探測(cè)整個(gè)散列表,所以最壞情況下的時(shí)間復(fù)雜度為O(n)

? ??????????????在刪除和查找時(shí)蹋嵌,也會(huì)線性探測(cè)整張散列表育瓜,才能找到要查找或者刪除的數(shù)據(jù)

? ??????????二次探測(cè)(Quadratic probing)

????????????????線性探測(cè)每次探測(cè)的步?是1,那它探測(cè)的下標(biāo)序列就是hash(key)+遞增序號(hào)

? ? ? ? ? ? ? ? 二次探測(cè)探測(cè)步?為原來(lái)的“二次方”栽烂,它探測(cè)的下標(biāo)序列就hash(key)+遞增序號(hào)^2

????????????雙重散列(Double hashing)

? ??????????????不僅要使用一個(gè)散列函數(shù)

? ? ? ? ? ? ? ? 使用一組散列函數(shù)躏仇,先用第一個(gè)散列函數(shù),如果計(jì)算得到的存儲(chǔ)位置已經(jīng)被占用腺办,

????????????????再用第二個(gè)散列函數(shù)焰手,依次類(lèi)推,直到找到空閑的存儲(chǔ)位置

? ? ? ? ? ? 探測(cè)方法總結(jié)

? ??????????????不管采用哪種探測(cè)方法怀喉,當(dāng)散列表中空閑位置不多時(shí)书妻,散列沖突的概率就會(huì)大大提高

? ??????????????一般情況下,我們會(huì)盡可能保證散列表中有一定比例的空閑槽位

? ??????????????裝載因子(load factor)來(lái)表示空位的多少

? ??????????????????散列表的裝載因子=填入表中的元素個(gè)數(shù)/散列表的?度

? ??????????????裝載因子越大躬拢,說(shuō)明空閑位置越少躲履,沖突越多,散列表的性能會(huì)下降

? ? ? ? ? ? ?2.鏈表法(chaining)

? ??????????????一種更加常用的散列沖突解決辦法

? ??????????????在散列表中聊闯,每個(gè)“桶(bucket)”或“槽(slot)”對(duì)應(yīng)一條鏈表工猜,

????????????????所有散列值相同的元素我們都放到相同槽位對(duì)應(yīng)的鏈表中

? ? ? ? ? ? ? ? 插入只需通過(guò)散列函數(shù)計(jì)算出對(duì)應(yīng)的槽位,將其插入到對(duì)應(yīng)鏈表菱蔬,時(shí)間復(fù)雜度為O(1)

? ??????????????查找/刪除元素時(shí)通過(guò)散列函數(shù)計(jì)算出對(duì)應(yīng)的槽域慷,然后遍歷鏈表查找或者刪除

? ? ? ? ? ? ? ? ? ? 操作時(shí)間復(fù)雜度跟鏈表的?度k成正比,也就是O(k)

????????????????????對(duì)于散列比較均勻的散列函數(shù)來(lái)說(shuō)汗销,理論上k=n/m

????????????????????其中n表示散列中數(shù)據(jù)的個(gè)數(shù)犹褒,m表示散列表中“槽”的個(gè)數(shù)

鏈表法示意圖

如何設(shè)計(jì)散列函數(shù)?

? ??首先弛针,散列函數(shù)的設(shè)計(jì)不能太復(fù)雜

? ??其次叠骑,散列函數(shù)生成的值要盡可能隨機(jī)并且均勻分布

? ? 其他,需要考慮因素有關(guān)鍵字的?度削茁、特點(diǎn)宙枷、分布掉房、還有散列表的大小等

裝載因子過(guò)大了怎么辦?

? ??當(dāng)散列表的裝載因子超過(guò)某個(gè)閾值時(shí)慰丛,就需要進(jìn)行擴(kuò)容

? ??裝載因子閾值的設(shè)置要權(quán)衡時(shí)間卓囚、空間復(fù)雜度。

????如果內(nèi)存空間不緊張诅病,對(duì)執(zhí)行效率要求很高哪亿,可以降低負(fù)載因子的閾值;

????相反贤笆,如果內(nèi)存空間緊張蝇棉,對(duì)執(zhí)行效率要求又不高,可以增加負(fù)載因子的值芥永,甚至可以大于1

如何避免低效地?cái)U(kuò)容篡殷?

? ??為了解決一次性擴(kuò)容耗時(shí)過(guò)多的情況,可以將擴(kuò)容操作穿插在插入操作的過(guò)程中埋涧,分批完成板辽。

????當(dāng)裝載因子觸達(dá)閾值之后,我們只申請(qǐng)新空間棘催,但并不將老的數(shù)據(jù)搬移到新散列表中

? ??通過(guò)均攤的方法戳气,將一次性擴(kuò)容的代價(jià)均攤到多次操作中,避免一次性擴(kuò)容耗時(shí)過(guò)多的情況巧鸭。

????這種實(shí)現(xiàn)方式瓶您,任何情況下,插入一個(gè)數(shù)據(jù)的時(shí)間復(fù)雜度都是O(1)

如何選擇沖突解決方法纲仍?

? ??1.開(kāi)放尋址法:? ??

? ??????當(dāng)數(shù)據(jù)量比較小呀袱、裝載因子小的時(shí)候,適合采用開(kāi)放尋址法郑叠。

????????這也是Java中ThreadLocalMap使用開(kāi)放尋址法解決散列沖突的原因

? ??2.鏈表法:?

? ??????鏈表法對(duì)內(nèi)存的利用率比開(kāi)放尋址法要高(鏈表結(jié)點(diǎn)可以在需要的時(shí)候再創(chuàng)建)

? ??????鏈表法比起開(kāi)放尋址法夜赵,對(duì)大裝載因子的容忍度更高

? ??????基于鏈表的散列沖突處理方法比較適合存儲(chǔ)大對(duì)象、大數(shù)據(jù)量的散列表乡革,

????????而且比起開(kāi)放尋址法寇僧,它更加靈活,支持更多的優(yōu)化策略沸版,比如用紅黑樹(shù)代替鏈表

? ??????于是在JDK1.8版本中嘁傀,為了對(duì)HashMap做進(jìn)一步優(yōu)化,引入了紅黑樹(shù)视粮。

? ? ? ? 當(dāng)鏈表?度太?(默認(rèn)為8)時(shí)细办,鏈表轉(zhuǎn)為紅黑樹(shù),利用紅黑樹(shù)快速增刪改查來(lái)提高性能;

????????當(dāng)紅黑樹(shù)結(jié)點(diǎn)個(gè)數(shù)少于8時(shí)蕾殴,紅黑樹(shù)轉(zhuǎn)為鏈表笑撞,小數(shù)據(jù)量時(shí)紅黑樹(shù)要維護(hù)平衡岛啸,性能無(wú)優(yōu)勢(shì)

工業(yè)級(jí)的散列表應(yīng)該具有哪些特性?

? ? 1.支持快速的查詢(xún)茴肥、插入坚踩、刪除操作;

? ? 2.內(nèi)存占用合理瓤狐,不能浪費(fèi)過(guò)多的內(nèi)存空間瞬铸;

? ? 3.性能穩(wěn)定,極端情況下芬首,散列表的性能也不會(huì)退化到無(wú)法接受的情況

如何實(shí)現(xiàn)這樣一個(gè)散列表呢?

? ? 1.設(shè)計(jì)一個(gè)合適的散列函數(shù)逼裆;

? ? 2.定義裝載因子閾值郁稍,并且設(shè)計(jì)動(dòng)態(tài)擴(kuò)容策略;

? ? 3.選擇合適的散列沖突解決方法

散列表和鏈表都是如何組合起來(lái)使用?

? ??LRU緩存淘汰算法

? ? ? ? 借助鏈表+散列表將時(shí)間復(fù)雜度降低為O(1)

? ? ? ? 單純鏈表實(shí)現(xiàn)LRU緩存淘汰算法步驟

? ??????????維護(hù)一個(gè)按照訪問(wèn)時(shí)間從大到小有序排列的鏈表結(jié)構(gòu)胜宇。

????????????因緩存大小有限耀怜,當(dāng)緩存空間不夠,需要淘汰一個(gè)數(shù)據(jù)時(shí)桐愉,直接將鏈表頭部的結(jié)點(diǎn)刪除

? ??????????當(dāng)要緩存某個(gè)數(shù)據(jù)時(shí)财破,先在鏈表中查找這個(gè)數(shù)據(jù)。

????????????如果沒(méi)有找到从诲,則直接將數(shù)據(jù)放到鏈表的尾部左痢;

????????????如果找到了,我們就把它移動(dòng)到鏈表的尾部系洛。

????????????因?yàn)椴檎覕?shù)據(jù)需要遍歷鏈表俊性,所以用鏈表實(shí)現(xiàn)的時(shí)間復(fù)雜度為O(n)

? ? ? ? ? ? 總結(jié)以上步驟,總共有三步,都涉及到查找,只用鏈表實(shí)現(xiàn)到時(shí)間復(fù)雜度為O(n)

? ??????????????往緩存中添加一個(gè)數(shù)據(jù)

? ??????????????從緩存中刪除一個(gè)數(shù)據(jù)

? ??????????????在緩存中查找一個(gè)數(shù)據(jù)

? ? ? ? 鏈表+散列表實(shí)現(xiàn)LUR緩存淘汰算法步驟

????????????雙向鏈表存儲(chǔ)數(shù)據(jù),每個(gè)結(jié)點(diǎn)包括數(shù)據(jù)(data)描扯、前驅(qū)指針(prev)定页、后繼指針(next)、hnext

? ??????????因?yàn)槲覀兊纳⒘斜硎峭ㄟ^(guò)鏈表法解決散列沖突的绽诚,所以每個(gè)結(jié)點(diǎn)會(huì)在兩條鏈中

? ??????????一個(gè)鏈?zhǔn)莿倓偽覀兲岬降碾p向鏈表典徊,另一個(gè)鏈?zhǔn)巧⒘斜碇械睦湣?/p>

????????????前驅(qū)和后繼指針是將結(jié)點(diǎn)串在雙向鏈表中,hnext指針是將結(jié)點(diǎn)串在散列表的拉鏈中

? ??????????這整個(gè)過(guò)程涉及的查找操作都可以通過(guò)散列表來(lái)完成

? ??????????其他的操作恩够,比如刪除頭結(jié)點(diǎn)卒落、鏈表尾部插入數(shù)據(jù)等,可以在O(1)的時(shí)間復(fù)雜度內(nèi)完成

? ? ? ? ? ? 添加蜂桶、查找导绷、刪除三個(gè)操作的時(shí)間復(fù)雜度都為O(1)

? ??????????至此通過(guò)組合使用,實(shí)現(xiàn)了一個(gè)高效的屎飘、支持LRU緩存淘汰算法的緩存系統(tǒng)原型

鏈表+散列表實(shí)現(xiàn)LUR緩存淘汰算法步驟

? ? Java LinkedHashMap

????????HashMap底層是通過(guò)散列表這種數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的妥曲。

????????而LinkedHashMap是通過(guò)雙向鏈表和散列表這兩種數(shù)據(jù)結(jié)構(gòu)組合實(shí)現(xiàn)的贾费。

????????LinkedHashMap中的“Linked”實(shí)際上是指的是雙向鏈表,并非指用鏈表法解決散列沖突

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末檐盟,一起剝皮案震驚了整個(gè)濱河市褂萧,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌葵萎,老刑警劉巖导犹,帶你破解...
    沈念sama閱讀 222,729評(píng)論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場(chǎng)離奇詭異羡忘,居然都是意外死亡谎痢,警方通過(guò)查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,226評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門(mén)卷雕,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)节猿,“玉大人,你說(shuō)我怎么就攤上這事漫雕”踔觯” “怎么了?”我有些...
    開(kāi)封第一講書(shū)人閱讀 169,461評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵浸间,是天一觀的道長(zhǎng)太雨。 經(jīng)常有香客問(wèn)我,道長(zhǎng)魁蒜,這世上最難降的妖魔是什么囊扳? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 60,135評(píng)論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮兜看,結(jié)果婚禮上宪拥,老公的妹妹穿的比我還像新娘。我一直安慰自己铣减,他們只是感情好她君,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,130評(píng)論 6 398
  • 文/花漫 我一把揭開(kāi)白布。 她就那樣靜靜地躺著葫哗,像睡著了一般缔刹。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上劣针,一...
    開(kāi)封第一講書(shū)人閱讀 52,736評(píng)論 1 312
  • 那天校镐,我揣著相機(jī)與錄音,去河邊找鬼捺典。 笑死鸟廓,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播引谜,決...
    沈念sama閱讀 41,179評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼牍陌,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼!你這毒婦竟也來(lái)了员咽?” 一聲冷哼從身側(cè)響起毒涧,我...
    開(kāi)封第一講書(shū)人閱讀 40,124評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎贝室,沒(méi)想到半個(gè)月后契讲,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,657評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡滑频,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,723評(píng)論 3 342
  • 正文 我和宋清朗相戀三年捡偏,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片峡迷。...
    茶點(diǎn)故事閱讀 40,872評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡银伟,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出凉当,到底是詐尸還是另有隱情枣申,我是刑警寧澤售葡,帶...
    沈念sama閱讀 36,533評(píng)論 5 351
  • 正文 年R本政府宣布看杭,位于F島的核電站,受9級(jí)特大地震影響挟伙,放射性物質(zhì)發(fā)生泄漏楼雹。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,213評(píng)論 3 336
  • 文/蒙蒙 一尖阔、第九天 我趴在偏房一處隱蔽的房頂上張望贮缅。 院中可真熱鬧,春花似錦介却、人聲如沸谴供。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 32,700評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)桂肌。三九已至,卻和暖如春永淌,著一層夾襖步出監(jiān)牢的瞬間崎场,已是汗流浹背。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 33,819評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工遂蛀, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留谭跨,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 49,304評(píng)論 3 379
  • 正文 我出身青樓,卻偏偏與公主長(zhǎng)得像螃宙,于是被迫代替她去往敵國(guó)和親蛮瞄。 傳聞我的和親對(duì)象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,876評(píng)論 2 361