C++数据结构--.哈希表线性探测开放寻址法与独立表链地址法

电玩女神 2021-11-17 02:38 343阅读 0赞

**1.哈希函数是个定位函数，它用键作为参数，返回表中的索引值  
![20130805133825875][]  
  
  
2.线性探测开放寻址法  
\*调用哈希函数处理键得到哈希值，用值除以表的长度后取余数，从而确定表中的一个位置  
\*如果该位置非空，则探测下一个位置，到达表最后一项时，折回表头。  
\*如果回到原来哈希位置上时还未找到空闲位置，说明表已经填满了。  
  
  
例如：hash(key)=key%11  
![20130805133856781][]**

**![20130805133957718][]**

**3.独立表链地址法  
\*把哈希表定义成容器（如向量和链表）的索引序列，每个容器（bucket)用来保存映射到同一位置上的数据集合  
![20130805134101625][]  
  
使用独立表链地址法存储上面线性探测开放寻址法存储的数据  
![20130805134145468][]  
  
  
  
实现代码：  
\#ifndef hashTable\_H  
\#define hashTable\_H  
\#include<vector>  
\#include<list>  
  
using namespace std;  
  
template<typename T , typename hashFun>  
class hashTable  
\{  
friend class hashIterator;  
private:  
vector<list<T>> table;  
hashFun fun;  //哈希函数对象  
size\_t rows;   
public:  
\#include"hashIterator.h" //详见[C++数据结构--.哈希表独立表链地址法迭代器的设计][C_--.]  
hashTable(size\_t r,hashFun hf=hashFun()):table(r),rows(r),fun(hf)\{\}  
  
//查找val所在的迭代器位置   
hashIterator find(const T &val)  
\{   
int r=fun(val)%rows;//用哈希函数定位  
if(table\[r\].empty()) //val不存在哈希表中，返回end()   
\{   
  
return hashIterator(this,-1,table\[r\].end());  
\}  
else  
\{   
 typenamelist<T>::iterator it=table\[r\].begin();  
 for(;it!=table\[r\].end();it++)//遍历哈希函数定位的行  
 \{   
 if(\*it==val)  
 return hashIterator(this,r,it);  
 \}  
return hashIterator(this,-1,table\[r\].end());//不存在val,返回end()   
\}  
\}  
  
//插入val,返回 hashIterator-bool键值对   
pair<hashIterator , bool> insert(const T &val)  
\{   
hashIterator hit=find(val);//查找val所在的迭代器位置   
size\_t r=fun(val)%rows;//用哈希函数定位  
bool success=false; //查找是否成功标志   
if(hit.row==-1) //当val不存在哈希表时，插入val   
\{   
typename list<T>::iterator it=table\[r\].end();  
it=table\[r\].insert(it,val);  
success=true;  
return make\_pair(hashIterator(this,r,it),success);  
\}  
  
return make\_pair(hit,success);//当val存在哈希表时，返回val所在迭代器位置，但不插入   
  
\}  
  
  
//删除val   
void erase(const T &val)  
\{   
hashIterator hit=find(val);  
size\_t r=fun(val)%rows;  
if(hit.row==-1) //val不存在哈希表示，删除非法   
\{   
cerr<<"value "<<val<<" is not exist,can't erase"<<endl;  
return;  
\}  
  
table\[r\].erase(hit.it);  
  
\}  
  
//删除迭代器指定的位置   
void erase(hashIterator pos)  
 \{   
if(pos==end())//删除end()，非法   
 \{   
cerr<<"can't erase end()"<<endl;  
return;  
 \}   
  
 T val=\*pos;  
 erase(val);  
  
 \}  
  
//返回第一个元素所在的迭代器位置  
hashIterator begin()  
\{   
for(int i=0;i<rows;i++)  
 \{   
 if(!table\[i\].empty())  
 return hashIterator(this,i,table\[i\].begin());  
 \}  
  
 return hashIterator(this,-1,table\[0\].end()); //哈希表为空时返回end()   
\}  
  
//返回end()迭代器   
hashIterator end()  
\{   
return hashIterator(this,-1,table\[0\].end());  
\}  
  
  
  
\};  
  
  
\#endif  
  
  
测试代码：  
\#include <iostream>  
\#include"hashTable.h"  
using namespace std;**

**class hashFun  //哈希函数对象类**

**\{  
public:  
size\_t operator()(size\_t val)  
\{  
return val;  
\}  
  
\};  
  
  
int main(int argc, char\*\* argv)  
\{  
  
  
hashTable<int,hashFun> ht(11);  
ht.insert(54);  
ht.insert(77);  
ht.insert(94);  
ht.insert(89);  
ht.insert(14);  
ht.insert(45);  
ht.insert(35);  
ht.insert(76);  
cout<<"in ht : ";  
for(int x:ht)  
\{  
cout<<x<<ends;  
\}  
  
auto p=ht.insert(94);  
cout<<endl<<"after insert duplicate val 94:"<<endl;  
if(!p.second)  
 cout<<"duplicate val "<<\*p.first<<" can't be inserted"<<endl;  
ht.erase(100); //删除不存在的元素  
auto p1=ht.end();   
ht.erase(p1); //删除end()迭代器  
p1++; //end()迭代器自增   
auto p2=ht.find(94);//查找94   
ht.erase(p2); //删除迭代器指定的元素   
ht.erase(89); //删除89   
cout<<"after erase 94 ,89: "<<endl;  
  
for(int x:ht)  
\{   
cout<<x<<ends;  
\}   
  
return 0;  
\}  
  
  
  
运行结果：  
![Center][]**

[20130805133825875]: /images/20211116/53e142d8d1304ce9a57bb3387a9aa86c.png
[20130805133856781]: /images/20211116/831c16ab7f5140499ba8627b80d38502.png
[20130805133957718]: /images/20211116/9b9cf72c497243499f227ac12cab0bc1.png
[20130805134101625]: /images/20211116/1ed0217642264e71ba1a04cef9636876.png
[20130805134145468]: /images/20211116/cbee0495301040d3b7c846be659f1bb4.png
[C_--.]: http://blog.csdn.net/piniheaven/article/details/9766351
[Center]: /images/20211116/49053cbf76d9437b88eb7046bda4700b.png