最近在復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu)以及在上極客時(shí)間的網(wǎng)課，對(duì)散列表的只是進(jìn)行部分總結(jié)：

1.當(dāng)使用散列表進(jìn)行存儲(chǔ)元素時(shí)，主要使用散列函數(shù)對(duì)鍵值進(jìn)行計(jì)算得到存儲(chǔ)位置?；凇傍澇苍怼?#xff0c;我們不可避免地必須處理沖突的問(wèn)題，解決沖突的方法一般有兩種：

? ? ?① 鏈表法：每個(gè)槽對(duì)應(yīng)一條鏈表，當(dāng)散列函數(shù)計(jì)算后會(huì)進(jìn)入某個(gè)槽，每個(gè)槽有一個(gè)指向鏈表的頭指針，所以插入鏈表時(shí)直接插入頭部就行，因此插入的效率是O(1)。查找一個(gè)元素時(shí)，同樣先對(duì)其鍵值進(jìn)行散列函數(shù)計(jì)算，然后進(jìn)入對(duì)應(yīng)的槽中查找，假設(shè)我們有n個(gè)元素，一共有m個(gè)槽。那么每個(gè)槽平均而言就有n/m個(gè)元素。查找的話(huà)就取決于這個(gè)m了，當(dāng)槽的數(shù)目和元素的數(shù)組接近時(shí)，O（n/m+1）查找的效率就接近O(1)。刪除的話(huà)和查找和類(lèi)似，主要就是那個(gè)刪除的操作。如果采用單鏈表存儲(chǔ)的話(huà)，找到待刪除元素時(shí)還得從鏈表頭找到待刪除元素的前一個(gè)元素。而如果采用雙鏈表的話(huà)效率會(huì)更高。刪除的效率也是接近O(1)。

? ? ? 缺點(diǎn)：最壞的情況就是所有的元素都進(jìn)入了一個(gè)槽，那么在散列表中的查找就退化成了在鏈表中查找，效率也就成了O(n)。

? ? ? 優(yōu)化方法：每個(gè)槽內(nèi)的元素采用“紅黑樹(shù)”或者“跳表”這種數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)，這樣我們就能保證在最壞情況下依然能有基本的效率保證。假如我們用紅黑樹(shù)存儲(chǔ)的話(huà)，查找最壞只不過(guò)退化為O(logn)。

? ? ②開(kāi)放尋址法：當(dāng)發(fā)生沖突時(shí)，我們繼續(xù)往后探測(cè)，如果找到空閑位置就插入。如果沒(méi)找到就一直探測(cè)。那么使用開(kāi)放尋址法處理沖突的散列表如何執(zhí)行查找操作呢？首先通過(guò)散列函數(shù)計(jì)算得到的散列值那個(gè)位置開(kāi)始查找，如果當(dāng)前位置的值就等于待找值的話(huà)就直接返回，如果不等于就繼續(xù)往后探測(cè)，如果一直找到空閑位置還未找到待找值，則返回未找到。插入的過(guò)程與查找類(lèi)似，如果發(fā)生沖突，就不斷繼續(xù)探測(cè)，直到遇到位置為空閑位置就插入。刪除的操作有些特別，我們不能簡(jiǎn)單地就把元素置為空閑，因?yàn)槲覀儾檎沂且杂龅娇臻e位置結(jié)束的。如果我們?cè)谀硞€(gè)值之前的位置執(zhí)行了刪除操作，那么我們重新查找該值得時(shí)候?qū)?huì)顯示查不到。因?yàn)樵谒坝龅搅丝臻e位置。所以刪除我們不能簡(jiǎn)單將位置置為空。而是將其給一個(gè)特殊的標(biāo)志位deleted，當(dāng)查找遇到deleted的位置時(shí)不要停止繼續(xù)往后查找。

? ? 缺點(diǎn)：當(dāng)插入元素越來(lái)越多時(shí)，散列表發(fā)生沖突的概率就會(huì)越來(lái)越大，空閑位置越來(lái)越少，線性探測(cè)時(shí)間也越來(lái)越久。極端情況下，我們可能需要探測(cè)整個(gè)散列表，所以最壞情況下的時(shí)間復(fù)雜度為O(n)。同理在刪除和查找時(shí)，也有可能會(huì)線性探測(cè)整張散列表，才能找到要查找或者刪除的數(shù)據(jù)。

