一、散列表

1.1 散列表

散列表（哈希表）,其思想主要是基于數(shù)組支持按照下標(biāo)隨機(jī)訪問數(shù)據(jù)，時(shí)間復(fù)雜度為O（1）的特性。

可以說是數(shù)組的一種拓展。

假設(shè)，我們?yōu)榱朔奖阌涗浤掣咝?shù)學(xué)專業(yè)的某個(gè)學(xué)生的信息，要求可以按照學(xué)號（入學(xué)時(shí)間+年級+專業(yè)+專業(yè)內(nèi)自增序號，如2019 1001 0002）能夠快速找到某個(gè)學(xué)生的信息。

這個(gè)時(shí)候我們可以取學(xué)號的自增序號部分，即后四位作為數(shù)組的索引下表，把學(xué)生相應(yīng)的信息存儲(chǔ)到對應(yīng)的內(nèi)存空間內(nèi)即可。

如上圖所示，我們把學(xué)號作為Key，通過截取學(xué)號后四位的函數(shù)計(jì)算后得到索引下標(biāo)，將數(shù)據(jù)存儲(chǔ)到數(shù)組中。

當(dāng)我們按照鍵值（學(xué)號）查找時(shí)，只需要再次計(jì)算出索引下標(biāo)，然后取出相應(yīng)數(shù)據(jù)即可。

以上便是散列思想。

計(jì)算下標(biāo)的函數(shù)我們叫它為 散列函數(shù) 或 哈希函數(shù)

1.2 散列函數(shù)

上面的例子中，截取學(xué)號后四位的函數(shù)就是一個(gè)簡單的散列函數(shù)。

//散列函數(shù) 偽代碼 
int Hash(string key) {
  // 獲取后四位字符
  string hashValue =int.parse(key.Substring(key.Length-4, 4));
  // 將后兩位字符轉(zhuǎn)換為整數(shù)
  return hashValue;
}

在這里散列函數(shù)的作用就是將Key值映射成數(shù)組的索引下標(biāo)。

關(guān)于散列函數(shù)的設(shè)計(jì)方法有很多，如：直接尋址法、數(shù)字分析法、隨機(jī)數(shù)法、取余法等等。

但即使再優(yōu)秀的設(shè)計(jì)方法也不能夠避免散列沖突。

在散列表中散列函數(shù)不應(yīng)設(shè)計(jì)的太復(fù)雜，不然太復(fù)雜的散列函數(shù)會(huì)造成更多的性能消耗，結(jié)果就適得其反了。

1.3 散列沖突

就像圖上所表達(dá)的一樣，不同的key通過散列函數(shù)計(jì)算出來的hash值相同，造成了這兩個(gè)數(shù)據(jù)都需要存儲(chǔ)在這個(gè)同一個(gè)下標(biāo)(內(nèi)存空間)上。

散列函數(shù)具有確定性和不確定性：

• 確定性：哈希的散列值不同，那么哈希的原始輸入絕對不相同。即hash(key1) ≠ hash(key2)，key1≠key2
• 不確定性：同一個(gè)散列值很有可能對應(yīng)多個(gè)不同的原始輸入。即hash(key1) =hash(key2)，key1≠key2

散列沖突：即key1≠key2，hash(key1)=hash(key2)的情況，散列沖突是不可避免的，如果我們key的個(gè)數(shù)為100，而數(shù)組的索引數(shù)量只有50，那么再優(yōu)秀的算法也無法避免散列沖突。

關(guān)于散列沖突也有很多解決辦法，這里簡單說明兩種： 開放尋址法 和 鏈表法 。

1.3.1 開放尋址法

開放尋址法的核心思想是，如果出現(xiàn)了散列沖突，我們就重新探測一個(gè)空閑位置，將其插入。

比如我們可以使用線性探測法。當(dāng)我們散列表中插入數(shù)據(jù)時(shí)，如果某個(gè)數(shù)據(jù)的key經(jīng)過散列函數(shù)散列之后，散列值對應(yīng)的存儲(chǔ)位置（下標(biāo)）已經(jīng)被占用，那么就從這個(gè)被占用的位置開始，依次往后進(jìn)行尋找空閑的位置，如果遍歷到尾部都沒有找到空閑的位置，那么我們就在從表頭開始找，知道找到為止。

散列表中查找元素的時(shí)候，我們通過散列函數(shù)求出要查找元素的鍵值對應(yīng)的散列值，然后比較數(shù)組中下標(biāo)為散列值的元素中的key和要查找的元素的key，如果相等則說明我就是我們要找的元素，否則就按順序往后依次查找。如果遍歷到數(shù)組中的空閑位置還是沒有找到想要的元素，就說明我們的找的元素不在該散列表中。

好，雖然使用開放尋址法完成了鍵值對的存儲(chǔ)和查找，但是對刪除操作稍微有些特別，不能單純的把要?jiǎng)h除的元素設(shè)置為空。因?yàn)樵诓檎业臅r(shí)候，我們通過線性探測法就會(huì)按順序向后面的內(nèi)存空間（下標(biāo)）一個(gè)一個(gè)的找，直到找到對應(yīng)的value或空為止，但是如果這時(shí)候碰到一個(gè)內(nèi)存空間（下標(biāo)）中的值是空，而這個(gè)空位置是我們刪除了其他元素后置為空的，就導(dǎo)致這個(gè)查找算法失效。 我們可以將刪除的元素，特殊的標(biāo)記為deleted。當(dāng)線性探測查找的時(shí)候，遇到標(biāo)記為deleted的空間并不是停下來，而是繼續(xù)向下探測。

