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

散列表：

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

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

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

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

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

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

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

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

解決沖突

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

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

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

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

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

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