? ?③其他還有二次探測(cè)法和雙重散列法? 二次探測(cè)是每次以02、12、22。。。。步進(jìn)行探測(cè)。雙重散列是使用多個(gè)散列函數(shù)，如果一個(gè)散列函數(shù)計(jì)算出來(lái)的位置被占了，就接著使用第二個(gè)。。以此類(lèi)推直到找到空閑位置。

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

? ?① 散列函數(shù)計(jì)算得到的散列值是一個(gè)非負(fù)整數(shù)

? ?② 如果key1==key2，那么hash(key1)==hash(key2);

? ?③? 如果 key1!=key2，那么hash(key1)!=hash(key2);

? 第三點(diǎn)要求不一定能滿(mǎn)足，沒(méi)有完美的散列函數(shù)能做到，既然避免不了沖突，我們就是用那兩種解決沖突的方法。

? ④ 散列函數(shù)生成的值要盡可能均勻分布在散列表中。

? ⑤ 根據(jù)關(guān)鍵字的長(zhǎng)度、特點(diǎn)、分布、還有散列表的大小等綜合設(shè)計(jì)

? ⑥散列函數(shù)不能太復(fù)雜，否則計(jì)算時(shí)間太長(zhǎng)，影響散列表的效率。

習(xí)題：假設(shè)我們有10萬(wàn)條URL訪問(wèn)日志，如何按照訪問(wèn)次數(shù)給URL排序？

? ? ? ? 答：先將這10萬(wàn)條URL日志放入散列表，key為URL，vlaue為訪問(wèn)次數(shù)。同時(shí)記錄下訪問(wèn)次數(shù)的最大值K，時(shí)間復(fù)雜度為O(n)，如果K不是很大的話(huà)我們可以采用計(jì)數(shù)排序，時(shí)間復(fù)雜度為O（n）。如果k很大的話(huà)就采用快速排序，時(shí)間復(fù)雜度為O(nlogn)。

? ? ? ? ?有兩個(gè)字符串?dāng)?shù)組，每個(gè)數(shù)組大約有10萬(wàn)條字符串，如何快速查找兩個(gè)數(shù)組中相同的字符串？

? ? ? ? 答：先對(duì)一個(gè)數(shù)組遍歷構(gòu)建散列表，key為字符串，value為訪問(wèn)次數(shù)。然后遍歷另一個(gè)數(shù)組，以字符串為key在散列表中查找，如果訪問(wèn)次數(shù)大于0，說(shuō)明存在相同字符串。時(shí)間復(fù)雜度為O（N）。

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

? 答：我們知道隨著裝載因子不斷變大，散列表的效率會(huì)越來(lái)越差。使用開(kāi)放尋址法解決沖突的散列表為了找到空閑位置需要不停探測(cè)，而使用鏈表法解決沖突的散列表隨著裝填因子的變大，在每個(gè)槽里存儲(chǔ)的對(duì)象數(shù)目也越來(lái)越多。查找效率也減少了好多。所以我們一般要在散列表的裝填因子達(dá)到某個(gè)閾值時(shí)，進(jìn)行動(dòng)態(tài)擴(kuò)容，與Vector的擴(kuò)容相類(lèi)似，都是將原來(lái)的元素搬到新的內(nèi)存中去，這段新的內(nèi)存可能是原內(nèi)存的兩倍。這樣裝填因子就成了原來(lái)的一半。與數(shù)組的擴(kuò)容不同的是，數(shù)組只需要簡(jiǎn)單的搬運(yùn)元素就行，而散列表的擴(kuò)容由于散列表的大小發(fā)生了改變，需要對(duì)所有元素進(jìn)行重新散列。復(fù)雜度的分析也與數(shù)組擴(kuò)容類(lèi)似，正常插入的效率一般是O(1)，在最壞情況下需要進(jìn)行擴(kuò)容，重新計(jì)算散列位置。那么效率成了O(n)。采用均攤分析的話(huà)，時(shí)間復(fù)雜度接近O(1)。如果我們對(duì)于空間消耗較為敏感的話(huà)，既然有動(dòng)態(tài)擴(kuò)容我們也可以動(dòng)態(tài)縮容，當(dāng)裝填因子小于某個(gè)值時(shí)，我們開(kāi)啟縮容操作。

?4.裝填因子閾值的設(shè)置

? 答：要綜合權(quán)衡時(shí)間、空間復(fù)雜度、如果內(nèi)存不緊張、對(duì)執(zhí)行效率要求很高的話(huà)，可以降低裝填因子的閾值；相反如果內(nèi)存空間緊張，對(duì)執(zhí)行效率要求不高，可以增加裝填因子閾值。

