数据结构32-33(下)

上一篇 / 下一篇  2010-07-04 21:14:29

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,若用线性探测再散列,如下:

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...

2、再哈希法

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

3、链地址法

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

4、建立一个公共溢出区

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

TAG:

 

评分:0

我来说两句

日历

« 2024-03-25  
     12
3456789
10111213141516
17181920212223
24252627282930
31      

数据统计

  • 访问量: 18467
  • 日志数: 51
  • 建立时间: 2009-04-22
  • 更新时间: 2010-12-09

RSS订阅

Open Toolbar