4、折叠法
将关键字分割成位数相同的几部分(最后一部分的位数可以不同),
然后取这几部分的叠加和(舍去进位)作为哈希地址,这方法称为折叠法。
例如:每一种西文图书都有一个国际标准图书编号,它是一个10位的十进制数字,若要以它作关键字建立一个哈希表,当馆藏书种类不到10,000时,可采用此法构造一个四位数的哈希函
数。如果一本书的编号为0-442-20586-4,则:
| 5864 | | 5864 |
| 4220 | | 0224 |
+) | 04 | +) | 04 |
| ----------- | | ----------- |
| 10088 | | 6092 |
| H(key)=0088 | | H(key)=6092 |
| | | |
| (a)移位叠加 | | (b)间界叠加 |
5、除留余数法
取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。
H(key)=key
MOD p (p<=m)
6、随机数法
选择一个随机函数,取关键字的随机函数值为它的哈希地址,即
H(key)=random(key)
,其中random为随机函数。通常用于关键字长度不等时采用此法。
三、总结
哈希表的优缺点
四、作业
预习如何处理冲突及哈希表的查找。
回目录上一课下一课
第三十三课
本课主题:哈希表(二)
教学目的:掌握哈希表处理冲突的方法及哈希表的查找算法
教学重点:哈希表处理冲突的方法
教学难点:开放定址法
授课内容:
一、复习上次课内容
什么是哈希表?如何构造哈希表?
提出问题:如何处理冲突?
二、处理冲突的方法
| | 成绩一 | 成绩二... |
3 | ... | | |
... | ... | | |
24 | 刘丽 | 82 | 95 |
25 | ... | | |
26 | 陈伟 | | |
... | ... | | |
33 | 吴军 | | |
... | ... | | |
42 | 李秋梅 | | |
... | ... | | |
46 | 刘宏英 | | |
... | ... | | |
72 | 吴小艳 | | |
... | ... | | |
78 | ... | | |
如果两个同学分别叫
刘丽 刘兰,当加入刘兰时,地址24发生了冲突,我们可以以某种规律使用其它的存储位置,如果选择的一个其它位置
仍有冲突,则再选下一个,直到找到没有冲突的位置。选择其它位置的方法有:
1、开放定址法
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,若用线性探测再散列,如下:
(a)插入前
(b)线性探测再散列
(c)二次探测再散列
(d)伪随机探测再散列
伪随机数列为9,5,3,8,1...
2、再哈希法
当发生冲突时,使用第二个、第三个、哈希函数计算地址,直到无冲
突时。缺点:计算时间增加。
3、链地址法
将所有关键字为同义词的记录存储在同一线性链表中。
4、建立一个公共溢出区
假设哈希函数的值域为[0,m-
1],则设向量HashTable[0..m-1]为基本表,另外设立存储空间向量OverTable[0..v]用以存储发生冲突的记录。