程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 哈希表的C++實現(轉)，哈希

哈希表的C++實現(轉)，哈希

編輯：C++入門知識

哈希表的C++實現(轉)，哈希

哈希表的幾個概念：

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

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

處理沖突的幾個方法：

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

例如：hash(i)=(hash(key)+d(i)) MOD m (i=1,2,3,......,k(k<m-1)) d為增量函數，d(i)=d1,d2,d3,...,dn-1

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

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

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

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

下面是代碼：

文件"myhash.h"

Cpp代碼

#include<iostream>
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<<"內存申請失敗"<<endl;
exit(0);
}
for(i=0;i<Hash_length;i++)
elem[i].key=NULLKEY;
return 1;
}
void Destroy_HashTable()
{
delete[]elem;
elem=NULL;
count=0;
size=0;
}
unsigned Hash(KeyType k) //hash函數的一種(取模法)
{
return k%Hash_length;
}
void Collision(int &p,int d) //解決沖突
{
p=(p+d)%Hash_length; //采用開放地址法裡的線性探測
}
bool Search_Hash(KeyType k,int &p) //查找
{
//在開放地址hash表中查找關鍵字等於k的元素
//若找到用p表示待查數據,查找不成功時，p指向的是可插入地址
c=0;
p=Hash(k); //求hash地址
while(elem[p].key!=NULLKEY && elem[p].key!=k)
{
c++;
if(c<Hash_length)
Collision(p,c);
else
return 0; //表示查找不成功
}
if(elem[p].key==k)
return 1;
else
return 0;
}
int Insert_Hash(Elemtype e) //插入
{
//在查找不成功的情況下將k插入到hash表中
int p;
if(Search_Hash(e.key,p))
return -1; //表示該元素已在hash表中
else if(c<hashsize[size]/2) //沖突次數未達到上限
{
//插入e
elem[p]=e;
count++;
return 1;
}
else
ReCreate_HashTable(); // 重建hash表
return 0; //插入失敗
}
void ReCreate_HashTable() //重建hash表
{
int i,count2=count;
Elemtype *p,*elem2=new Elemtype[count];
p=elem2;
cout<<"____重建hash表_____"<<endl;
for(i=0;i<Hash_length;i++) //將原有元素暫存到elem2中
if(elem[i].key!=NULLKEY)
*p++=*(elem+i);
count=0;
size++; //hash容量增大
Hash_length=hashsize[size];
p=new Elemtype[Hash_length];
if(!p)
{
cout<<"空間申請失敗"<<endl;
exit(0);
}
elem=p;
for(i=0;i<Hash_length;i++)
elem[i].key=NULLKEY;
for(p=elem2;p<elem2+count2;p++) //將原有元素放回新表
Insert_Hash(*p);
}
void Traverse_HashTable()
{
cout<<"哈希地址0->"<<Hash_length-1<<endl;
for(int i=0;i<Hash_length;i++)
if(elem[i].key!=NULLKEY)
cout<<"元素的關鍵字值和它的標志分別是："<<elem[i].key<<" "<<elem[i].ord<<endl;
}
void Get_Data(int p)
{
cout<<"元素的關鍵字值和它的標志分別是："<<elem[p].key<<" "<<elem[p].ord<<endl;
}
};

測試函數"main.cpp"

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<<"表中已有關鍵字為"<<r[i].key<<" "<<r[i].ord<<"的記錄"<<endl;
}
cout<<"按哈希地址順序遍歷哈希表"<<endl;
H.Traverse_HashTable();
cout<<endl;
cout<<"輸入要查找的記錄的關鍵字：";
cin>>k;
j=H.Search_Hash(k,p);
if(j==1)
H.Get_Data(p);
else
cout<<"無此記錄"<<endl;
j=H.Insert_Hash(r[11]); //插入最後一個元素
if(j==0)
{
cout<<"插入失敗"<<endl;
cout<<"需要重建哈希表才可以插入"<<endl;
cout<<"____重建哈希表____"<<endl;
H.Insert_Hash(r[i]); //重建後重新插入
}
cout<<"遍歷重建後的哈希表"<<endl;
H.Traverse_HashTable();
cout<<endl;
cout<<"輸入要查找的記錄的關鍵字：";
cin>>k;
j=H.Search_Hash(k,p);
if(j==1)
H.Get_Data(p);
else
cout<<"該記錄不存在"<<endl;
cout<<"____銷毀哈希表____"<<endl;
H.Destroy_HashTable();
return 0;
}