第三十三课：哈希表（二）
时间：2010-09-21 来源：yuxinlen
第三十三课
本课主题： 哈希表（二）
教学目的： 掌握哈希表处理冲突的方法及哈希表的查找算法
教学重点： 哈希表处理冲突的方法
教学难点： 开放定址法
授课内容：
一、复习上次课内容
什么是哈希表？如何构造哈希表？
提出问题：如何处理冲突？
二、处理冲突的方法
|
|
|
成绩一 |
成绩二... |
|
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);
}
四、总结
处理冲突的要求是什么？
相关阅读 更多 +