線性探測法存在很大的問題。當(dāng)散列表中插入的數(shù)據(jù)越來越多時(shí)，其散列沖突的可能性就會(huì)越來越大，在極端情況下甚至要探測整個(gè)散列表，因此最壞的時(shí)間復(fù)雜度為O(N)。在開放尋址法中，除了線性探測法，我們可以使用二次探測和雙重散列等方式。

1.3.2 鏈表法

鏈表法是一種比較常見的散列解決辦法，Java的HashMap和Redis的Hash結(jié)構(gòu)就是使用的鏈表法來解決散列沖突。 鏈表法的原理：如果遇到?jīng)_突，就會(huì)在原地址上新建一個(gè)空間，讓已經(jīng)存在的元素中的next屬性指向當(dāng)前空間的地址。以鏈表節(jié)點(diǎn)的形式插入到該空間。 當(dāng)插入的時(shí)候我們只需要通過散列函數(shù)計(jì)算出對應(yīng)的散列槽位，將其插入到對應(yīng)鏈表中即可。

1.3.3 負(fù)載因子loadFactory與rehash

我們可以使用負(fù)載因子來衡量散列表的“健康狀況”。

散列表的負(fù)載因子 = 填入表中的元素個(gè)數(shù) ÷ 散列表的長度（數(shù)組的長度）

散列表的負(fù)載因子越大，代表空閑位置越少，沖突也就越多，散列表的性能會(huì)下降。對于散列表來說，負(fù)載因子過大或過小都不好，因?yàn)樨?fù)載因子是決定散列表的數(shù)據(jù)密度。

負(fù)載因子過大，散列表的數(shù)據(jù)密度就會(huì)高，鏈表的長度就會(huì)長，導(dǎo)致散列表的性能下降。負(fù)載因子過小，散列表很容易就會(huì)觸發(fā)擴(kuò)容，則會(huì)造成內(nèi)存不能合理使用，從而形成內(nèi)存浪費(fèi)。

因此我們?yōu)榱吮ＷC負(fù)載因子維持在一個(gè)合理的范圍內(nèi)，要對散列表的大小進(jìn)行收縮或拓展，即rehash。

散列表的rehash過程類似于數(shù)組的擴(kuò)容，但是相比要多出來數(shù)據(jù)的從新排列，更換空間位置等復(fù)雜操作。

1.3.4 開放尋址法與鏈表比較

對于開放尋址解決沖突的散列表，由于數(shù)據(jù)都存儲(chǔ)在數(shù)組中，因此可以有效的利用CPU緩存加快查詢速度（數(shù)組占用內(nèi)存中連續(xù)的空間）。但是刪除數(shù)據(jù)時(shí)比較麻煩，需要標(biāo)記已刪除的元素為deleted。而且開放尋址法中，所有數(shù)據(jù)都存儲(chǔ)在一個(gè)數(shù)組中，比起鏈表來說，沖突的代價(jià)更高，*（每次都要遍歷數(shù)組，遍歷到數(shù)組尾部時(shí)再轉(zhuǎn)向數(shù)組頭部開始遍歷，仍沒有找到位置便需要擴(kuò)容。）*所以使用開放尋址法解決沖突的散列表，負(fù)載因子的上限不能太大，也就是數(shù)據(jù)的密度不能太高。將導(dǎo)致比鏈表法更浪費(fèi)內(nèi)存空間。

對于鏈表法解決沖突的散列表，堆內(nèi)存的利用率要比開放尋址法要高。因?yàn)殒湵斫Y(jié)點(diǎn)可以在需要的時(shí)候再創(chuàng)建，并不需要像開放尋址法那樣提前準(zhǔn)備好內(nèi)存空間。鏈表法比起開放尋址法對裝載因子的容忍度更高。開放尋址法只能適用裝載因子小于1的情況。接近1時(shí)，就可能會(huì)有大量的散列沖突，性能會(huì)下降很多。但是對于鏈表法，只要散列函數(shù)的值隨機(jī)均勻，即便裝載因子變成1，也就是鏈表變長了而已，雖然查找效率要有所下降，但是比起開放尋址的線性探測順序查找還是要快的很多。但是鏈表要存儲(chǔ)指針，所以對于比較小的存儲(chǔ)對象，是比較消耗內(nèi)存的，性價(jià)比并不高。而且鏈表中的節(jié)點(diǎn)是零散分布在內(nèi)存中，不是連續(xù)的，所以對CPU緩存不是很友好，這對于執(zhí)行效率有一定的影響，但是鏈表中的每個(gè)節(jié)點(diǎn)有相互連接，所以影響不大。

到此這篇關(guān)于C語言數(shù)據(jù)結(jié)構(gòu)之Hash散列表的文章就介紹到這了,更多相關(guān)Hash散列表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論