第七章-哈希表

====Word行业资料分享--可编辑版本--双击可删====

哈希表又称散列表,实际上就是一个数组。

哈希函数是一个用来求存储在哈希的关键字 在哈希表的地址下标的函数.

比如一个哈希表 int hashtable[5];

现在有下面4个数要存入到哈希表中:

（3，15，22，24）

给定一个哈希函数 : H(k)=k % 5

最终数据存储如下图：

理想情况下，哈希函数在关键字和地址之间建立了一个一一对应关系，从而使得查找只需一次

计算即可完成。由于关键字值的某种随机性，使得这种一一对应关系难以发现或构造。因而可能会出

现不同的关键字对应一个存储地址。即k1≠k2，但H(k1)=H(k2)，这种现象称为冲突。

把这种具有不同关键字值而具有相同哈希地址的对象称“同义词”。

在大多数情况下，冲突是不能完全避免的。这是因为所有可能的关键字的集合可能比较大，而对应

的地址数则可能比较少。

对于哈希技术，主要研究两个问题：

（1）如何设计哈希函数以使冲突尽可能少地发生。

（2）发生冲突后如何解决。

哈希函数的构造方法:

构造好的哈希函数的方法，应能使冲突尽可能地少，因而应具有较好的随机性。这样可使一组关键字

的散列地址均匀地分布在整个地址空间。根据关键字的结构和分布的不同，可构造出许多不同的哈希

函数。

1．直接定址法

直接定址法是以关键字k本身或关键字加上某个数值常量c作为哈希地址的方法。该哈希函数H(k)

为：

H(k)=k+c (c≥0)

这种哈希函数计算简单，并且不可能有冲突发生。当关键字的分布基本连续时，可使用直接定址法

的哈希函数。否则，若关键字分布不连续将造成内存单元的大量浪费。

2．除留余数法 (注意：这种方法常用)

取关键字k除以哈希表长度m所得余数作为哈希函数地址的方法。即：

源-于-网-络-收-集

====Word行业资料分享--可编辑版本--双击可删====

H(k)=k％m

这是一种较简单、也是较常见的构造方法。这种方法的关键是选择好哈希表的长度m。使得数据

集合中的每一个关键字通过该函数转化后映射到哈希表的任意地址上的概率相等。理论研究表明，在m

取值为素数（质数）时，冲突可能性相对较少。

3．平方取中法

取关键字平方后的中间几位作为哈希函数地址（若超出范围时，可再取模）。

4．折叠法

这种方法适合在关键字的位数较多，而地址区间较小的情况。

将关键字分隔成位数相同的几部分。然后将这几部分的叠加和作为哈希地址（若超出范围，可再

取模）。

为该身份证关键字的哈希函数地址。

5．数值分析法

若事先知道所有可能的关键字的取值时，可通过对这些关键字进行分析，发现其变化规律，构造

出相应的哈希函数。

若取最后两位作为哈希地址，则哈希地址的集合为下表所示：

关键字哈希函数地址

2

92317602

75

92326875

28

92739628

34

92343634

16

92706816

38

92774638

62

92381262

冲突解决

1.开放地址法

处理冲突就是为该关键字的记录找到另一个“空”的哈希地址。即通过一个新的哈希函数得到一

源-于-网-络-收-集

====Word行业资料分享--可编辑版本--双击可删====

个新的哈希地址。如果仍然发生冲突，则再求下一个，依次类推。直至新的哈希地址不再发生冲突为

止。

用开放定址法处理冲突就是当冲突发生时，形成一个地址序列。沿着这个序列逐个探测，直到找出一

个“空”的开放地址。将发生冲突的关键字值存放到该地址中去。

