yy玄幻小说排行榜完本,穿越小说完本

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案

秒懂散列表和散列函數(shù)

一、什么是散列表

散列表是由數(shù)組擴(kuò)展而來，其通過散列函數(shù)將元素的鍵值映射為下標(biāo)，然后將元素存儲在數(shù)組中對應(yīng)下標(biāo)的位置。

創(chuàng)新互聯(lián)公司是創(chuàng)新、創(chuàng)意、研發(fā)型一體的綜合型網(wǎng)站建設(shè)公司，自成立以來公司不斷探索創(chuàng)新，始終堅(jiān)持為客戶提供滿意周到的服務(wù)，在本地打下了良好的口碑，在過去的10年時間我們累計服務(wù)了上千家以及全國政企客戶，如成都圍欄護(hù)欄等企業(yè)單位，完善的項(xiàng)目管理流程，嚴(yán)格把控項(xiàng)目進(jìn)度與質(zhì)量監(jiān)控加上過硬的技術(shù)實(shí)力獲得客戶的一致稱譽(yù)。

關(guān)鍵字經(jīng)過散列函數(shù)的計算得到一個散列值：hash(key)=hashCode；關(guān)于散列函數(shù)的選擇和設(shè)計，應(yīng)該要滿足如下三個要求：

散列值一定是一個非負(fù)整數(shù)；
如果key1 == key2，那么hash(k1) == hash(k2)；
如果key1 != key2，那么hash(k1) != hash(k2)；

這三個條件中，最難滿足的就是第三點(diǎn)，在現(xiàn)實(shí)中找一個這樣的散列函數(shù)幾乎是不可能的；比如著名的hash算法MD5、SHA、CRC等，都只是盡量均勻地散列，盡量避免散列沖突，但是做不到完全避免；而且由于數(shù)組空間有限，散列沖突就太正常不過了。

二、如何處理散列沖突

2.1 開放尋址法

線性探測

當(dāng)散列沖突發(fā)生時，存儲位置已經(jīng)被占用，那么就往后探測查找空閑位置；

如果想在散列表中查找某個元素，那么先計算得到散列值，找到該值對應(yīng)的存儲空間，如果無值，說明要查找的元素不存在；如果有值，那么就比對值是否相等，相等則說明找到了，不相等那么就依次往后探測比較，要么找到，要么遇到空閑的存儲空間，說明查找的元素不存在；

如果想在散列表中刪除元素，那么不能將其簡單地刪除，因?yàn)閯h除后會導(dǎo)致該空間后面的元素查找失敗，因?yàn)閷⑿枰獎h除的元素置為邏輯刪除，如此才能不影響后面元素的查找過程；

線性探測方法弊端比較明顯，極端情況下插入、查找、刪除都需要探測n個元素才能找到目標(biāo)位置，時間復(fù)雜度為O(n)；

二次探測

其實(shí)是在線性探測的基礎(chǔ)上每次探測增大步長，比如，每次探測當(dāng)前次數(shù)的平方之后的位置，如此可以降低探測的次數(shù)的概率；但是不能解決線性探測同樣的弊端問題；

雙重散列

準(zhǔn)備多個散列函數(shù)，如果第一個散列之后沖突了，就換一個散列函數(shù)，依次類推，直到找到空閑位置；但是一樣的，當(dāng)元素增多后，所有散列函數(shù)都可能造成散列沖突；

使用場景

當(dāng)數(shù)據(jù)量比較小，且裝載因子也比較小的時候，適合使用開放尋址法，比如ThreadLocalMap；

2.2 鏈表法

該種方法中，每個位置（可以稱為桶、槽）對應(yīng)一個鏈表，所有散列值相同的元素都放在該位置對應(yīng)的鏈表中，結(jié)構(gòu)示意圖如下：

鏈表發(fā)解決散列沖突示意

當(dāng)需要插入元素的時候，直接找到對應(yīng)下標(biāo)的插槽，插入鏈表即可，時間復(fù)雜度為O(1)；

