哈希表的C++實現

哈希表的幾個概念：

映像：由哈希函數得到的哈希表是一個映像。

沖突：如果兩個關鍵字的哈希函數值相等，這種現象稱為沖突。

處理沖突的幾個方法：

1、開放地址法：用開放地址處理沖突就是當沖突發生時，形成一個地址序列，沿著這個序列逐個深測，直到找到一個“空”的開放地址，將發生沖突的關鍵字值存放到該地址中去。

例如：hash(i)=(hash(key)+d(i)) MOD m (i=1,2,3,......,k(k

根據增量序列的取法不同，可以得到不同的開放地址處理沖突探測方法。

有線性探測法、二次方探測法、偽隨機探測法。

2、鏈地址法：把所有關鍵字為同義詞的記錄存儲在一個線性鏈表中，這個鏈表成為同義詞鏈表，即把具有相同哈希地址的關鍵字值存放在同義鏈表中。

3、再哈希表：費時間的一種方法

下面是代碼：

文件"myhash.h"
 

#include  
using namespace std;  
  
typedef int KeyType; //設關鍵字域為整形,需要修改類型時，只需修改這裡就可以  
const int NULLKEY=0; //NULLKEY表示該位置無值  
int c=0; //用來統計沖突次數  
  
struct Elemtype //數據元素類型  
{  
    KeyType key;  
    int ord;   
};  
  
int hashsize[]={11,19,29,37,47}; //hash表容量遞增表  
int Hash_length=0;//hash表表長  
  
class HashTable  
{  
private:  
    Elemtype *elem; //數據元素數組,動態申請  
    int count;// 當前數據元素個數  
    int size; //決定hash表的容量為第幾個,hashsize[size]為當前hash容量  
public:  
  
    int Init_HashTable() //構造一個空hash表  
    {  
        int i;  
        count=0;  
        size=0; //初始化容量為hashsize[0]=11  
        Hash_length=hashsize[0];  
        elem=new Elemtype[Hash_length];  
        if(!elem)  
        {  
            cout<<"內存申請失敗"<
測試函數"main.cpp"
#include"myhash.h"  
  
int main()  
{  
    Elemtype r[12]={{17,1},{60,2},{29,3},{38,4},{1,5},{2,6},{3,7},{4,8},{5,9},{6,10},{7,11},{8,12}};  
    HashTable H;  
    int i,p,j;  
    KeyType k;  
    H.Init_HashTable();  
    for(i=0;i<11;i++) //插入前11個記錄  
    {  
        j=H.Insert_Hash(r[i]);  
        if(j==-1)  
            cout<<"表中已有關鍵字為"<