? ? ? ?哈希查找也稱為散列查找。所謂的哈希其實就是在記錄的存儲位置和記錄的關鍵字之間建立一個確定的對應關系f，使得每個關鍵字key對應一個存儲位置f(key)。查找時，根據(jù)這個確定的對應關系找到給定值的映射f(key),若查找集合中存在這個記錄，則必定在f(key)的位置上。哈希技術既是一種存儲方法，也是一種查找方法。示例代碼上傳至：https://github.com/chenyufeng1991/HashSearch ?。

六種哈希函數(shù)的構造方法：

（1）直接定址法

函數(shù)公式：f(key) = a * key + b（a,b為常數(shù)）

這種方法的優(yōu)點是：簡單、均勻，不會產(chǎn)生沖突。但是需要事先知道關鍵字的分布情況，適合查找表較小并且連續(xù)的情況。

（2）數(shù)字分析法

? ? ? ?也就是取出關鍵字中的若干位組成哈希地址。比如我們的11位手機號是“187****1234”，其中前三位是接入號，一般對應不同的電信公司。中間四位表示歸屬地。最后四位才表示真正的用戶號。

? ? ? ?如果現(xiàn)在要存儲某個部門的員工的手機號，使用手機號碼作為關鍵字，那么很有可能前面7位都是相同的，所以我們選擇后面的四位作為哈希地址就不錯。

（3）平方取中法

取關鍵字平方后的中間幾位作為哈希地址。由于一個數(shù)的平方的中間幾位與這個數(shù)的每一位都有關，所以平方取中法產(chǎn)生沖突的機會相對較小。平方取中法所取的位數(shù)由表長決定。

如：K=456，K^2=207936,如果哈希表的長度為100，則可以取79（中間兩位）作為哈希函數(shù)值。

（4）折疊法

折疊法是將關鍵字從左到右分割成位數(shù)相等的幾個部分（最后一部分位數(shù)不夠可以短），然后將這幾部分疊加求和，并按哈希表表長，取后幾位作為哈希地址。當關鍵字位數(shù)很多，而且關鍵字中每一位上數(shù)字分布大致均勻時，可以使用折疊法。

如：我們的關鍵字是9876543210，哈希表表長三位，我們可以分為四組：987 | 654 | 321 | 0，然后將他們疊加求和：987+654+321+0 = 1962,再取后三位就可以得到哈希地址為962.

（5）除留余數(shù)法

選擇一個適當?shù)恼麛?shù)p（p<=表長），用關鍵字除以p，所得的余數(shù)可以作為哈希地址。即：H(key) = key % p(p<=表長)，除留余數(shù)法的關鍵是選取適當?shù)膒，一般選p為小于或等于哈希表的長度(m)的某個素數(shù)。

如：m = 8,p=7.

m = 16,p = 13.

m = 32,p = 31.

（6）隨機數(shù)法

函數(shù)公式：f(key) = random(key). ?這里的random是隨機函數(shù)，當關鍵字的長度不等時，采用這種方式比較合適。

總之，哈希函數(shù)的規(guī)則就是：通過某種轉(zhuǎn)換關系，使關鍵字適度的分散到指定大小的順序結構中。越分散，查找的時間復雜度就越小， 空間復雜度就越高。哈希查找明顯是一種以空間換時間的算法。

? ? ?上面提到了如何構造一個哈希函數(shù)，那就不得不提如何避免沖突的算法。

（1）開放定址法

當沖突發(fā)生時，使用某種方法在哈希表中形成一探查序列。然后沿著該探查序列逐個單位的查找，直到找到一個開放的地址（即該地址單元為空）為止。對于哈希表中形成一探查序列時，可以有3種不同的方法：

? ? ? ? 1.線性探測法

將散列看成一個環(huán)形表，探測序列是（假設表長為m）：

H(k),H(k)+1,H(k)+2.....m-1,0,1......H(k)-1。用線性探測法解決沖突時，求下一個開放地址的公式為：Hi = (H(k)+i) MOD m.

?

? ? ? ? 2.二次探測法

二次探測法的探測序列依次是12，-12，22，-22等等。當發(fā)生沖突時，求下一個開放地址的公式為：

H2i-1?=?(H(k)+i2)?MOD?m

H2i?=?(H(k)-i2)?MOD?m?(1=<?i?<=?(m-1)/2?)

優(yōu)點：減少了堆集發(fā)生的可能性；

缺點：不容易探測到哈希表空間。

? ? ? ?3.偽隨機探測法

采用隨機探測法解決沖突時，下一個開放地址的公式為：Hi?=?(H(k)+Ri)?MOD?m。

其中R1,R2,...,Rm-1是一個隨機排列。

?

（2）再哈希法

當沖突發(fā)生時，使用另一個函數(shù)計算得到一個新的哈希地址，直到?jīng)_突不再發(fā)生時為止。Hi?=?RHi(key)?i?=?1,2,…,k ?。其中RHi均是不同的哈希函數(shù)。優(yōu)點是不易產(chǎn)生聚集，缺點是增加了計算時間。

（3）鏈地址法

