哈希表

• 什麼是哈希表
• • 為什麼需要哈希呢？
  • • 查詢數組中資料
    • 哈希表存儲
    • 查詢哈希表中的資料
• 哈希沖突的解決辦法
• • 鍊位址法
  • 開放位址法(開放尋址法)
  • 公共溢出區法
• 哈希函數的構造方法
• • 直接定制法
  • 數字分析法
  • 平方取中法
  • 折疊法
  • 除留餘數法
• 哈希表的查找
• 哈希表的删除

什麼是哈希表

• 哈希表(Hash Table)，也可以稱為散清單或者 Hash 表。
• 哈希表用的是數組支援按照下标通路資料的特性，是以哈希表其實就是數組的一種擴充，由數組演化而來。

• 是根據鍵（Key）而直接通路在記憶體存儲位置的資料結構。

  過程：它通過映射函數 輸入key 輸出數組下标的方式，将所需查詢的資料映射到表中一個位置來通路記錄，這加快了查找速度。這個映射函數稱做哈希函數，存放記錄的數組稱做哈希表

為什麼需要哈希呢？

連結清單和哈希表做對比

比如 現在我們将每個人的性别作為資料進行存儲，鍵為人名，值為對應的性别，其中 M 表示性别為男，F 表示性别為女。

查詢數組中資料

為了和哈希表進行對比，我們先将這些資料存儲在數組中。

此處準備了6個箱子（即長度為6的數組）來存儲資料，假設我們需要查詢 Ally 的性别，由于不知道 Ally 的資料存儲在哪個箱子裡，是以隻能從頭開始查詢，這個操作便叫作線性查找。一般來說，我們可以把鍵當成資料的辨別符，把值當成資料的内容。

從 0 号箱子開始查找，發現 0 号箱子中存儲的鍵是 Joe 而不是 Ally，是以接着查找 1 号箱子。

哦豁，1 号箱子中的也不是 Ally，沒辦法，隻能接着往下找。

有點小糟糕，2 号、3 号箱子中的也都不是 Ally。

功夫不負有心人，當我們查找到 4 号箱子的時候，發現其中資料的鍵為 Ally，把鍵對應的值取出，我們就知道 Ally 的性别為女（F）。

哈希表存儲

通過上面的查找過程，我們發現資料量越多，線性查找耗費的時間就越長。由此可知：由于資料的查詢較為耗時，是以此處并不适合使用數組來存儲資料。

但使用哈希表便可以解決這個問題，首先準備好數組，這次我們用 5 個箱子的數組來存儲資料。

嘗試把 Joe 存進去，使用哈希函數（Hash）計算 Joe 的鍵，也就是字元串 Joe 的哈希值，比如得到的結果為4928。

将得到的哈希值除以數組的長度 5，求得其餘數，這樣的求餘運算叫作mod運算，此處mod運算的結果為3。

是以，我們将 Joe 的資料存進數組的 3 号箱子中，重複前面的操作，将其他資料也存進數組中。

Sue 鍵的哈希值為 7291, mod 5 的結果為 1，将 Sue 的資料存進 1 号箱中。

Dan 鍵的哈希值為 1539, mod 5 的結果為 4，将 Dan 的資料存進 4 号箱中。

Nell 鍵的哈希值為 6276, mod 5 的結果為 1，本應将其存進數組的 1 号箱中，但此時 1 号箱中已經存儲了 Sue 的資料，這種存儲位置重複了的情況便叫作沖突（哈希沖突）。

遇到這種情況，其中一種方法用連結清單法，用連結清單在已有資料的後面繼續存儲新的資料。

Ally 鍵的哈希值為 9143, mod 5 的結果為 3，本應将其存儲在數組的 3 号箱中，但 3 号箱中已經有了 Joe 的資料，是以使用連結清單，在其後面存儲 Ally 的資料。

Bob 鍵的哈希值為 5278, mod 5 的結果為 3，本應将其存儲在數組的 3 号箱中，但 3 号箱中已經有了 Joe 和 Ally 的資料，是以使用連結清單，在 Ally 的後面繼續存儲 Bob 的資料。

像這樣存儲完所有資料，哈希表也就制作完成了。

查詢哈希表中的資料

接下來講解資料的查詢方法，假設我們要查詢 Dan 的性别。

