寫在前面：博主是一位普普通通的19屆雙非軟工在讀生，平時最大的愛好就是聽聽歌，逛逛B站。博主很喜歡的一句話花開堪折直須折，莫待無花空折枝：博主的理解是頭一次為人，就應該做自己想做的事，做自己不后悔的事，做自己以后不會留有遺憾的事，做自己覺得有意義的事，不浪費這大好的青春年華。博主寫博客目的是記錄所學到的知識并方便自己復習，在記錄知識的同時獲得部分瀏覽量，得到更多人的認可，滿足小小的成就感，同時在寫博客的途中結交更多志同道合的朋友，讓自己在技術的路上并不孤單。

目錄:
1.哈希表的構建
2.哈希函數的構造
???? ?? 直接定址法
???? ?? 數字分析法
???? ?? 平方取中法
???? ?? 折疊法
???? ?? 除留余數法
???? ?? 隨機數法
???? ?? 哈希函數的選擇
3.哈希沖突的解決方法
???? ?? 開放地址法
???? ?? 再哈希法
???? ?? 鏈地址法
???? ?? 建立一個公共溢出區
4.哈希查找算法
???? ?? 哈希查找算法思想
???? ?? 哈希查找算法開放地址法(C語言完整代碼實現)
5.哈希查找效率分析

1.哈希表的構建

哈希表可以通過關鍵字直接找到數據的存儲位置，不需要進行任何的比較，其查找的效率相較于前面所介紹的查找算法是更高的

在初中的數學課本中學習過函數的相關知識，給定一個 x，通過一個數學公式，只需要將 x 的值帶入公式就可以求出一個新的值 y。哈希表的建立同函數類似，把函數中的 x 用查找記錄時使用的關鍵字來代替，然后將關鍵字的值帶入一個精心設計的公式中，就可以求出一個值，用這個值來表示記錄存儲的哈希地址即：

數據的哈希地址=f（關鍵字的值）

哈希地址只是表示在查找表中的存儲位置，而不是實際的物理存儲位置。f（）是一個函數，通過這個函數可以快速求出該關鍵字對應的的數據的哈希地址，稱之為“哈希函數”。

例如，這里有一個電話簿（查找表），電話簿中有 4 個人的聯系方式：

張三 13912345678
李四 15823457890
王五 13409872338
趙六 13805834722

假如想查找李四的電話號碼，對于一般的查找方式最先想到的是從頭遍歷，一一比較。而如果將電話簿構建成一張哈希表，可以直接通過名字“李四”直接找到電話號碼在表中的位置。

在構建哈希表時，最重要的是哈希函數的設計。例如設計電話簿案例中的哈希函數為：每個名字的姓的首字母的 ASCII 值即為對應的電話號碼的存儲位置。這時會發現，張三和趙六兩個關鍵字的姓的首字母都是 Z ，最終求出的電話號碼的存儲位置相同，這種現象稱為沖突。在設計哈希函數時，要盡量地避免沖突現象的發生。

對于哈希表而言，沖突只能盡可能地少，無法完全避免。

2.哈希函數的構建

常用的哈希函數的構造方法有 6 種：直接定址法、數字分析法、平方取中法、折疊法、除留余數法和隨機數法。

2.1直接地址法

其哈希函數為一次函數，即以下兩種形式：

H（key）= key 或者 H（key）=a * key + b

其中 H（key）表示關鍵字為 key 對應的哈希地址，a 和 b 都為常數。

例如有一個從 1 歲到 100 歲的人口數字統計表，如下圖所示：

假設其哈希函數為第一種形式，其關鍵字的值表示最終的存儲位置。若需要查找年齡為 25 歲的人口數量，將年齡 25 帶入哈希函數中，直接求得其對應的哈希地址為 25（求得的哈希地址表示該記錄的位置在查找表的第 25 位）。

2.2數字分析法

如果關鍵字由多位字符或者數字組成，就可以考慮抽取其中的 2 位或者多位作為該關鍵字對應的哈希地址，在取法上盡量選擇變化較多的位，避免沖突發生。

例如下表中列舉的是一部分關鍵字，每個關鍵字都是有 8 位十進制數組成：

通過分析關鍵字的構成，很明顯可以看到關鍵字的第 1 位和第 2 位都是固定不變的，而第 3 位不是數字 3 就是 4，最后一位只可能取 2、7 和 5，只有中間的 4 位其取值近似隨機，所以為了避免沖突，可以從 4 位中任意選取 2 位作為其哈希地址。

