基礎(chǔ)概念

散列技術(shù)是在記錄的存儲(chǔ)位置和它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系f，使得每個(gè)關(guān)鍵字key對(duì)應(yīng)一個(gè)存儲(chǔ)位置f(key).這里對(duì)應(yīng)關(guān)系f稱為散列函數(shù)，又稱為哈希（Hash)函數(shù)。

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

散列技術(shù)既是一種存儲(chǔ)方法，也是一種查找方法。

散列技術(shù)最適合的求解問(wèn)題是查找與給定值相等的記錄。不適合一對(duì)多的查找，也不適合范圍查找。

散列技術(shù)中的兩個(gè)關(guān)鍵問(wèn)題：

設(shè)計(jì)一個(gè)簡(jiǎn)單、均勻、存儲(chǔ)利用率高的散列函數(shù)； 沖突

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

幾種散列函數(shù)的構(gòu)造方法

直接定址法

取關(guān)鍵字的某個(gè)線性函數(shù)值為散列地址，即

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

優(yōu)點(diǎn)：簡(jiǎn)單、均勻、不會(huì)產(chǎn)生沖突；

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

不常用。

數(shù)字分析法

抽取關(guān)鍵字的一部分來(lái)計(jì)算散列位置的方法，也可以對(duì)抽取出來(lái)的數(shù)字再進(jìn)行反轉(zhuǎn)，循環(huán)移位，甚至前兩數(shù)與后兩數(shù)疊加等方法。適合處理關(guān)鍵字比較大的情況，如果事先知道關(guān)鍵字的分布且關(guān)鍵字的若干位分布較均勻，就可以考慮用這個(gè)方法。

平方取中法

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

平方取中適用于不知道關(guān)鍵字的分布，而位數(shù)又不是很大的情況。

折疊法

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

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

折疊法事先不需要知道關(guān)鍵字的分布，適合關(guān)鍵字位數(shù)較多的情況。

除留余數(shù)法

此法為最常用的構(gòu)造散列函數(shù)方法，對(duì)于散列表長(zhǎng)為m的散列函數(shù)公式為：

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

根據(jù)經(jīng)驗(yàn)，若散列表表長(zhǎng)為m，通常p為小于或等于表長(zhǎng)（最好接近m）的最小質(zhì)數(shù)或不包含小于20質(zhì)因子的合數(shù)。

隨機(jī)數(shù)法

取關(guān)鍵字的隨機(jī)函數(shù)值為它的散列地址，f(key)=random(key).

當(dāng)關(guān)鍵字的長(zhǎng)度不等時(shí)，采用這個(gè)方法構(gòu)造散列函數(shù)是比較合適的。

設(shè)計(jì)散列函數(shù)需要考慮的因素：

計(jì)算散列地址所需的事件 關(guān)鍵字的長(zhǎng)度 散列表的大小 關(guān)鍵字的分布情況 記錄查找的頻率

處理散列沖突的方法

開(kāi)放定址法

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

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

這種解決沖突的開(kāi)放定址法稱為線性探測(cè)法。

當(dāng)表中第i，i+1，i+2位置上已填有記錄時(shí)，下一哈希地址為i，i+1，i+2和i+3的記錄都將填入i+3的位置。這種第一個(gè)哈希地址不同的記錄爭(zhēng)奪同一個(gè)后繼哈希地址的現(xiàn)象成為“聚集”(堆積）。 堆積使得需要不斷處理沖突。可以改進(jìn)di=1,-1,4,-4,9,-9,……,q*q,-q*q,(q<=m/2);正負(fù)號(hào)相間等于是可以雙向?qū)ふ铱赡艿目瘴恢?#xff0c;增加平方運(yùn)算的目的是為了不讓關(guān)鍵字都聚集在某一塊區(qū)域，這種方法稱為二次探測(cè)法。

另外，在沖突時(shí)，對(duì)于位移量di可以采用偽隨機(jī)函數(shù)計(jì)算得到，這種方法稱之為隨即探測(cè)法。