為了知道 Dan 存儲在哪個箱子裡，首先需要算出 Dan 鍵的哈希值，然後對其進行 mod 運算，最後得到的結果為 4，于是我們知道了它存儲在 4 号箱中。

檢視 4 号箱可知，其中的資料的鍵與 Dan 一緻，于是取出對應的值，由此我們便知道了 Dan 的性别為男（M）。

那麼，想要查詢 Ally 的性别時該怎麼做呢？為了找到它的存儲位置，先要算出 Ally 鍵的哈希值，再對其進行 mod 運算，最終得到的結果為 3。

然而 3 号箱中資料的鍵是 Joe 而不是 Ally，此時便需要對 Joe 所在的連結清單進行線性查找。

于是我們找到了鍵為 Ally 的資料，取出其對應的值，便知道了 Ally 的性别為女（F）。

哈希沖突的解決辦法

鍊位址法

可以利用連結清單在存儲資料後面加一個指針，指向後面沖突的資料來解決沖突，這種方法被稱為連結清單法，也被稱為鍊位址法。

有一組資料

19 01 23 14 55 68 11 86 37要存儲在表長11的數組中，其中H（key）=key MOD 11

開放位址法(開放尋址法)

這種方法是指當沖突發生時，立刻計算出一個候補位址（數組上的位置）并将資料存進去。如果仍然有沖突，便繼續計算下一個候補位址，直到有空位址為止，可以通過多次使用哈希函數或線性探測法等方法計算候補位址。

首先有一個H（key）的哈希函數

有三種取法

1）線性探測再散列

2）平方探測再散列

3）随機探測在散列（雙探測再散列）

三種開放定址法解決沖突方案的例子

有一組資料

19 01 23 14 55 68 11 86 37要存儲在表長11的數組中，其中H（key）=key MOD 11

那麼按照上面三種解決沖突的方法，存儲過程如下：

（表格解釋：從前向後插入資料，如果插入位置已經占用，發生沖突，沖突的另起一行，計算位址，直到位址可用，後面沖突的繼續向下另起一行。最終結果取最上面的資料（因為是最“占座”的資料））

線性探測再散列

我們取di=1，即沖突後存儲在沖突後一個位置，如果仍然沖突繼續向後

平方探測再散列

随機探測在散列（雙探測再散列） 發生沖突後 H（key）‘=(H(key)+di)MOD m 在該例子中 H（key）=key MOD 11 我們取di=key MOD 10 +1 則有如下結果：

公共溢出區法

建立一個特殊存儲空間，專門存放沖突的資料。此種方法适用于資料和沖突較少的情況。

4.再散列法

準備若幹個hash函數，如果使用第一個hash函數發生了沖突，就使用第二個hash函數，第二個也沖突，使用第三個……

重點了解一下開放定制法和鍊位址法

哈希函數的構造方法

直接定制法

數字分析法

平方取中法

折疊法

除留餘數法

H（key）=key MOD p （p<=m m為表長）

很明顯，如何選取p是個關鍵問題。

使用舉例

比如我們存儲3 6 9，那麼p就不能取3

因為 3 MOD 3 == 6 MOD 3 == 9 MOD 3

p應為不大于m的質數或是不含20以下的質因子的合數，這樣可以減少位址的重複（沖突）

比如key = 7，39，18，24，33，21時取表長m為9 p為7 那麼存儲如下

index	1	2	3	4	5	6	7	8
key	7	21（沖突後移）	24	39	18（沖突後移）	33（沖突後移）

随機數法 H（key） =Random（key） 取關鍵字的随機函數值為它的散列位址

哈希表的查找

查找過程和造表過程一緻，假設采用開放定址法處理沖突，則查找過程為：

對于給定的key，計算hash位址index = H（key）

如果數組arr【index】的值為空 則查找不成功

如果數組arr【index】== key 則查找成功

否則 使用沖突解決方法求下一個位址，直到arr【index】== key或者 arr【index】==null

哈希表的删除

首先鍊位址法是可以直接删除元素的，但是開放定址法是不行的，拿前面的雙探測再散列來說，假如我們删除了元素1，将其位置置空，那 23就永遠找不到了。正确做法應該是删除之後置入一個原來不存在的資料，比如-1

備注：

借鑒了：

https://blog.csdn.net/u011109881/article/details/80379505

https://zhuanlan.zhihu.com/p/107326081