建站
咨詢
售后
建站咨詢
新聞中心
一、什么是散列表
散列表是由數(shù)組擴展而來，其通過散列函數(shù)將元素的鍵值映射為下標，然后將元素存儲在數(shù)組中對應(yīng)下標的位置。
創(chuàng)新互聯(lián)公司是創(chuàng)新、創(chuàng)意、研發(fā)型一體的綜合型網(wǎng)站建設(shè)公司，自成立以來公司不斷探索創(chuàng)新，始終堅持為客戶提供滿意周到的服務(wù)，在本地打下了良好的口碑，在過去的10年時間我們累計服務(wù)了上千家以及全國政企客戶，如成都圍欄護欄等企業(yè)單位，完善的項目管理流程，嚴格把控項目進度與質(zhì)量監(jiān)控加上過硬的技術(shù)實力獲得客戶的一致稱譽。
關(guān)鍵字經(jīng)過散列函數(shù)的計算得到一個散列值：hash(key)=hashCode；關(guān)于散列函數(shù)的選擇和設(shè)計，應(yīng)該要滿足如下三個要求：
- 散列值一定是一個非負整數(shù)；
- 如果key1 == key2，那么hash(k1) == hash(k2)；
- 如果key1 != key2， 那么hash(k1) != hash(k2)；
這三個條件中，最難滿足的就是第三點，在現(xiàn)實中找一個這樣的散列函數(shù)幾乎是不可能的；比如著名的hash算法MD5、SHA、CRC等，都只是盡量均勻地散列，盡量避免散列沖突，但是做不到完全避免；而且由于數(shù)組空間有限，散列沖突就太正常不過了。
二、如何處理散列沖突
2.1 開放尋址法
線性探測
當散列沖突發(fā)生時，存儲位置已經(jīng)被占用，那么就往后探測查找空閑位置；
如果想在散列表中查找某個元素，那么先計算得到散列值，找到該值對應(yīng)的存儲空間，如果無值，說明要查找的元素不存在；如果有值，那么就比對值是否相等，相等則說明找到了，不相等那么就依次往后探測比較，要么找到，要么遇到空閑的存儲空間，說明查找的元素不存在；
如果想在散列表中刪除元素，那么不能將其簡單地刪除，因為刪除后會導致該空間后面的元素查找失敗，因為將需要刪除的元素置為邏輯刪除，如此才能不影響后面元素的查找過程；
線性探測方法弊端比較明顯，極端情況下插入、查找、刪除都需要探測n個元素才能找到目標位置，時間復(fù)雜度為O(n)；
二次探測
其實是在線性探測的基礎(chǔ)上每次探測增大步長，比如，每次探測當前次數(shù)的平方之后的位置，如此可以降低探測的次數(shù)的概率；但是不能解決線性探測同樣的弊端問題；
雙重散列
準備多個散列函數(shù)，如果第一個散列之后沖突了，就換一個散列函數(shù)，依次類推，直到找到空閑位置；但是一樣的，當元素增多后，所有散列函數(shù)都可能造成散列沖突；
使用場景
當數(shù)據(jù)量比較小，且裝載因子也比較小的時候，適合使用開放尋址法，比如ThreadLocalMap；
2.2 鏈表法
該種方法中，每個位置（可以稱為桶、槽）對應(yīng)一個鏈表，所有散列值相同的元素都放在該位置對應(yīng)的鏈表中，結(jié)構(gòu)示意圖如下：
鏈表發(fā)解決散列沖突示意
當需要插入元素的時候，直接找到對應(yīng)下標的插槽，插入鏈表即可，時間復(fù)雜度為O(1)；
當需要查找和刪除元素的時候，也是找到對應(yīng)下標的插槽，然后遍歷鏈表查找即可，時間復(fù)雜度為O(n/m)，n是當前元素的個數(shù)，m是數(shù)組大小，假設(shè)散列是均勻的，那么時間復(fù)雜度就是鏈表的長度；
無論插入、查找還是刪除，時間復(fù)雜度都要優(yōu)于開放尋址法；
適用場景：
當需要存儲的數(shù)據(jù)比較多，或者存儲的是大對象的時候，鏈表法比較合適，而且鏈表的長度過長時可以采用靈活的優(yōu)化策略，比如紅黑樹來代替鏈表，如此查找時間復(fù)雜度最壞情況下的O(n)就能優(yōu)化為O(logn)；
2.3 裝載因子
裝載因子=已經(jīng)裝入散列表中的元素個數(shù)/散列表總的位置個數(shù)
裝載因子是用來衡量散列表當前盈滿程度的指標，其越大，說明散列沖突的概率就越高，當達到一定程度，就需要對散列表進行擴容了。
開放尋址法中，裝載因子不會超過100%，但是在拉鏈法中，裝載因子是會超過100%的；
三、散列函數(shù)的設(shè)計
散列函數(shù)不能太復(fù)雜，否則計算散列值就需要花費很多時間和資源；
散列函數(shù)生成的值要盡可能隨機并且均勻分布，最小化散列沖突，并避免某個槽中的鏈表過長；
裝載因子需要根據(jù)實際情況進行設(shè)置，當超過閾值會觸發(fā)散列表的擴容和rehash（重新申請一個大的散列表），時間復(fù)雜度將為O(n)；當小于某個閾值會觸發(fā)縮容和rehash；如果閾值設(shè)置地太大，就容易造成散列沖突，但如果設(shè)置地太小，就容易造成空間資源浪費；
為了避免擴容和rehash的影響，可以在裝載因子達到閾值時先申請大的散列表，但是不做rehash，當有新的元素需要插入的時候，就插入到新的散列表中，并從舊的散列表中取小量的元素進行rehash，當插入若干新元素后，舊的散列表中的所有元素就能逐漸rehash到新的散列表，如此是將整個rehash均攤到每次插入新元素操作中，用戶就不會感覺效率低了，此時的時間復(fù)雜度近似O(1)；
四、散列表HashMap分析
初始大小默認為16，如果事先能知道數(shù)據(jù)量，可以在初始化的時候就設(shè)置相應(yīng)的大小，避免動態(tài)擴容。
最大裝載因子為0.75，觸發(fā)擴容時，會擴容為原來的兩倍。
當鏈表長度超過8時，鏈表就轉(zhuǎn)換為紅黑樹，從而提高增刪查改的效率；當紅黑樹元素個數(shù)小于8個的時候，就會再次轉(zhuǎn)換會鏈表，因為小數(shù)據(jù)量時紅黑樹為了維護平衡，性能并不比鏈表高。
散列函數(shù)并不復(fù)雜，足夠簡單高效，并且分布均勻。
int hash(Object key){
// 鍵對象的
hashcodeint h = key.hashCode();
// capitity表示散列表的大小
return (h ^ (h >>> 16)) & (capitity - 1);
}五、散列表LinkedHashMap分析
也是通過散列表和鏈表組合在一起實現(xiàn)的，只不過此處的鏈表不是單鏈表，而是雙向鏈表，可以用來記錄元素插入的順序?
標題名稱：秒懂散列表和散列函數(shù)
網(wǎng)頁鏈接：http://www.5511xx.com/article/cddigpe.html