2.3平方取中法

是對關鍵字做平方操作，取中間得幾位作為哈希地址。此方法也是比較常用的構造哈希函數的方法。
例如關鍵字序列為{421，423，436}，對各個關鍵字進行平方后的結果為{177241，178929，190096}，則可以取中間的兩位{72，89，00}作為其哈希地址。

2.4折疊法

是將關鍵字分割成位數相同的幾部分（最后一部分的位數可以不同），然后取這幾部分的疊加和（舍去進位）作為哈希地址。此方法適合關鍵字位數較多的情況。

例如，在圖書館中圖書都是以一個 10 位的十進制數字為關鍵字進行編號的，若對其查找表建立哈希表時，就可以使用折疊法。

若某書的編號為：0-442-20586-4，分割方式如下圖中所示，在對其進行折疊時有兩種方式：一種是移位折疊，另一種是間界折疊：

移位折疊是將分割后的每一小部分，按照其最低位進行對齊，然后相加,如圖a

間界折疊是從一端向另一端沿分割線來回折疊，如圖 b

2.5除留余數法

若已知整個哈希表的最大長度 m，可以取一個不大于 m 的數 p，然后對該關鍵字 key 做取余運算，即：

H（key）= key % p。

在此方法中，對于 p 的取值非常重要，由經驗得知 p 可以為不大于 m 的質數或者不包含小于 20 的質因數的合數。

2.6隨機數法

是取關鍵字的一個隨機函數值作為它的哈希地址，即：H（key）=random（key），此方法適用于關鍵字長度不等的情況。

這里的隨機函數其實是偽隨機函數，隨機函數是即使每次給定的 key 相同，但是 H（key）都是不同；而偽隨機函數正好相反，每個 key 都對應的是固定的 H（key）

2.7構建哈希表的選擇規則

• 關鍵字的長度。如果長度不等，就選用隨機數法。如果關鍵字位數較多，就選用折疊法或者數字
• 分析法；反之如果位數較短，可以考慮平方取中法；
• 哈希表的大小。如果大小已知，可以選用除留余數法；
• 關鍵字的分布情況；
• 查找表的查找頻率；
• 計算哈希函數所需的時間（包括硬件指令的因素）

3.哈希沖突的解決方法

3.1開放定址法

H（key）=（H（key）+ d）MOD m（其中 m 為哈希表的表長，d 為一個增量）

當得出的哈希地址產生沖突時，選取以下 3 種方法中的一種獲取 d 的值，然后繼續計算，直到計算出的哈希地址不在沖突為止，這 3 種方法為：

線性探測法：d=1，2，3，…，m-1

二次探測法：d=12，-12，22，-22，32，…

偽隨機數探測法：d=偽隨機數

例如，在長度為 11 的哈希表中已填寫好 17、60 和 29 這 3 個數據（如圖 （a） 所示），其中采用的哈希函數為：H（key）=key MOD 11，現有第 4 個數據 38 ，當通過哈希函數求得的哈希地址為 5，與 60 沖突，則分別采用以上 3 種方式求得插入位置如圖 （b）所示：

在線性探測法中，當遇到沖突時，從發生沖突位置起，每次 +1，向右探測，直到有空閑的位置為止；二次探測法中，從發生沖突的位置起，按照 +12，-12，+22，…如此探測，直到有空閑的位置；偽隨機探測，每次加上一個隨機數，直到探測到空閑位置結束。

3.2再哈希法

當通過哈希函數求得的哈希地址同其他關鍵字產生沖突時，使用另一個哈希函數計算，直到沖突不再發生。

3.3鏈地址法

將所有產生沖突的關鍵字所對應的數據全部存儲在同一個線性鏈表中。例如有一組關鍵字為{19,14,23,01,68,20,84,27,55,11,10,79}，其哈希函數為：H(key)=key MOD 13，使用鏈地址法所構建的哈希表如圖所示：

3.4建立一個公共溢出區

建立兩張表，一張為基本表，另一張為溢出表。基本表存儲沒有發生沖突的數據，當關鍵字由哈希函數生成的哈希地址產生沖突時，就將數據填入溢出表。

4.哈希查找算法

4.1哈希查找算法思想

