欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

哈希表的C++实现

程序员文章站 2022-04-02 08:02:16
哈希表的几个概念: 映像:由哈希函数得到的哈希表是一个映像。 冲突:如果两个关键字的哈希函数值相等,这种现象称为冲突。 处理冲突的几个方法: 1、开放地址法:用开放地址处理...

哈希表的几个概念:

映像:由哈希函数得到的哈希表是一个映像。

冲突:如果两个关键字的哈希函数值相等,这种现象称为冲突。

处理冲突的几个方法:

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<<"表中已有关键字为"<
;>