其中H（k）为哈希函数，m为哈希表长，d为增量函数，d（i）=dl，d2…dn-l。
增量序列的取法不同，可得到不同的开放地址处理冲突探测方法。
1.1线性探测法
线性探测法是从发生冲突的地址（设为d）开始，依次探查d+l，d+2，…m-1（当达到表尾m-1时，又从0开始探查）等地址，直到找到一个空闲位置来存放冲突处的关键字。
若整个地址都找遍仍无空地址，则产生溢出。
线性探查法的数学递推描述公式为：
注释:
这里的di-1为上一次哈希值
例题：
已知哈希表大小11，哈希表名字为A,给定关键字序列（20，30，70，15，8，12，18，63，19）。
哈希函数为H（k）=k％ll，采用线性探测法处理冲突，则将以上关键字依次存储到哈希表中。
试构造出该哈希表，并求出等概率情况下的平均查找长度。
本题中各元素的存放到哈希表过程如下：
H（20）=9，可直接存放到A[9]中去。
H（30）=8，可直接存放到A[8]中去。
H（70）=4，可直接存放到A[4]中去。
H（15）=4，冲突；
d0=4
d1=（4+1）%11=5，将15放入到A[5]中。
H（8）=8，冲突；
d0=8
d1=（8+1）%11=9，仍冲突；
d2=（8+2）%11=10，将8放入到A[10]中。
H（12）=l，可直接存放到A[1]中去。
H（18）=7，可直接存放到A[7]中去。
H（63）=8，冲突；
d0=8
d1=（8+1）%11=9，仍冲突;
d2=（8+2）%11=10，仍冲突;
d3=（8+3）%11=0，将63放入到A[0]中。
H（19）=8，冲突；
d0=8
d1=（8+1）%11=9，仍冲突;
d2=（8+2）%11=10，仍冲突;
d3=（8+3）%11=0，仍冲突;
d4=（8+4）%11=1，仍冲突;
d5=（8+5）%11=2，将19放入到A[2]中。
由此得哈希表如图所示:
平均查找长度:
（1*5+2+3+4+6）/9=20/9
利用线性探查法处理冲突容易造成关键字的“堆积”问题。
这是因为当连续n个单元被占用后，再散列到这些单元上的关键字和直接散列到后面一个空闲单元上的关键字都要占用这个空闲单元，致使该空闲单元很容易被占用，从而发生非同义冲突。
造成平均查找长度的增加。
为了克服堆积现象的发生，可以用下面的方法替代线性探查法。
1.2平方探查法
设发生冲突的地址为d，则平方探查法的探查序列为：
d+12，d+22，…直到找到一个空闲位置为止。
平方探查法的数学描述公式为：
平方探测法和上面的线性探测法实现过程一样,只不过这里的解决冲突的新哈希不同而已。
若解决冲突时，探查到一半单元仍找不到一个空闲单元。
则表明此哈希表太满，需重新建立哈希表。
2.链地址法
用链地址法解决冲突的方法是：
把所有关键字为同义词的记录存储在一个线性链表中，这个链表称为同义词链表。
并将这些链表的表头指针放在数组中（下标从0到m-1）。
这类似于图中的邻接表和树中孩子链表的结构。
链地址法查找分析:
由于在各链表中的第一个元素的查找长度为l，第二个元素的查找长度为2，依此类推。
因此，在等概率情况下成功的平均查找长度为：
（1*5+2*2+3*l+4*1）／9=16／9
虽然链地址法要多费一些存储空间，但是彻底解决了“堆积”问题，大大提高了查找效率。
哈希表的查找及性能分析
哈希法是利用关键字进行计算后直接求出存储地址的。
当哈希函数能得到均匀的地址分布时，不需要进行任何比较就可以直接找到所要查的记录。
但实际上不可能完全避免冲突，因此查找时还需要进行探测比较。
在哈希表中，虽然冲突很难避免，但发生冲突的可能性却有大有小。
这主要与三个因素有关。
第一:
与装填因子有关
所谓装填因子是指哈希表中己存入的元素个数n与哈希表的大小m的比值，即=n/m。
当越小时，发生冲突的可能性越小，越大（最大为1）时，发生冲突的可能性就越大。
第二:
与所构造的哈希函数有关
若哈希函数选择得当，就可使哈希地址尽可能均匀地分布在哈希地址空间上，从而减少冲突的发生。
否则，若哈希函数选择不当，就可能使哈希地址集中于某些区域，从而加大冲突的发生。
第三:
与解决冲突的哈希冲突函数有关
哈希冲突函数选择的好坏也将减少或增加发生冲突的可能性。
下面有3道例题，分别是线性探测法、链地址法解决冲突的例题和综合练习辞典的例题
例题1:
线性探测法解决冲突
#include
#include
#include
/*
【例】已知哈希表地址区间为0～10，
给定关键字序列（20，30，70，15，8，12，18，63，19）。
哈希函数为H（k）=k％11，采用线性探测法处理冲突，
新哈希函数H（k）=（H（k）+1）%11
则将以上关键字依次存储到哈希表中。
试构造出该哈希表，并求出等概率情况下的平均查找长度。
*/
#defineN11
//创建哈希表
int*create_hashtable（）;
//哈希函数：
用来求关键字在哈希表中的下标值
inthashfun（intkey）;
voidadd_hash（int*hashtable,intdata）;
intcount=0;
intmain（void）
{
int*hashtable=create_hashtable（）;
intarr[9]={20,30,70,15,8,12,18,63,19};
inti;
for（i=0;i<9;i++）
add_hash（hashtable,arr[i]）;
printf（"平均查找长度为:
%f\n",count/9.0）;
return0;
}
int*create_hashtable（）
{
int*hashtable=（int*）malloc（N*sizeof（int））;
memset（hashtable,0,N*sizeof（int））;//清空哈希表
if（!
hashtable）{printf（"cannotmalloc\n"）;}
returnhashtable;
}
inthashfun（intkey）
{
returnkey%N;
}
voidadd_hash（int*hashtable,intdata）
{
if（!
hashtable）{printf（"hashtable=NULL\n"）;return;}
intserch=1;
intaddr=hashfun（data）;
if（hashtable[addr]==0）//表示这个空间是空的
hashtable[addr]=data;
else
{//这个空间不是空的,产生冲突，需要调用新哈希函数去寻找新的哈希地址
do
{
serch++;
addr=（addr+1）%N;
}while（hashtable[addr]!
=0）;//不等于0表示空间非空,需要重新找
//上面循环结束表示找到能够使用的哈希地址
hashtable[addr]=data;
}
count+=serch;
}
例题2:
链地址法解决冲突
#include
#include
#include
#defineN11
typedefstructNode
{
intdata;
structNode*next;
}node,*pnode;
pnode*create_hashtable（）;
inthashfun（intkey）;
voidadd_hash（pnode*hashtable,intdata）;
voidshow_hash（pnode*hashtable）;
intmain（void）
{
intarr[9]={20,30,70,15,8,12,18,63,19};
pnode*hashtable=create_hashtable（）;
inti;
for（i=0;i<9;i++）
add_hash（hashtable,arr[i]）;
show_hash（hashtable）;
return0;
}
pnode*create_hashtable（）
{
pnode*hashtable=（pnode*）malloc（N*sizeof（pnode））;
if（!
hashtable）{printf（"hashtable=NULL\n"）;}
memset（hashtable,0,N*sizeof（pnode））;//清空
returnhashtable;
}
inthashfun（intkey）{returnkey%N;}
voidadd_hash（pnode*hashtable,intdata）
{
if（!
hashtable）{printf（"hashtable=NULL\n"）;return;}
intaddr=hashfun（data）;
pnodenewnode=（pnode）malloc（sizeof（node））;
if（!
newnode）{printf（"cannotmalloc\n"）;return;}
newnode->next=NULL;
newnode->data=data;
if（hashtable[addr]==NULL）//这个哈希地址空间为空
hashtable[addr]=newnode;
else
{//尾插
pnodep=hashtable[addr];
while（p->next!
=NULL）//循环结束p指向尾节点
p=p->next;
//下面将新节点插入到尾部
p->next=newnode;
}
}
voidshow_hash（pnode*hashtable）
{
inti;
for（i=0;i{
printf（"[%d]->",i）;
if（hashtable[i]==NULL）
printf（"^\n"）;
else
{
pnodep=hashtable[i];
while（p!
=NULL）
{
printf（"%d->",p->data）;
p=p->next;
}
printf（"^\n"）;
}
}
}
例题3:
用哈希表来实现一个简单的辞典
#include
#include
#include
#defineN1000
typedefstructWords
{
charwords[22];
charmean[122];
}word,*pword;
typedefstructNode
{
wordw;
structNode*next;
}node,*pnode;
pnode*create_hashtable（）;
intgetkey（char*str）;
inthashfun（intkey）;
voidadd_hash（pnode*hashtable,pwordpw）;
pwordfind_hash（pnode*hashtable,char*word）;
voidsave（pnode*hashtable）;
voidload（pnode*hashtable）;
intmain（void）
{
pnode*hashtable=create_hashtable（）;
wordw[3]={"hello","你好","hi","嗨","howareyou","你最近怎么样"};
add_hash（hashtable,&w[0]）;
add_hash（hashtable,&w[1]）;
add_hash（hashtable,&w[2]）;
//save（hashtable）;
//load（hashtable）;
charstr[22];
while
（1）
{
gets（str）;
if（!
strcmp（str,"exit"））
return0;
pwordp=find_hash（hashtable,str）;
if（p==NULL）
printf（"没找到\n"）;
else
printf（"mean:
%s\n",p->mean）;
}
return0;
}
pnode*create_hashtable（）
{
pnode*hashtable=（pnode*）malloc（sizeof（pnode）*N）;
if（!
hashtable）{printf（"hashtable=NULL\n"）;}
memset（hashtable,0,sizeof（pnode）*N）;
returnhashtable;
}
intgetkey（char*str）
{
intkey=0;
while（*str!
='\0'）
{
key=key+*str;
str++;
}
returnkey;
}
inthashfun（intkey）{returnkey%N;}
voidadd_hash（pnode*hashtable,pwordpw）
{
if（!
hashtable）{printf（"hashtable=NULL\n"）;return;}
intaddr=hashfun（getkey（pw->words））;
pnodenewnode=（pnode）malloc（sizeof（node））;
if（!
newnode）{printf（"cannotmalloc\n"）;return;}
newnode->next=NULL;
memcpy（&newnode->w,pw,sizeof（word））;
if（hashtable[addr]==NULL）
hashtable[addr]=newnode;
else
{//尾插
pnodep=hashtable[addr];
while（p->next!
=NULL）//循环结束时,p指向尾节点
p=p->next;
//将新节点插入到尾部
p->next=newnode;
}
}
pwordfind_hash（pnode*hashtable,char*word）
{
if（!
hashtable）{printf（"hashtable=NULL\n"）;returnNULL;}
intaddr=hashfun（getkey（word））;
if（hashtable[addr]==NULL）
returnNULL;
else
{
pnodep=hashtable[addr];
while（p!
=NULL）
{
if（!
strcmp（p->w.words,word））
return&p->w;
p=p->next;
}
returnNULL;
}
}
voidsave（pnode*hashtable）
{
FILE*fp=fopen（"data","w"）;
if（!
fp）{printf（"cannotopenfile\n"）;return;}
inti;
pnodep;
for（i=0;i{
if（hashtable[i]!
=NULL）
{
p=hashtable[i];
while（p!
=NULL）
{
fwrite（&p->w,sizeof（word）,1,fp）;
p=p->next;
}
}
}
fclose（fp）;
}
voidload（pnode*hashtable）
{
FILE*fp=fopen（"data","r"）;
if（!
fp）{printf（"cannotopenfile\n"）;return;}
wordw;
while（fread（&w,sizeof（w）,1,fp）>0）
add_hash（hashtable,&w）;
fclose（fp）;
}
升级会员 