在哈希表中進行查找的操作同哈希表的構建過程類似，其具體實現思路為：對于給定的關鍵字 K，將其帶入哈希函數中，求得與 該關鍵字對應的數據的哈希地址，如果該地址中沒有數據，則證明該查找表中沒有存儲該數據，查找失敗：如果哈希地址中有數 據，就需要做進一步的證明（排除沖突的影響），找到該數據對應的關鍵字同 K 進行比對，如果相等，則查找成功；反之，如 果不相等，說明在構造哈希表時發生了沖突，需要根據構造表時設定的處理沖突的方法找到下一個地址，同地址中的數據進行比 對，直至遇到地址中數據為 NULL（說明查找失敗），或者比對成功。

4.2哈希查找算法開放地址法(C語言完整代碼實現)

#include "stdio.h" #include "stdlib.h" #define HASHSIZE 7 //定義散列表長為數組的長度 #define NULLKEY -1 typedef struct{int *elem;//數據元素存儲地址，動態分配數組int count; //當前數據元素個數 }HashTable; //對哈希表進行初始化 void Init(HashTable *hashTable){int i;hashTable->elem= (int *)malloc(HASHSIZE*sizeof(int));hashTable->count=HASHSIZE;for (i=0;i<HASHSIZE;i++){hashTable->elem[i]=NULLKEY;} } //哈希函數(除留余數法) int Hash(int data){ return data%HASHSIZE; } //哈希表的插入函數，可用于構造哈希表 void Insert(HashTable *hashTable,int data){int hashAddress=Hash(data); //求哈希地址 //發生沖突while(hashTable->elem[hashAddress]!=NULLKEY){ //利用開放定址法解決沖突hashAddress=(++hashAddress)%HASHSIZE;}hashTable->elem[hashAddress]=data; } //哈希表的查找算法 int Search(HashTable *hashTable,int data){int hashAddress=Hash(data); //求哈希地址while(hashTable->elem[hashAddress]!=data){//發生沖突 //利用開放定址法解決沖突hashAddress=(++hashAddress)%HASHSIZE; //如果查找到的地址中數據為 NULL，或者經過一圈的遍歷回到原位置，則查找失敗if (hashTable->elem[hashAddress]==NULLKEY||hashAddress==Hash(data)){return -1;}}return hashAddress; } int main(){int i,result;HashTable hashTable;int arr[HASHSIZE]={13,29,27,28,26,30,38}; //初始化哈希表Init(&hashTable); //利用插入函數構造哈希表for (i=0;i<HASHSIZE;i++){Insert(&hashTable,arr[i]);} //調用查找算法result= Search(&hashTable,29);if (result==-1)printf("查找失敗"); else printf("29 在哈希表中的位置是:%d",result+1); return 0; }

5.哈希查找效率分析

在構造哈希表的過程中，由于沖突的產生，使得哈希表的查找算法仍然會涉及到比較的過程，因此對于哈希表的查找效率仍需以 平均查找長度來衡量。

在哈希表的查找過程中需和給定值進行比較的關鍵字的個數取決于以下 3 個因素：

哈希函數：哈希函數的“好壞”取決于影響出現沖突的頻繁程度。但是一般情況下，哈希函數相比于后兩種的影響，可以 忽略不計。

處理沖突的方式：對于同一組關鍵字，設定相同的哈希函數，使用不同的處理沖突的方式得到的哈希表是不同的，表的平 均查找長度也不同。

哈希表的裝填因子：在一般情況下，當處理沖突的方式相同的情況下，其平均查找長度取決于哈希表的裝滿程度：裝的越滿，插入數據時越有可能發生沖突；反之則越小。

裝填因子=哈希表中數據的個數/哈希表的長度用字符 α 表示（是數學符號，而不是字符 a）。裝填因子越小，表 示哈希表中空閑的位置就越多

• 用字符 α 表示（是數學符號，而不是字符 a）。裝填因子越小，表 示哈希表中空閑的位置就越多
• 其查找成功的平均查找長度約為：-1/α * ln?(1-α) 其查找不成功的平均查找長度約為：1/(1-α)

通過公式可以看到，哈希表的查找效率只同裝填因子有關，而同哈希表中的數據的個數無關，所以在選用哈希表做查找操作時， 選擇一個合適的裝填因子是非常有必要的。

本篇博客轉載C語言中文網

總結

以上是生活随笔為你收集整理的一文搞定哈希(六种构建、四种冲突解决方法、查找算法总结)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。