哈希表的C++实现
哈希表的幾個(gè)概念：
映像：由哈希函數(shù)得到的哈希表是一個(gè)映像。
沖突：如果兩個(gè)關(guān)鍵字的哈希函數(shù)值相等，這種現(xiàn)象稱為沖突。
處理沖突的幾個(gè)方法：
1、開放地址法：用開放地址處理沖突就是當(dāng)沖突發(fā)生時(shí)，形成一個(gè)地址序列，沿著這個(gè)序列逐個(gè)深測(cè)，直到找到一個(gè)“空”的開放地址，將發(fā)生沖突的關(guān)鍵字值存放到該地址中去。
例如：hash(i)=(hash(key)+d(i)) MOD m (i=1,2,3,......,k(k<m-1)) d為增量函數(shù)，d(i)=d1,d2,d3,...,dn-1
根據(jù)增量序列的取法不同，可以得到不同的開放地址處理沖突探測(cè)方法。
有線性探測(cè)法、二次方探測(cè)法、偽隨機(jī)探測(cè)法。
2、鏈地址法：把所有關(guān)鍵字為同義詞的記錄存儲(chǔ)在一個(gè)線性鏈表中，這個(gè)鏈表成為同義詞鏈表，即把具有相同哈希地址的關(guān)鍵字值存放在同義鏈表中。
3、再哈希表：費(fèi)時(shí)間的一種方法
下面是代碼：
文件"myhash.h"
#include<iostream> using namespace std; typedef int KeyType; //設(shè)關(guān)鍵字域?yàn)檎?需要修改類型時(shí)，只需修改這里就可以 const int NULLKEY=0; //NULLKEY表示該位置無值 int c=0; //用來統(tǒng)計(jì)沖突次數(shù) struct Elemtype //數(shù)據(jù)元素類型 { KeyType key; int ord; }; int hashsize[]={11,19,29,37,47}; //hash表容量遞增表 int Hash_length=0;//hash表表長(zhǎng) class HashTable { private: Elemtype *elem; //數(shù)據(jù)元素?cái)?shù)組,動(dòng)態(tài)申請(qǐng) int count;// 當(dāng)前數(shù)據(jù)元素個(gè)數(shù) int size; //決定hash表的容量為第幾個(gè),hashsize[size]為當(dāng)前hash容量 public: int Init_HashTable() //構(gòu)造一個(gè)空hash表 { int i; count=0; size=0; //初始化容量為hashsize[0]=11 Hash_length=hashsize[0]; elem=new Elemtype[Hash_length]; if(!elem) { cout<<"內(nèi)存申請(qǐng)失敗"<<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函數(shù)的一種(取模法) { return k%Hash_length; } void Collision(int &p,int d) //解決沖突 { p=(p+d)%Hash_length; //采用開放地址法里的線性探測(cè) } bool Search_Hash(KeyType k,int &p) //查找 { //在開放地址hash表中查找關(guān)鍵字等于k的元素 //若找到用p表示待查數(shù)據(jù),查找不成功時(shí)，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) //沖突次數(shù)未達(dá)到上限 { //插入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<<"空間申請(qǐng)失敗"<<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<<"元素的關(guān)鍵字值和它的標(biāo)志分別是："<<elem[i].key<<" "<<elem[i].ord<<endl; } void Get_Data(int p) { cout<<"元素的關(guān)鍵字值和它的標(biāo)志分別是："<<elem[p].key<<" "<<elem[p].ord<<endl; } };
Cpp代碼?
總結(jié)
- 上一篇： python实现自顶向下，自底向上
- 下一篇： STL之七：STL各种容器的使用时机详解