基礎概念

散列技術是在記錄的存儲位置和它的關鍵字之間建立一個確定的對應關系f，使得每個關鍵字key對應一個存儲位置f(key).這里對應關系f稱為散列函數，又稱為哈希（Hash)函數。

采用散列技術將記錄存儲在一塊連續的存儲空間中，這塊連續存儲空間稱為散列表或哈希表（Hash table)。

散列技術既是一種存儲方法，也是一種查找方法。

散列技術最適合的求解問題是查找與給定值相等的記錄。不適合一對多的查找，也不適合范圍查找。

散列技術中的兩個關鍵問題：

設計一個簡單、均勻、存儲利用率高的散列函數； 沖突

散列查找中，時常會碰到兩個關鍵字key1!=key2,但是卻有f(key1)==f(key2),這種現象稱為沖突（collision），并把key1和key2稱為這個散列函數的同義詞（synonym)。

幾種散列函數的構造方法

直接定址法

取關鍵字的某個線性函數值為散列地址，即

?????????????? f(key)=a×key+b?????????? (a,b為常數）??????????????

優點：簡單、均勻、不會產生沖突；

確定：需事先知道關鍵字的分布情況，適合查找表比較小且連續的情況。

不常用。

數字分析法

抽取關鍵字的一部分來計算散列位置的方法，也可以對抽取出來的數字再進行反轉，循環移位，甚至前兩數與后兩數疊加等方法。適合處理關鍵字比較大的情況，如果事先知道關鍵字的分布且關鍵字的若干位分布較均勻，就可以考慮用這個方法。

平方取中法

例如：關鍵字1234，其平方值為1522756，取其中間三位就是227，用作散列地址。

平方取中適用于不知道關鍵字的分布，而位數又不是很大的情況。

折疊法

折疊法是將關鍵字從左到右分割成位數相等的幾部分（注意最后一部分位數不夠時可以短些），然后將這幾部分疊加求和，并按散列表表長，取后幾位作為散列地址。

例如：關鍵字9876543210，散列表表長為三位，我們將它分為四組，987|654|321|0，然后將他們疊加求和987+654+321+0=1962，再求后3位得到散列地址為962.

折疊法事先不需要知道關鍵字的分布，適合關鍵字位數較多的情況。

除留余數法

此法為最常用的構造散列函數方法，對于散列表長為m的散列函數公式為：

??????????????? f(key) = key mod p?????? (p<=m)???????????????????

根據經驗，若散列表表長為m，通常p為小于或等于表長（最好接近m）的最小質數或不包含小于20質因子的合數。

隨機數法

取關鍵字的隨機函數值為它的散列地址，f(key)=random(key).

當關鍵字的長度不等時，采用這個方法構造散列函數是比較合適的。

設計散列函數需要考慮的因素：

計算散列地址所需的事件 關鍵字的長度 散列表的大小 關鍵字的分布情況 記錄查找的頻率

處理散列沖突的方法

開放定址法

開放定址法就是一旦發生了沖突,就去尋找下一個空的散列地址,只要散列表足夠大,空的散列地址總能找到,并將記錄存入.公式:

????????????? fi(key)=(f(key)+di) MOD m???? (di=1,2,3,……,m-1)???????????

這種解決沖突的開放定址法稱為線性探測法。

當表中第i，i+1，i+2位置上已填有記錄時，下一哈希地址為i，i+1，i+2和i+3的記錄都將填入i+3的位置。這種第一個哈希地址不同的記錄爭奪同一個后繼哈希地址的現象成為“聚集”(堆積）。 堆積使得需要不斷處理沖突。可以改進di=1,-1,4,-4,9,-9,……,q*q,-q*q,(q<=m/2);正負號相間等于是可以雙向尋找可能的空位置，增加平方運算的目的是為了不讓關鍵字都聚集在某一塊區域，這種方法稱為二次探測法。

另外，在沖突時，對于位移量di可以采用偽隨機函數計算得到，這種方法稱之為隨即探測法。

再散列函數法

事先準備多個散列函數

??????????????????????????? fi(key) = RHi(key)?????? (i=1,2,…k)?????????????????????????

這里RHi就是不同的散列函數，每當發生散列地址沖突時，就換一個散列函數計算，相信總會有一個可以把沖突解決掉。

鏈地址法

將所有關鍵字為同義詞的記錄存儲在一個單鏈表中，這種表稱為同義詞子表，在散列表中只存儲所有同義詞子表的頭指針。

特點
（1）不產生“聚集”現象，故ASL較短；
（2）結點空間動態申請，適合于表前無法確定表長的情況；
（3）刪除結點的操作易于實現；
（4）α=n/m較大時，所用空間比開放地址法多。但α越大，
開放地址法所需探查次數越多。

公共溢出區法

將所有沖突的關鍵字發那個在一個公共的溢出區來存放，當散列查找不成功時，則到溢出表去進行順序查找。

散列表查找算法實現

/*代碼源自《大話數據結構》一書*/ #include "stdio.h" #include "stdlib.h" #include "io.h" #include "math.h" #include "time.h"#define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0#define MAXSIZE 100 /* 存儲空間初始分配量 */#define SUCCESS 1 #define UNSUCCESS 0 #define HASHSIZE 12 /* 定義散列表長為數組的長度 */ #define NULLKEY -32768 typedef int Status; /* Status是函數的類型,其值是函數結果狀態代碼，如OK等 */ typedef struct {int *elem; /* 數據元素存儲基址，動態分配數組 */int count; /* 當前數據元素個數 */ }HashTable;int m=0; /* 散列表表長，全局變量 *//* 初始化散列表 */ Status InitHashTable(HashTable *H) {int i;m=HASHSIZE;H->count=m;H->elem=(int *)malloc(m*sizeof(int));for(i=0;i<m;i++)H->elem[i]=NULLKEY; return OK; }/* 散列函數 */ int Hash(int key) {return key % m; /* 除留余數法 */ }/* 插入關鍵字進散列表 */ void InsertHash(HashTable *H,int key) {int addr = Hash(key); /* 求散列地址 */while (H->elem[addr] != NULLKEY) /* 如果不為空，則沖突 */{addr = (addr+1) % m; /* 開放定址法的線性探測 */}H->elem[addr] = key; /* 直到有空位后插入關鍵字 */ }/* 散列表查找關鍵字 */ Status SearchHash(HashTable H,int key,int *addr) {*addr = Hash(key); /* 求散列地址 */while(H.elem[*addr] != key) /* 如果不為空，則沖突 */{*addr = (*addr+1) % m; /* 開放定址法的線性探測 */if (H.elem[*addr] == NULLKEY || *addr == Hash(key)) /* 如果循環回到原點 */return UNSUCCESS; /* 則說明關鍵字不存在 */}return SUCCESS; }int main() {int arr[HASHSIZE]={12,67,56,16,25,37,22,29,15,47,48,34};int i,p,key,result;HashTable H;key=39;InitHashTable(&H);for(i=0;i<m;i++)InsertHash(&H,arr[i]);result=SearchHash(H,key,&p);if (result)printf("查找 %d 的地址為：%d \n",key,p);elseprintf("查找 %d 失敗。\n",key);for(i=0;i<m;i++){key=arr[i];SearchHash(H,key,&p);printf("查找 %d 的地址為：%d \n",key,p);}return 0; }

散列表查找性能分析

如果沒有沖突，散列查找的時間復雜度為O(1).

影響散列查找的平均查找長度因素

1.散列函數是否均勻

2.處理沖突的方法

3.散列表的裝填因子

所謂裝填因子α=填入表中的記錄個數/散列表長度。α越大，產生沖突的可能性就越大。

轉載于:https://www.cnblogs.com/xingchenfeng/p/3714783.html

總結

以上是生活随笔為你收集整理的查找 之 散列表查找（哈希表）的全部內容，希望文章能夠幫你解決所遇到的問題。

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