一、哈希查找算法原理

哈希查找是一種快速查找算法，該算法不需要對關鍵字進行比較，而是以關鍵字為自變量，以該關鍵字在存儲空間中的地址為因變量，建立某種函數關系，稱為哈希函數，這樣在查找某一關鍵字的時候，就可以通過哈希函數直接得到其地址，有效的提高了查找效率。
選取哈希函數及基本原則主要有：計算函數所需時間、關鍵字的長度、哈希表長度（哈希地址范圍）、關鍵字分布情況、記錄的查找頻率等。
哈希函數的構造有多種，常見的有“直接定址法”、“數字分析法”、“平方取中法”、“折疊法”、“除留余數法”、“隨機數法”等。
哈希函數構造的一個基本原則就是盡量避免沖突，也就是盡量避免因變量地址的沖突。一旦發生沖突，就需要重新定址。常見的處理地址沖突的方法有：“開放定址法”、“再哈希法”、“鏈地址法”、“建立公共溢出區”等。

二、創建哈希查找及哈希插值表示例

假設有數據{ 10, 8, 14, 15, 20, 31 }，創建哈希表以進行哈希查找。
1.創建哈希表
以除留余數法構造哈希函數，以線性探測法作為處理沖突的方法，取哈希表長度為7，建立哈希表過程如下：
H(10) = 10 % 7 = 3
H(8) = 8 % 7 = 1
H(14) = 14 % 7 = 0
H(15) = 15 % 7 = 1 此時沖突，重新定址：H(15) = (H(15)+1) % 7 = 2
H(20) = 20 % 7 = 6
H(31) = 31 % 7 = 3 此時沖突，重新定址：H(31) = (H(31)+1) % 7 = 4
哈希表如下：

2.哈希查找
當查找某一元素的時候，首先通過哈希函數計算其哈希地址，然后比較該地址的值是否等于目標值，如果相等則查找結束，否則利用處理沖突的方法確定新的地址，再進行比較。如果哈希地址為空，則查找失敗。
利用哈希函數計算元素15的地址是1，此時表里的元素不等于15，因此使用線性探測法更新哈希地址，得到新地址是2，此時查找成功。

三、哈希查找算法的C程序

以“除留余數法”作為哈希函數，以“線性探測法”作為處理沖突的方法，給出創建哈希表和哈希查找算法的C程序。
1.哈希表的結構：
可以根據實際需要調整成員列表中的成員。

typedef struct HashTable {int key; //關鍵字 int EmptyFlag;//占用（沖突）標志，0表示沒被占用，1表示被占用 }HashTable;

2. 創建哈希表

//tbl：哈希表 //data：已知的數組 //m：數組的長度 //p：哈希表的長度 void CreateHashTable( HashTable *tbl, int *data, int m, int p ) {int i, addr, k;for( i=0; i<p; i++ ) //把哈希表被占用標志置為0 {tbl[i].EmptyFlag = 0;}for( i=0; i<m; i++ ){addr = data[i] % p;//計算哈希地址 k = 0;//記錄沖突次數 while( k++ < p ){if( tbl[addr].EmptyFlag == 0 ){tbl[addr].EmptyFlag = 1;//表示該位置已經被占用 tbl[addr].key = data[i];break;}else{addr = ( addr + 1 ) % p; //處理沖突 }} } }

3.哈希查找

int SearchHashTable( HashTable *tbl, int key, int p ) {int addr, k, loc;//loc表示查找位置下標，如果為0則表示查找失敗 addr = key % P;//計算Hash地址 loc = -1; k = 0;//記錄沖突次數 while( k++ < p ){if( tbl[addr].key == key ){loc = addr;break;}else{addr = ( addr + 1 ) % p; //處理沖突 } }return loc; }

3.完成的測試代碼

#include"stdio.h" #define M 6 #define P (M+1) typedef struct HashTable {int key; //關鍵字 int EmptyFlag;//占用（沖突）標志，0表示沒被占用，1表示被占用 }HashTable;void CreateHashTable( HashTable *tbl, int *data, int m, int p ); int SearchHashTable( HashTable *tbl, int key, int p );int main() {HashTable HashTbl[P];int data[M] = { 10, 8, 14, 15, 20, 31 };int i, loc;printf( "初始數據：\n" );for( i=0; i<M; i++ ){printf( "data[%d] = %5d\n", i, data[i] );}printf( "\n" );CreateHashTable( HashTbl, data, M, P );printf( "哈希表： \n" );for( i=0; i<M; i++ ){printf( "tbl[%d] = %5d\n", i, HashTbl[i].key );}printf( "\n" );for( i=0; i<M; i++ ){loc = SearchHashTable( HashTbl, data[i], P );printf( "%5d 's loc = %5d\n", data[i], loc );}return 0; } void CreateHashTable( HashTable *tbl, int *data, int m, int p ) {int i, addr, k;for( i=0; i<p; i++ ) //把哈希表被占用標志置為0 {tbl[i].EmptyFlag = 0;}for( i=0; i<m; i++ ){addr = data[i] % p;//計算哈希地址 k = 0;//記錄沖突次數 while( k++ < p ){if( tbl[addr].EmptyFlag == 0 ){tbl[addr].EmptyFlag = 1;//表示該位置已經被占用 tbl[addr].key = data[i];break;}else{addr = ( addr + 1 ) % p; //處理沖突 }} } }int SearchHashTable( HashTable *tbl, int key, int p ) {int addr, k, loc;//loc表示查找位置下標，如果為0則表示查找失敗 addr = key % P;//計算Hash地址 loc = -1; k = 0;//記錄沖突次數 while( k++ < p ){if( tbl[addr].key == key ){loc = addr;break;}else{addr = ( addr + 1 ) % p; //處理沖突 } }return loc; }

4.測試結果

總結

以上是生活随笔為你收集整理的哈希（Hash）查找算法详解之C语言版的全部內容，希望文章能夠幫你解決所遇到的問題。

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