上一節介紹了有關哈希表及其構造過程的相關知識，本節將介紹如何利用哈希表實現查找操作。在哈希表中進行查找的操作同哈希表的構建過程類似，其具體實現思路為：對于給定的關鍵字 K，將其帶入哈希函數中，求得與該關鍵字對應的數據的哈希地址，如果該地址中沒有數據，則證明該查找表中沒有存儲該數據，查找失敗：如果哈希地址中有數據，就需要做進一步的證明(排除沖突的影響)，找到該數據對應的關鍵字同 K 進行比對，如果相等，則查找成功；反之，如果不相等，說明在構造哈希表時發生了沖突，需要根據構造表時設定的處理沖突的方法找到下一個地址，同地址中的數據進行比對，直至遇到地址中數據為 NULL(說明查找失敗)，或者比對成功。

回顧：哈希表在構造過程中，處理沖突的方法有：開放定址法、再哈希法、鏈地址法、建立公共溢出區法。

假設哈希表在構造過程采用的開放定址法處理的沖突，則哈希表的查找過程用代碼實現為：

#include #include #define HASHSIZE 7 //定義散列表長為數組的長度#define NULLKEY -1typedef struct{    int *elem;//數據元素存儲地址，動態分配數組    int count; //當前數據元素個數}HashTable;//對哈希表進行初始化void Init(HashTable *hashTable){    int i;    hashTable->elem= (int *)malloc(HASHSIZE*sizeof(int));    hashTable->count=HASHSIZE;    for (i=0;i        hashTable->elem[i]=NULLKEY;    }}//哈希函數(除留余數法)int Hash(int data){    return data%HASHSIZE;}//哈希表的插入函數，可用于構造哈希表void Insert(HashTable *hashTable,int data){    int hashAddress=Hash(data); //求哈希地址    //發生沖突    while(hashTable->elem[hashAddress]!=NULLKEY){        //利用開放定址法解決沖突        hashAddress=(++hashAddress)%HASHSIZE;    }    hashTable->elem[hashAddress]=data;}//哈希表的查找算法int Search(HashTable *hashTable,int data){    int hashAddress=Hash(data); //求哈希地址    while(hashTable->elem[hashAddress]!=data){//發生沖突        //利用開放定址法解決沖突        hashAddress=(++hashAddress)%HASHSIZE;        //如果查找到的地址中數據為NULL，或者經過一圈的遍歷回到原位置，則查找失敗        if (hashTable->elem[hashAddress]==NULLKEY||hashAddress==Hash(data)){            return -1;        }    }    return hashAddress;}int main(){    int i,result;    HashTable hashTable;    int arr[HASHSIZE]={13,29,27,28,26,30,38};    //初始化哈希表    Init(&hashTable);    //利用插入函數構造哈希表    for (i=0;i        Insert(&hashTable,arr[i]);    }    //調用查找算法    result= Search(&hashTable,29);    if (result==-1) printf("查找失敗");    else printf("29在哈希表中的位置是:%d",result+1);    return  0;}

運行結果為：

29在哈希表中的位置是:2

哈希查找算法的效率分析

在構造哈希表的過程中，由于沖突的產生，使得哈希表的查找算法仍然會涉及到比較的過程，因此對于哈希表的查找效率仍需以平均查找長度來衡量。在哈希表的查找過程中需和給定值進行比較的關鍵字的個數取決于以下 3 個因素：

• 哈希函數：哈希函數的“好壞”取決于影響出現沖突的頻繁程度。但是一般情況下，哈希函數相比于后兩種的影響，可以忽略不計。

• 處理沖突的方式：對于同一組關鍵字，設定相同的哈希函數，使用不同的處理沖突的方式得到的哈希表是不同的，表的平均查找長度也不同。

• 哈希表的裝填因子：在一般情況下，當處理沖突的方式相同的情況下，其平均查找長度取決于哈希表的裝滿程度：裝的越滿，插入數據時越有可能發生沖突；反之則越小。

裝填因子=哈希表中數據的個數/哈希表的長度，用字符 α 表示(是數學符號，而不是字符 a)。裝填因子越小，表示哈希表中空閑的位置就越多。

經過計算，在假設查找表中的所有數據的查找概率相等的情況下，對于表長為 m，數據個數為 n 的哈希表：

• 其查找成功的平均查找長度約為：-1/α * ln?(1-α)

• 其查找不成功的平均查找長度約為：1/(1-α)

通過公式可以看到，哈希表的查找效率只同裝填因子有關，而同哈希表中的數據的個數無關，所以在選用哈希表做查找操作時，選擇一個合適的裝填因子是非常有必要的。