當(dāng)需要查找和刪除元素的時候，也是找到對應(yīng)下標(biāo)的插槽，然后遍歷鏈表查找即可，時間復(fù)雜度為O(n/m)，n是當(dāng)前元素的個數(shù)，m是數(shù)組大小，假設(shè)散列是均勻的，那么時間復(fù)雜度就是鏈表的長度；

無論插入、查找還是刪除，時間復(fù)雜度都要優(yōu)于開放尋址法；

適用場景：

當(dāng)需要存儲的數(shù)據(jù)比較多，或者存儲的是大對象的時候，鏈表法比較合適，而且鏈表的長度過長時可以采用靈活的優(yōu)化策略，比如紅黑樹來代替鏈表，如此查找時間復(fù)雜度最壞情況下的O(n)就能優(yōu)化為O(logn)；

2.3 裝載因子

裝載因子=已經(jīng)裝入散列表中的元素個數(shù)/散列表總的位置個數(shù)

裝載因子是用來衡量散列表當(dāng)前盈滿程度的指標(biāo)，其越大，說明散列沖突的概率就越高，當(dāng)達(dá)到一定程度，就需要對散列表進(jìn)行擴(kuò)容了。

開放尋址法中，裝載因子不會超過100%，但是在拉鏈法中，裝載因子是會超過100%的；

三、散列函數(shù)的設(shè)計

散列函數(shù)不能太復(fù)雜，否則計算散列值就需要花費(fèi)很多時間和資源；

散列函數(shù)生成的值要盡可能隨機(jī)并且均勻分布，最小化散列沖突，并避免某個槽中的鏈表過長；

裝載因子需要根據(jù)實(shí)際情況進(jìn)行設(shè)置，當(dāng)超過閾值會觸發(fā)散列表的擴(kuò)容和rehash（重新申請一個大的散列表），時間復(fù)雜度將為O(n)；當(dāng)小于某個閾值會觸發(fā)縮容和rehash；如果閾值設(shè)置地太大，就容易造成散列沖突，但如果設(shè)置地太小，就容易造成空間資源浪費(fèi)；

為了避免擴(kuò)容和rehash的影響，可以在裝載因子達(dá)到閾值時先申請大的散列表，但是不做rehash，當(dāng)有新的元素需要插入的時候，就插入到新的散列表中，并從舊的散列表中取小量的元素進(jìn)行rehash，當(dāng)插入若干新元素后，舊的散列表中的所有元素就能逐漸rehash到新的散列表，如此是將整個rehash均攤到每次插入新元素操作中，用戶就不會感覺效率低了，此時的時間復(fù)雜度近似O(1)；

四、散列表HashMap分析

初始大小默認(rèn)為16，如果事先能知道數(shù)據(jù)量，可以在初始化的時候就設(shè)置相應(yīng)的大小，避免動態(tài)擴(kuò)容。

最大裝載因子為0.75，觸發(fā)擴(kuò)容時，會擴(kuò)容為原來的兩倍。

當(dāng)鏈表長度超過8時，鏈表就轉(zhuǎn)換為紅黑樹，從而提高增刪查改的效率；當(dāng)紅黑樹元素個數(shù)小于8個的時候，就會再次轉(zhuǎn)換會鏈表，因?yàn)樾?shù)據(jù)量時紅黑樹為了維護(hù)平衡，性能并不比鏈表高。

散列函數(shù)并不復(fù)雜，足夠簡單高效，并且分布均勻。

int hash(Object key){
  // 鍵對象的
  hashcodeint h = key.hashCode();
  // capitity表示散列表的大小
  return (h ^ (h >>> 16)) & (capitity - 1);
}

五、散列表LinkedHashMap分析

也是通過散列表和鏈表組合在一起實(shí)現(xiàn)的，只不過此處的鏈表不是單鏈表，而是雙向鏈表，可以用來記錄元素插入的順序?

本文名稱：秒懂散列表和散列函數(shù)
網(wǎng)站路徑：http://m.fisionsoft.com.cn/article/cddigpe.html

新聞中心

一、什么是散列表