C++数据结构哈希表详解

第C++数据结构哈希表详解目录实现散列函数开散列方法闭散列方法(开地址方法)删除*

实现

哈希表，即散列表，可以快速地存储和查询记录。理想哈希表的存储和查询时间都是O(1)。

本《资料》中哈希表分以下几部分：散列函数、存储和查找时的元素定位、存储、查找。删除操作因为不常用，所以只给出思想，不给出代码。

根据实际情况，可选择不同的散列方法。

以下代码假设哈希表不会溢出。

//N表示哈希表长度，是一个素数，M表示额外空间的大小，empty代表“没有元素”。

constintN=9997,M=10000,empty=-1;

inta[N];

voidinit()//初始化哈希表

memset(a,empty,sizeof(a));//注意，只有empty等于0或-1时才可以这样做！

memset(bucket,empty,sizeof(bucket));

memset(first,0,sizeof(first));

inlineinth(int);//散列函数

int*locate(int,bool);//用于存储和查找的定位函数，并返回对应位置。

//如果用于存储，则第二个参数为true，否则为false①。

voidsave(intx)//存储数据

int*p=locate(x,true);

if(p!=NULL)*p=x;

boolisexist(intx)//查找数据

int*p=locate(x,false);

return(p!=NULL*p==x);

}

散列函数

为了达到快速存储和查找的目的，就必须在记录的存储位置和它的关键字之间建立一个确定的对应关系h。

这个关系h叫做哈希函数。

哈希表存取方便但存储时容易冲突：即不同的关键字可以对应同一哈希地址。如何确定哈希函数和解决冲突是关键。以下是几种常见的哈希函数的构造方法：

1.取余数法：h(x)＝x％p（pN，且最好是素数）

2.直接定址法：h(x)＝x或h(x)＝a*x＋b

3.数字分析法：取关键字的若干数位（如中间两位数）组成哈希地址。

4.平方取中法：关键字平方后取中间几位数组成哈希地址。

5.折叠法：将关键数字分割成位数相同的几部分（最后一部分的位数可以不同）然后取几部分的叠加和（舍去进位）作为哈希地址。

6.伪随机数法：事先产生一个随机数序列r[]，然后令h(x)＝r[x]。

设计哈希函数时，要注意

对关键码值的分布并不了解希望选择的散列函数在关键码范围内能够产生一个大致平均的关键码值随机分布，同时避免明显的聚集可能性，如对关键码值的高位或低位敏感的散列函数。

对关键码值的分布有所了解应该使用一个依赖于分布的散列函数，避免把一组相关的关键码值映射到散列表的同一个槽中。

开散列方法

哈希表中难免会发生冲突。使用开散列方法可以解决这个问题。常用操作方法是拉链法，即相同的地址的关键字值均链入对应的链表中。

如果散列函数很差，就容易形成长长的链表，从而影响查找的效率。

下面是用拉链法处理冲突时的定位函数：

intsize=-1;

structnode{intv;node*next;}*first[N],mem[M];

#defineNEW(p)p=mem[++size];p-next=NULL

int*locate(intx,boolins=false)

intp=h(x);

if(a[p]==x!ins)returna[p];

//处理冲突

node*q=first[p];

if(ins)

if(q==NULL)

NEW(q);

first[p]=q;

returnq-

while(q-next!=NULL)q=q-next;

node*r;NEW(r);

q-next=r;

returnr-

while(q!=NULL)

if(q-v==x)returnq-

q=q-next;

returnNULL;

}

闭散列方法(开地址方法)

处理冲突的另一种方法是为该关键字的记录找到另一个空的哈希地址。在处理中可能得到一个地址序列g(i)（i＝1，2，，k；0g(i)n－1)，即在处理冲突时若得到的另一个哈希地址g(1)仍发生冲突，再

求下一地址g(2)，若仍冲突，再求g(3)怎样得到g(i)呢？

溢出桶法：设一个溢出桶，不管得到的哈希地址如何，一旦发生冲突，都填入溢出桶。

再哈希法：使用另外一种哈希函数来定位。

线性探查：g(i)＝(h(x)＋di)%N，其中h(x)为哈希函数，N为哈希表长，di为增量序列。

1.线性探测再散列：di＝1，2，3，，m－1

2.二次探测再散列：

3.伪随机探测序列：事先产生一个随机数序列random[]，令di＝random[i]。

下面是用溢出桶处理冲突时的定位函数：

intbucket[M],top=-1;//用于闭散列方法（溢出桶）

int*locate(intx,boolins=false)

intp=h(x);

if(a[p]==x!ins)//在查找模式下碰到了所需的元素

returna[p];

elseif(ins)

if(a[p]==empty)//可以插入

returna[p];

else//处理冲突

returnbucket[++top];

else//到溢出桶中寻找元素

for(inti=0;i=top;i++)

if(bucket[i]==x)returnbucket[i];

returnNULL;

}

下面是用线性探查处理冲突的定位函数，当然，它也可以用于再哈希法处理冲突

inlineintg(intp,inti){return(p+i)%N;}//根据需要来设计

int*locate(intx,boolins=false)

intp=h(x);

intp2,c=0;

if(a[p]==x!ins)

returna[p];

elseif(ins)

p2=g(p,c++);

}while(a[p2]!=empty);

returna[p2];

}else{

p2=g(p,c++);

}while(a[p2]!=xa[p2]!=empty);

if(a[p2]==x)returna[p2];

returnNULL;

}

闭散列方法的优点是节省空间。不过，无论是溢出桶，还是线性探查，都会在寻址过程中浪费时间。线性

探查的探查序列如果太长，就会使一些其他元素被迫散列在其他位置，从而影响了其他元素的查找效率。

删除*

如果使用开散列方法，那么可以直接删除元素。然而，使用闭散列方法，是不可以直接删除元素的。假如

直接删除，很有可能会影响其他元素的查找。

在这种情况下，有两种删除方法：一种是交换法，另一种是标记法。

交换法：在删除某元素时，不要立刻把它清除。按照线性探查函数继续寻找，直到没有数值为止。将遇到

的最后一个数值与它交换。当然，交换之前还要进行类似的操作，可谓牵一发而动全