將所有關鍵字為同義詞的結點鏈接在同一個單鏈表中。若選定的哈希函數(shù)所產(chǎn)生的哈希地址為0~m-1,則可以將哈希表定義成一個由m個鏈表頭指針組成的指針數(shù)組。優(yōu)點是：不產(chǎn)生聚集；由于結點空間是動態(tài)申請的，故更適合造表前無法確定表長的情況；從表中刪除節(jié)點容易。

（4）公共溢出區(qū)法

? ? ? 假設哈希函數(shù)的值域為[0...m-1]，則設向量HashTable[0...m-1]為基本表，每個分量存放一個記錄，另設立向量OverTable[0..v]為溢出表。所有關鍵字和基本表中關鍵字為同義詞的記錄，不管它們由哈希函數(shù)得到的哈希地址是什么，一旦發(fā)生沖突，都被填入溢出表中。

? ? ? 在哈希表上進行查找的過程和建表的過程基本一致。假設給定的值為k，根據(jù)建表時設定的哈希函數(shù)H，計算出哈希地址H(k),若表中該地址對應的空間未被占用。則查找失敗。否則將該地址中的節(jié)點與給定值k比較，若相等則查找成功，否則按建表時設定的處理沖突方法找下一個地址，如此反復下去，直到找到某個地址空間未被占用（查找失敗）或者關鍵字比較相等（查找成功）為止。

代碼如下：

// // main.c // HashSearch // // Created by chenyufeng on 16/2/17. // Copyright ? 2016年 chenyufengweb. All rights reserved. //#include "stdio.h" #include "stdlib.h"#define HASHSIZE 7 // 定義散列表長為數(shù)組的長度 #define NULLKEY -32768typedef int Status; typedef struct{int *elem; // 數(shù)據(jù)元素存儲地址，動態(tài)分配數(shù)組int count; // 當前數(shù)據(jù)元素個數(shù) }HashTable;// 散列表表長，全局變量 int m = 0;void InitHashTable(HashTable *hashTable); Status Hash(int key); void Insert(HashTable *hashTable,int key); Status Search(HashTable *hashTable,int key); void DisplayHashTable(HashTable *hashTable);int main(int argc, const char * argv[]) {int result;HashTable hashTable;int arr[HASHSIZE] = {13,29,27,28,26,30,38};//初始化哈希表InitHashTable(&hashTable);/*** 向哈希表中插入數(shù)據(jù);也就是把元素使用哈希函數(shù)映射到哈希表中；*/for (int i = 0;i < HASHSIZE;i++){Insert(&hashTable,arr[i]);}//數(shù)據(jù)已存到哈希表中，打印觀察哈希表，元素的位置和原數(shù)組是完全不一樣的DisplayHashTable(&hashTable);//查找數(shù)據(jù)result = Search(&hashTable,30);if (result == -1){printf("沒有找到！");}else{printf("在哈希表中的位置是:%d\n",result);}return 0; }//初始化一個空的哈希表 void InitHashTable(HashTable *hashTable){m = HASHSIZE;hashTable->elem = (int *)malloc(m * sizeof(int)); //申請內(nèi)存hashTable->count = m;for(int i = 0;i < m;i++){hashTable->elem[i] = NULLKEY;} }//哈希函數(shù)(除留余數(shù)法) Status Hash(int key){return key % m; }//插入 void Insert(HashTable *hashTable,int key){/*** 根據(jù)每一個關鍵字，計算哈希地址hashAddress；*/int hashAddress = Hash(key); //求哈希地址/*** 發(fā)生沖突，表示該位置已經(jīng)存有數(shù)據(jù)*/while(hashTable->elem[hashAddress] != NULLKEY){//利用開放定址的線性探測法解決沖突hashAddress = (hashAddress + 1) % m;}//插入值hashTable->elem[hashAddress] = key; }//查找 Status Search(HashTable *hashTable,int key){//求哈希地址int hashAddress = Hash(key);//發(fā)生沖突while(hashTable->elem[hashAddress] != key){//利用開放定址的線性探測法解決沖突hashAddress = (hashAddress + 1) % m;if (hashTable->elem[hashAddress] == NULLKEY || hashAddress == Hash(key)){return -1;}}//查找成功return hashAddress; }//打印結果 void DisplayHashTable(HashTable *hashTable){for (int i = 0;i < hashTable->count;i++){printf("%d ",hashTable->elem[i]);}printf("\n"); }

在C語言編程中，我們常常會設定一些預定義常量，或者說是函數(shù)的結果狀態(tài)碼，如下所示：

#define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2
因為在C語言中是沒有BOOL布爾這種數(shù)據(jù)類型的，所以上面的預定義可以簡化編程。我們有時候還會進行如下的預定義：

typedef int Status;表示Status是函數(shù)的返回類型，其值是函數(shù)結果狀態(tài)代碼。我在上述代碼中也使用了這種預定義。

本文參考：http://www.cnblogs.com/jingmoxukong/p/4332252.html

http://www.cnblogs.com/mcgrady/archive/2013/09/01/3294871.html

總結

以上是生活随笔為你收集整理的经典算法学习——哈希查找的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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