HardBirch

【数据结构重温】哈希表

时间:10-04-26 栏目:系统技术篇 作者:鲁智森也有文化 评论:0 点击: 1,332 次

1. 哈希表

(1) 哈希表(散列表,杂凑表)

根据设定的哈希函数和处理冲突的方法,将一组关键字映像到一个有限的连续的地址集上,并以关键字在地址集中的象作为记录在表中的存储位置,这种表称为哈希表,又叫散列表杂凑表

(2) 哈希函数

常用除留余数法H(key) = key MOD p

(3) 冲突

什么是冲突?H(key1)=H(key2),且key1key2,称冲突

处理冲突的方法:当H(key)处已有记录,出现冲突,如何处理?

1°. 开放定址法

试用H(key)di,常见以下三种。

(1) 线形探测再散列:试用H(key)1H(key)2...

(2) 二次探测再散列:试用H(key)12H(key)-12H(key)22H(key)-22...

(3) 伪随机探测再散列:试用H(key)f(1)H(key)f(2)...

2°. 再哈希法

H1(key)冲突,试用H2(key)H3(key)...

3°. 链地址法

发生冲突的记录链成单链表。

4°. 建立公共溢出区

所有冲突记录存入溢出区。

(4) 装填因子

              

n个记录,m个地址空间。

哈希表的平均查找长度与记录个数n不直接相关,而是取决于装填因子和处理冲突的方法。

(5) 举例

例:已知一组关键字{19, 14, 23, 1, 68, 20, 85, 9},采用哈希函数H(key)=key MOD 11,请分别采用以下处理冲突的方法构造哈希表,并求各自的平均查找长度。

1) 采用线性探测再散列;

2) 采用伪随机探测再散列,伪随机函数为f(n) = - n

3) 采用链地址法。

 

思路:开始时表为空,依次插入关键字建立哈希表。

 

1) 线性探测再散列

key         19   14     23     1     68    20     85     9       ß 关键字

H(key)    8      3      1      1      2      9      8      9       ß H(key)

                                      2      3              9      10      ß 冲突时计算下一地址

                                              4              10     0       ß

查找长度     1      1      1      2      3      1      3      3       ß 每个关键字的查找长度

 

ASL = (1+1+1+2+3+1+3+3)/8 = 15/8

 

2) 伪随机探测再散列

key         19     14    23     1      68     20    85     9

H(key)     8      3      1      1      2      9      8      9

                                        0                      7      8

                                                                       7

                                                                       6

查找长度             1      1      1      2      1      1      2      4

 

ASL = (1+1+1+2+1+1+2+4)/8 = 13/8

 

3) 链地址法

 

ASL = (1×5+2×3)/8 = 11/8

注:关键字在链表中的插入位置可以在表头或表尾,也可以在中间以便保持关键字有序。

 

最后,此哈希表的装填因子是α= 8/11

 

声明: 本文由( 鲁智森也有文化 )原创编译,转载请保留链接: 【数据结构重温】哈希表

【数据结构重温】哈希表:等您坐沙发呢!

发表评论


QQ群互动

Linux系统与内核学习群:194051772

WP建站技术学习交流群:194062106

魔豆之路QR

魔豆的Linux内核之路

魔豆的Linux内核之路

优秀工程师当看优秀书籍

优秀程序员,要看优秀书!

赞助商广告

友荐云推荐