如 Hi=(H(k)+d（i）) % m, i=1，2，…k (k

其中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

源-于-网-络-收-集

====Word行业资料分享--可编辑版本--双击可删====

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）。这类似于图中的邻接表和

树中孩子链表的结构。

源-于-网-络-收-集

====Word行业资料分享--可编辑版本--双击可删====

链地址法查找分析:

由于在各链表中的第一个元素的查找长度为l，第二个元素的查找长度为2，依此类推。因此，在

等概率情况下成功的平均查找长度为：

(1*5+2*2+3*l+4*1)／9=16／9

虽然链地址法要多费一些存储空间，但是彻底解决了“堆积”问题，大大提高了查找效率。

哈希表的查找及性能分析

哈希法是利用关键字进行计算后直接求出存储地址的。当哈希函数能得到均匀的地址分布时，不

需要进行任何比较就可以直接找到所要查的记录。但实际上不可能完全避免冲突，因此查找时还需要

进行探测比较。

在哈希表中，虽然冲突很难避免，但发生冲突的可能性却有大有小。这主要与三个因素有关。

第一:与装填因子有关

所谓装填因子是指哈希表中己存入的元素个数n与哈希表的大小m的比值，即 =n/m。

当 越小时，发生冲突的可能性越小，越大（最大为1）时，发生冲突的可能性就越大。

第二:与所构造的哈希函数有关

若哈希函数选择得当，就可使哈希地址尽可能均匀地分布在哈希地址空间上，从而减少冲突的发

生。否则，若哈希函数选择不当，就可能使哈希地址集中于某些区域，从而加大冲突的发生。

源-于-网-络-收-集

====Word行业资料分享--可编辑版本--双击可删====

第三:与解决冲突的哈希冲突函数有关

哈希冲突函数选择的好坏也将减少或增加发生冲突的可能性。

下面有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

则将以上关键字依次存储到哈希表中。

试构造出该哈希表，并求出等概率情况下的平均查找长度。

*/

#define N 11

//创建哈希表

int * create_hashtable();

//哈希函数：用来求关键字在哈希表中的下标值

int hashfun(int key);

void add_hash(int * hashtable,int data);

int count = 0;

int main(void)

{

int * hashtable = create_hashtable();

int arr[9] = {20,30,70,15,8,12,18,63,19};

int i;

for(i = 0; i < 9;i++)

add_hash(hashtable,arr[i]);

printf("平均查找长度为:%fn",count/9.0);

return 0;

}

int * create_hashtable()

源-于-网-络-收-集

====Word行业资料分享--可编辑版本--双击可删====

{

int * hashtable = (int *)malloc(N*sizeof(int));

memset(hashtable,0,N*sizeof(int)); //清空哈希表

if(!hashtable){printf("cannot mallocn");}

return hashtable;

}

int hashfun(int key)

{

return key%N;

}

void add_hash(int * hashtable,int data)

{

if(!hashtable){ printf("hashtable = NULLn"); return ;}

int serch = 1;

int addr = 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

#define N 11

typedef struct Node

{

int data;

struct Node * next;

}node,*pnode;

源-于-网-络-收-集

====Word行业资料分享--可编辑版本--双击可删====

pnode * create_hashtable();

int hashfun(int key);

void add_hash(pnode * hashtable,int data);

void show_hash(pnode * hashtable);

int main(void)

{

int arr[9] = {20,30,70,15,8,12,18,63,19};

pnode * hashtable = create_hashtable();

int i;

for(i = 0; i < 9;i++)

add_hash(hashtable,arr[i]);

show_hash(hashtable);

return 0;

}

pnode * create_hashtable()

{

pnode * hashtable = (pnode *)malloc(N*sizeof(pnode));

if(!hashtable){ printf("hashtable = NULLn");}

memset(hashtable,0,N*sizeof(pnode)); //清空

return hashtable;

}

int hashfun(int key){ return key%N ;}

void add_hash(pnode * hashtable,int data)

{

if(!hashtable) {printf("hashtable = NULLn"); return ;}

int addr = hashfun(data);

pnode newnode = (pnode)malloc(sizeof(node));

if(!newnode){ printf("cannot mallocn"); return ;}

newnode->next = NULL;

newnode->data = data;

if(hashtable[addr] == NULL) //这个哈希地址空间为空

hashtable[addr] = newnode;

else

{//尾插

pnode p = hashtable[addr];

while(p->next != NULL) //循环结束p指向尾节点

p = p->next;

//下面将新节点插入到尾部

p->next = newnode;

}

源-于-网-络-收-集

====Word行业资料分享--可编辑版本--双击可删====

}

void show_hash(pnode * hashtable)

{

int i;

for(i = 0; i < N;i++)

{

printf("[%d]->",i);

if(hashtable[i] == NULL)

printf("^n");

else

{

pnode p = hashtable[i];

while(p != NULL)

{

printf("%d->",p->data);

p = p->next;

}

printf("^n");

}

}

}

例题3: 用哈希表来实现一个简单的辞典

#include

#include

#include

#define N 1000

typedef struct Words

{

char words[22];

char mean[122];

}word,*pword;

typedef struct Node

{

源-于-网-络-收-集

====Word行业资料分享--可编辑版本--双击可删====

word w;

struct Node * next;

}node,*pnode;

pnode * create_hashtable();

int getkey(char *str);

int hashfun(int key);

void add_hash(pnode * hashtable,pword pw);

pword find_hash(pnode * hashtable,char * word);

void save(pnode *hashtable);

void load(pnode *hashtable);

int main(void)

{

pnode * hashtable = create_hashtable();

word w[3] = {"hello","你好","hi"," 嗨","how are you","你最近怎么样"};

add_hash(hashtable,&w[0]);

add_hash(hashtable,&w[1]);

add_hash(hashtable,&w[2]);

// save(hashtable);

// load(hashtable);

char str[22];

while(1)

{

gets(str);

if(!strcmp(str,"exit"))

return 0;

pword p = find_hash(hashtable,str);

if(p == NULL)

printf("没找到n");

else

printf("mean:%sn",p->mean);

}

return 0;

}

pnode * create_hashtable()

{

pnode * hashtable = (pnode *)malloc(sizeof(pnode)*N);

if(!hashtable){printf("hashtable = NULLn");}

memset(hashtable,0,sizeof(pnode)*N);

return hashtable;

源-于-网-络-收-集

====Word行业资料分享--可编辑版本--双击可删====

}

int getkey(char *str)

{

int key = 0;

while(*str != '0')

{

key = key + *str;

str++;

}

return key;

}

int hashfun(int key){ return key%N; }

void add_hash(pnode * hashtable,pword pw)

{

if(!hashtable){printf("hashtable = NULLn"); return ;}

int addr = hashfun( getkey(pw->words) );

pnode newnode = (pnode)malloc(sizeof(node));

if(!newnode){printf("cannot mallocn"); return ;}

newnode->next = NULL;

memcpy(&newnode->w,pw,sizeof(word));

if(hashtable[addr] == NULL)

hashtable[addr] = newnode;

else

{//尾插

pnode p = hashtable[addr];

while(p->next != NULL) //循环结束时,p指向尾节点

p =p->next;

//将新节点插入到尾部

p->next = newnode;

}

}

pword find_hash(pnode * hashtable,char * word)

{

if(!hashtable){printf("hashtable = NULLn"); return NULL;}

int addr = hashfun( getkey(word) );

if(hashtable[addr] == NULL)

return NULL;

else

源-于-网-络-收-集

====Word行业资料分享--可编辑版本--双击可删====

{

pnode p = hashtable[addr];

while(p != NULL)

{

if(!strcmp( p->, word))

return &p->w;

p = p->next;

}

return NULL;

}

}

void save(pnode *hashtable)

{

FILE * fp= fopen("data","w");

if(!fp){printf("cannot open filen"); return ;}

int i;

pnode p;

for(i = 0; i < N;i++)

{

if(hashtable[i] != NULL)

{

p = hashtable[i];

while(p != NULL)

{

fwrite(&p->w,sizeof(word),1,fp);

p = p->next;

}

}

}

fclose(fp);

}

void load(pnode *hashtable)

{

FILE * fp= fopen("data","r");

if(!fp){printf("cannot open filen"); return ;}

word w;

while(fread(&w,sizeof(w),1,fp) > 0 )

add_hash(hashtable,&w);

fclose(fp);

}

源-于-网-络-收-集