首页 / 软件开发 / 数据结构与算法 / 数据结构教程 第三十三课 哈希表（二）

数据结构教程 第三十三课 哈希表（二）2007-05-16教学目的： 掌握哈希表处理冲突的方法及哈希表的查找算法

教学重点： 哈希表处理冲突的方法

教学难点： 开放定址法

授课内容：

一、复习上次课内容

什么是哈希表？如何构造哈希表？

提出问题：如何处理冲突？

二、处理冲突的方法

		成绩一	成绩二...
3	...
...	...
24	刘丽	82	95
25	...
26	陈伟
...	...
33	吴军
...	...
42	李秋梅
...	...
46	刘宏英
...	...
72	吴小艳
...	...
78	...

如果两个同学分别叫 刘丽 刘兰，当加入刘兰时，地址24发生了冲突，我们可以以某种规律使用其它的存储位置，如果选择的一个其它位置仍有冲突，则再选下一个，直到找到没有冲突的位置。选择其它位置的方法有：

１、开放定址法

Hi=（H（key）+di） MOD m i=1,2,...,k（k<=m-1）

其中m为表长，di为增量序列

如果di值可能为1,2,3,...m-1，称线性探测再散列。

如果di取值可能为1,-1,2,-2,4,-4,9,-9,16,-16,...k*k,-k*k（k<=m/2）

称二次探测再散列。

如果di取值可能为伪随机数列。称伪随机探测再散列。

例：在长度为11的哈希表中已填有关键字分别为17,60,29的记录，现有第四个记录，其关键字为38，由哈希函数得到地址为5，若用线性探测再散列，如下：

0	1	2	3	4	5	6	7	8	9	10
					60	17	29

（a）插入前

0	1	2	3	4	5	6	7	8	9	10
					60	17	29	38

（b）线性探测再散列

0	1	2	3	4	5	6	7	8	9	10
					60	17	29

（c）二次探测再散列

0	1	2	3	4	5	6	7	8	9	10
			38		60	17	29

（d）伪随机探测再散列

伪随机数列为9,5,3,8,1...

２、再哈希法

当发生冲突时，使用第二个、第三个、哈希函数计算地址，直到无冲突时。缺点：计算时间增加。

３、链地址法

将所有关键字为同义词的记录存储在同一线性链表中。

４、建立一个公共溢出区

假设哈希函数的值域为[0,m-1],则设向量HashTable[0..m-1]为基本表，另外设立存储空间向量OverTable[0..v]用以存储发生冲突的记录。

三、哈希表的查找

//开放定址哈希表的存储结构

int hashsize[]={997,...};

typedef struct{

ElemType *elem;

int count;

int sizeindex;

}HashTable;

#define SUCCESS 1

#define UNSUCCESS 0

#define DUPLICATE -1

Status SearchHash（HashTable H,KeyType K,int &p,int &c）{

p=Hash（K）;

while（H.elem[p].key！=NULLKEY && ！EQ（K,H.elem[p].key））

collision（p,++c）;

if（EQ（K,H.elem[p].key）

return SUCCESS;

else return UNSUCCESS;

}

Status InsertHash（HashTable &H,EleType e）{

c=0;

if（SearchHash（H,e.key,p,c））

return DUPLICATE;

else if（c<hashsize[H.sizeindex]/2）{

H.elem[p]=e; ++H.count; return OK;

}

else RecreateHashTable（H）;

}

四、总结

处理冲突的要求是什么？