再散列函數(shù)法

事先準(zhǔn)備多個(gè)散列函數(shù)

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

這里RHi就是不同的散列函數(shù)，每當(dāng)發(fā)生散列地址沖突時(shí)，就換一個(gè)散列函數(shù)計(jì)算，相信總會(huì)有一個(gè)可以把沖突解決掉。

鏈地址法

將所有關(guān)鍵字為同義詞的記錄存儲(chǔ)在一個(gè)單鏈表中，這種表稱為同義詞子表，在散列表中只存儲(chǔ)所有同義詞子表的頭指針。

特點(diǎn)
（1）不產(chǎn)生“聚集”現(xiàn)象，故ASL較短；
（2）結(jié)點(diǎn)空間動(dòng)態(tài)申請(qǐng)，適合于表前無(wú)法確定表長(zhǎng)的情況；
（3）刪除結(jié)點(diǎn)的操作易于實(shí)現(xiàn)；
（4）α=n/m較大時(shí)，所用空間比開(kāi)放地址法多。但α越大，
開(kāi)放地址法所需探查次數(shù)越多。

公共溢出區(qū)法

將所有沖突的關(guān)鍵字發(fā)那個(gè)在一個(gè)公共的溢出區(qū)來(lái)存放，當(dāng)散列查找不成功時(shí)，則到溢出表去進(jìn)行順序查找。

散列表查找算法實(shí)現(xiàn)

/*代碼源自《大話數(shù)據(jù)結(jié)構(gòu)》一書(shū)*/ #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 /* 存儲(chǔ)空間初始分配量 */#define SUCCESS 1 #define UNSUCCESS 0 #define HASHSIZE 12 /* 定義散列表長(zhǎng)為數(shù)組的長(zhǎng)度 */ #define NULLKEY -32768 typedef int Status; /* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等 */ typedef struct {int *elem; /* 數(shù)據(jù)元素存儲(chǔ)基址，動(dòng)態(tài)分配數(shù)組 */int count; /* 當(dāng)前數(shù)據(jù)元素個(gè)數(shù) */ }HashTable;int m=0; /* 散列表表長(zhǎng)，全局變量 *//* 初始化散列表 */ 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; }/* 散列函數(shù) */ int Hash(int key) {return key % m; /* 除留余數(shù)法 */ }/* 插入關(guān)鍵字進(jìn)散列表 */ void InsertHash(HashTable *H,int key) {int addr = Hash(key); /* 求散列地址 */while (H->elem[addr] != NULLKEY) /* 如果不為空，則沖突 */{addr = (addr+1) % m; /* 開(kāi)放定址法的線性探測(cè) */}H->elem[addr] = key; /* 直到有空位后插入關(guān)鍵字 */ }/* 散列表查找關(guān)鍵字 */ Status SearchHash(HashTable H,int key,int *addr) {*addr = Hash(key); /* 求散列地址 */while(H.elem[*addr] != key) /* 如果不為空，則沖突 */{*addr = (*addr+1) % m; /* 開(kāi)放定址法的線性探測(cè) */if (H.elem[*addr] == NULLKEY || *addr == Hash(key)) /* 如果循環(huán)回到原點(diǎn) */return UNSUCCESS; /* 則說(shuō)明關(guān)鍵字不存在 */}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; }

散列表查找性能分析

如果沒(méi)有沖突，散列查找的時(shí)間復(fù)雜度為O(1).

影響散列查找的平均查找長(zhǎng)度因素

1.散列函數(shù)是否均勻

2.處理沖突的方法

3.散列表的裝填因子

所謂裝填因子α=填入表中的記錄個(gè)數(shù)/散列表長(zhǎng)度。α越大，產(chǎn)生沖突的可能性就越大。

轉(zhuǎn)載于:https://www.cnblogs.com/xingchenfeng/p/3714783.html

總結(jié)

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

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。