哈希查找是通過計算數據元素的存儲地址進行查找的一種方法。
基本介紹
定義,操作步驟,解決衝突,
定義
哈希查找的操作步驟：
⑴用給定的哈希函式構造哈希表；
⑵根據選擇的衝突處理方法解決地址衝突；
⑶在哈希表的基礎上執行哈希查找。
操作步驟
step1 取數據元素的關鍵字key，計算其哈希
函式值。若該地址對應的存儲
空間還沒有被占用，則將該元素存入；
否則執行step2解決衝突。
step2 根據選擇的衝突處理方法，計算關鍵字
key的下一個存儲地址。若下一個存儲地
址仍被占用，則繼續執行step2，直到找
到能用的存儲地址為止。
哈希查找步驟為：
設哈希表為HST[0~M-1]，哈希函式取H（key），解決衝突的方法為R（x）；
Step1 對給定k值，計算哈希地址 Di=H（k）；若HST為空，則查找失敗；
若HST=k，則查找成功；否則，執行step2（處理衝突）。
Step2 重複計算處理衝突的下一個存儲地址 Dk=R（Dk-1），直到HST[Dk]為
空，或HST[Dk]=k為止。若HST[Dk]=K，則查找成功，否則查找失敗。
哈希查找的本質是先將數據映射成它的哈希值。哈希查找的核心是構造一個哈希函式，它將原來直觀、整潔的數據映射為看上去似乎是隨機的一些整數。
哈希查找的產生有這樣一種背景——有些數據本身是無法排序的(如圖像)，有些數據是很難比較的(如圖像)。如果數據本身是無法排序的，就不能對它們進行比較查找。如果數據是很難比較的，即使採用折半查找，要比較的次數也是非常多的。因此，哈希查找並不查找數據本身，而是先將數據映射為一個整數(它的哈希值)，並將哈希值相同的數據存放在同一個位置一即以哈希值為索引構造一個數組。
在哈希查找的過程中，只需先將要查找的數據映射為它的哈希值，然後查找具有這個哈希值的數據，這就大大減少了查找次數。如果構造哈希函式的參數經過精心設計，記憶體空間也足以存放哈希表，查找一個數據元素所需的比較次數基本上就接近於一次。
解決衝突
影響哈希查找效率的一個重要因素是哈希函式本身。當兩個不同的數據元素的哈希值相同時，就會發生衝突。為減少發生衝突的可能性，哈希函式應該將數據儘可能分散地映射到哈希表的每一個表項中。解決衝突的方法有以下兩種：
(1) 開放地址法
如果兩個數據元素的哈希值相同，則在哈希表中為後插入的數據元素另外選擇一個表項。
當程式查找哈希表時，如果沒有在第一個對應的哈希表項中找到符合查找要求的數據元素，程式就會繼續往後查找，直到找到一個符合查找要求的數據元素，或者遇到一個空的表項。
(2) 鏈地址法
例3. 6是一個簡單的哈希查找算法程式，你可以將它和本章結尾的有關代碼一起編譯連線成一個可執行程式。
例3．6一個簡單的哈希查找算法程式
1: #include<stdlib.h>
2: #include<string.h>
3: #include "list.h"
4: #include "hash.h"
5:
6: #define HASH_SIZE 1024
7:
8: static listnode_t *hashTable[HASH_SIZE];
9:
10: void insert(const char * s)
11: {
12: listnode_t *ele = newNode((void * ) s)
13: unsigned int h = hash(s) % HASH_SIZE;
14:
15: ele->next = hashTable[h]
16: hashTable[h] = ele;
17: }
18:
19: void print (void)
20: {
21: int h;
22:
23: for (h = 0; h < HASH_SIZE; h++)
24: {
25: listnode_t * lp = hashTalbe[h];
26:
27: if(lp == NULL)
28: continue;
29: printf("[%d]" , h);
30: while (lp)
31: {
32: printf("\t'%s'" , lp->u.str)
33: lp = ip->next;
34: }
35: putchar ('\n');
36: }
37: }
38:
39: const char *search(const char *s)
40: {
39: unsigned int h = hash(s) % HASH_SIZE;
42: listnode_t * lp = hashTable[h];
43:
44: while (lp)
45: {
46: if (! strcmp (s, lp->u.str))
47: return lp->u.str;
48: lp = lp->next;
49: }
50: return NULL;
51: }
請參見：
3. 4 哪一種查找方法最方便?
3．5 哪一種查找方法最快?
3．8 怎樣查找鍊表中的數據?
_____________________________________________
以下是一個簡單示例：
#include<iostream>
#include<string>
using namespace std;
#define m 5 //人數
#define n 10 //哈希表長度
#define q 7 //隨機數
struct name{
char *py;
int k;
};
name namelist[n];
struct hash{
char *py;
int k;
int s;
};
hash hashlist[n];
void listname()
{
char *f;
int s0,r,i;
namelist[0].py="as";
namelist[1].py="sa";
namelist[2].py="d";
namelist[3].py="f";
namelist[4].py="g";
for(i=0;i<m;i++)
{
s0=0;
f=namelist[i].py;
for(r=0;*(f+r)!='\0';r++)
s0+=*(f+r);
namelist[i].k=s0;
}
}
void creathash()
{
int i;
for(i=0;i<n;i++)
{
hashlist[i].py="";
hashlist[i].k=0;
hashlist[i].s=0;
}
for(i=0;i<m;i++)
{
int sum=0;
int adr=(namelist[i].k)%q;
int d=adr;
if(hashlist[adr].s==0)
{
hashlist[adr].py=namelist[i].py;
hashlist[adr].k=namelist[i].k;
hashlist[adr].s=1;
}
else
{
while(hashlist[d].k!=0)
{
d=(d+namelist[i].k%5+1)%q;
sum+=1;
}
hashlist[d].py=namelist[i].py;
hashlist[d].k=namelist[i].k;
hashlist[d].s=sum+1;
}
}
}
void find()
{
string nam;
int s0=0,r,sum=1,adr,d;
cout<<"請輸入姓名的拼音："<<endl;
cin>>nam;;
for(r=0;r<20;r++)
s0+=nam[r];
adr=s0%q;
d=adr;
if(hashlist[adr].k==s0)
cout<<"姓名:"<<hashlist[d].py<<" "<<"關鍵字:"<<s0<<" "<<"查找長度為: 1"<<endl;
else if(hashlist[adr].k==0)
cout<<"無此記錄！"<<endl;
else
{
int g=0;
while(g==0)
{
d=(d+s0%5+1)%q;
sum+=1;
if(hashlist[d].k==0)
{
cout<<"無此記錄！"<<endl;
g=1;
}
if(hashlist[d].k==s0)
{
cout<<"姓名:"<<hashlist[d].py<<" "<<"關鍵字:"<<s0<<" "<<"查找長度為: 1"<<endl;
g=1;
}
}
}
}
void display()
{
int i;
float av=0;
for(i=0;i<n;i++)
{
cout<<"姓名:"<<hashlist[i].py<<" "<<"關鍵字:"<<hashlist[i].k<<"搜尋長度："<<hashlist[i].s<<endl;
}
for(i=0;i<7;i++)
{
av+=hashlist[i].s;
}
av/=m;
cout<<"平均查找長度：="<<av<<endl;
}
int main()
{
char x;
listname();
creathash();
cout<<"d. 顯示哈希表 f. 查找 任意鍵退出 請選擇："<<endl;
while(cin>>x){
if(x=='d'){display(); cout<<endl;}
else if(x=='f'){find();cout<<endl;}
else break;
}
return 0;
}
