一、散列表

1.1 散列表

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

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

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

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

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

當我們按照鍵值（學號）查找時，只需要再次計算出索引下標，然后取出相應數(shù)據即可。

以上便是散列思想。

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

1.2 散列函數(shù)

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

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

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

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

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

在散列表中散列函數(shù)不應設計的太復雜，不然太復雜的散列函數(shù)會造成更多的性能消耗，結果就適得其反了。

1.3 散列沖突

就像圖上所表達的一樣，不同的key通過散列函數(shù)計算出來的hash值相同，造成了這兩個數(shù)據都需要存儲在這個同一個下標(內存空間)上。

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

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

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

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

1.3.1 開放尋址法

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

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

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

好，雖然使用開放尋址法完成了鍵值對的存儲和查找，但是對刪除操作稍微有些特別，不能單純的把要刪除的元素設置為空。因為在查找的時候，我們通過線性探測法就會按順序向后面的內存空間（下標）一個一個的找，直到找到對應的value或空為止，但是如果這時候碰到一個內存空間（下標）中的值是空，而這個空位置是我們刪除了其他元素后置為空的，就導致這個查找算法失效。 我們可以將刪除的元素，特殊的標記為deleted。當線性探測查找的時候，遇到標記為deleted的空間并不是停下來，而是繼續(xù)向下探測。

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

1.3.2 鏈表法

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

1.3.3 負載因子loadFactory與rehash

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

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

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

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

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

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

1.3.4 開放尋址法與鏈表比較

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

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

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

最新評論