數(shù)據(jù)結(jié)構(gòu)中散列表的簡介
2022-04-29 14:08:53

散列表：

? 散列表是一種數(shù)據(jù)集，其中的數(shù)據(jù)項的存儲方式尤其有利于將來快速的查找定位。

? 散列表中的每一個存儲位置，成為槽（slot），可以用來保存數(shù)據(jù)項，每個槽有唯一一個的名稱。

?例如：一個包含11個槽的散列表，槽的名稱分別為0~10，在插入數(shù)據(jù)項之前，每個槽的值都是None，表示為空槽。

?實現(xiàn)從數(shù)據(jù)項到存儲槽名稱轉(zhuǎn)化的，稱為散列函數(shù)

有一種常用的散列方法是：求余數(shù)，將數(shù)據(jù)項除以散列表的大小，得到的余數(shù)稱為槽號。實際上求余數(shù)方法會以不同形式出現(xiàn)在所有散列函數(shù)里，因為散列函數(shù)返回的槽號必須在散列表大小范圍之內(nèi)，所以一般會對散列表大小求余。

?槽被數(shù)據(jù)項占據(jù)的比例稱為散列表的**“負(fù)載因子”。**

要查找某個數(shù)據(jù)項是否存在于表中，我們只需要使用同一個散列函數(shù)，對查找項進(jìn)行計算，測試下返回的槽號所對應(yīng)的槽中是否有數(shù)據(jù)項即可！實現(xiàn)O（1）時間復(fù)雜度的查找算法。

??缺陷??：沖突，數(shù)據(jù)存在同一個槽里。

解決沖突

??完美散列函數(shù)??：給定一組數(shù)據(jù)項，如果一個散列函數(shù)能把每個數(shù)據(jù)項映射到不同的槽中，那么這個散列函數(shù)就可以稱為：完美散列函數(shù)。對于一組固定的數(shù)據(jù)，總能想辦法設(shè)計出完美散列函數(shù)。

但如果數(shù)據(jù)項經(jīng)常性的變動，很難有一個系統(tǒng)性的方法來設(shè)計對應(yīng)的完美散列函數(shù)，當(dāng)然沖突也不是致命性的錯誤，我們會有辦法處理的。

獲得完美散列函數(shù)的一種方法是擴大散列表的容量，大到所有可能出現(xiàn)的數(shù)據(jù)項都能夠占據(jù)不同的槽。

但是這種方法對于可能數(shù)據(jù)項范圍過大的情況并不實用，比如我們要保存手機號（11位），完美散列函數(shù)得要求散列表具備百億個槽！會浪費太多的存儲空間。

退而求其次，好的散列函數(shù)需要具備的特性：

1.沖突最少（近似完美）
2.計算難度低（額外開銷小）
3.充分分散數(shù)據(jù)項（節(jié)約空間）**