? 開(kāi)放尋址法裝填因子不能大于1? ? ?鏈表法可以大于1

5.如何避免低效擴(kuò)容？

? ?答：當(dāng)我們的用戶(hù)要求較高時(shí)，不允許出現(xiàn)較為明顯卡頓時(shí)。采用一次性擴(kuò)容的政策就顯得有些局限。盡管大多數(shù)操作都能很快執(zhí)行，但是偶爾的一次插入會(huì)特別慢，用戶(hù)體驗(yàn)就會(huì)下降。所以我們可以將擴(kuò)容操作穿插在插入操作的過(guò)程中，分批完成。當(dāng)裝填因子達(dá)到閾值時(shí)，我們只申請(qǐng)新空間，不搬運(yùn)元素。當(dāng)有新元素插入時(shí)，將其將入到新的散列表中，同時(shí)從老的散列表中拿出一個(gè)元素放入新的散列表中。每一次插入操作都這樣重復(fù)。經(jīng)過(guò)多次操作老的散列表所有元素就都搬到了新的散列表中去，這樣每次插入操作都會(huì)很快了。采用了新的搬運(yùn)操作的話(huà)，查找方法就要發(fā)生改變，當(dāng)我們要查找一個(gè)元素時(shí)，我們先在新的散列表中查找，沒(méi)找到再去舊的散列表中找。避免了一次性擴(kuò)容耗時(shí)過(guò)久的代價(jià)。在新的實(shí)現(xiàn)方式下，所有的插入操作都有了O(1)的效率。

6.比較開(kāi)放尋址法和鏈表法優(yōu)缺點(diǎn)

? 開(kāi)放尋址法? 優(yōu)點(diǎn)：散列表的數(shù)據(jù)都存放在數(shù)組中，可以有效利用CPU的緩存加快查詢(xún)速度。而且香斷鏈表法它不需要很多指針，也避免了不必要的開(kāi)銷(xiāo)。

缺點(diǎn)：刪除操作比較麻煩，相對(duì)于鏈表法，所有的數(shù)據(jù)都存儲(chǔ)在一個(gè)數(shù)組中，沖突的代價(jià)更高。所以采用開(kāi)放尋址法的散列表不能有太高的裝填因子，也使得其比鏈表法更浪費(fèi)內(nèi)存空間。

? ?總結(jié)：當(dāng)數(shù)據(jù)量小，裝填因子小的時(shí)候采用開(kāi)放尋址法。

? 鏈表法? 優(yōu)點(diǎn)：對(duì)內(nèi)存的利用率比開(kāi)放尋址法更高，因?yàn)殒湵斫Y(jié)點(diǎn)可以在需要的時(shí)候再進(jìn)行創(chuàng)建，并不需要像開(kāi)放尋址法那樣事先申請(qǐng)好。鏈表法的裝填因子可以很大，最多就是鏈表的長(zhǎng)度變長(zhǎng)而已，效率會(huì)下降，但是相比順序查找還是很快。

? 鏈表由于不是順序存儲(chǔ)所以無(wú)法使用CPU緩存，而且鏈表的每個(gè)結(jié)點(diǎn)都需要有一個(gè)指針的消耗。當(dāng)然如果我們存儲(chǔ)的是大對(duì)象的話(huà)這一點(diǎn)消耗完全是可以忽略的。

? ? 總結(jié)：鏈表法比較適合大對(duì)象、大數(shù)據(jù)量的散列表，而且比起開(kāi)放尋址法，它更加靈活，支持更多的優(yōu)化策略，比如紅黑樹(shù)代替鏈表。

7.工業(yè)化的散列表實(shí)例

? ?Java的HashMap的默認(rèn)大小為16，默認(rèn)裝填因子為0.75。當(dāng)每個(gè)槽的鏈表長(zhǎng)度大于8時(shí)采用紅黑樹(shù)存儲(chǔ)，小于6時(shí)采用鏈表，因?yàn)楫?dāng)數(shù)據(jù)量較小時(shí)，紅黑樹(shù)要維持平衡，比起鏈表性能并無(wú)太大優(yōu)勢(shì)。

? C++ STL 中的hash_map 也有動(dòng)態(tài)擴(kuò)容，但是并沒(méi)有采用紅黑樹(shù)，也沒(méi)有退化采用的鏈表。直接采用就是鏈表法。

?

總結(jié)

以上是生活随笔為你收集整理的散列表知识点总结的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。