散列(Hash)表
标签: 数据结构
学习人数: 7973


全屏播放
赞赏支持

介绍

哈希表(Hash table,也叫散列表), 是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。

哈希表hash table(key,value) 的做法其实很简单,就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字,然后就将该数字对数组长度进行取余,取余结果就当作数组的下标,将value存储在以该数字为下标的数组空间里。

而当使用哈希表进行查询的时候,就是再次使用哈希函数将key转换为对应的数组下标,并定位到该空间获取value,如此一来,就可以充分利用到数组的定位性能进行数据定位。

哈希表最大的优点,就是把数据的存储和查找消耗的时间大大降低,几乎可以看成是常数时间;而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下,用空间换时间的做法是值得的。另外,编码比较容易也是它的特点之一。 哈希表又叫做散列表,分为“开散列” 和“闭散列”。...

登录查看完整内容


课后作业

课后习题

 

【2019年真题】现有长度为11且初始为空的散列表HT,散列函数是H(key)=key%7,采用线性探查(线性探测再散列)法解决冲突将关键字序列87,40,30,6,11,22,98,20依次插入到HT后,HT查找失败的平均查找长度是
A. 4               B. 5.25               C. 6                   D. 6.29

参考答案:C

 

【2018年真题】现有长度为7、初始为空的散列表HT ,散列函数H(k) = k % 7,用线性探测再散列法解决冲突。将关键字22, 43, 15 依次插人到    HT 后,查找成功的平均查找长度是()
A. 1.5        B. 1.6        C. 2        D. 3

参考答案:C

 

【2014年真题】用哈希(散列)方法处理冲突(碰撞)时可能出现堆积(聚集)现象,下列选项中, 会受堆积现象直接影响的是()
A.存储效率 
B.散列函数 
C.装填(装载)因子 
D.平均查找长度 

参考答案:D
答案解析:产生堆积现象,即产生了冲突,它对存储效率、散列函数和装填因子均不会有影响,而平均查找长度会因为堆积现象而增大,选 D。

 

【2011年真题】为提高散列(Hash)表的查找效率,可以采取的正确措施是()
Ⅰ. 增大装填(载)因子 
Ⅱ.设计冲突(碰撞)少的散列函数 
Ⅲ.处理冲突(碰撞)时避免产生聚集(堆积)现象 
A.仅Ⅰ
B.仅Ⅱ
C.仅Ⅰ、Ⅱ
D.仅Ⅱ、Ⅲ 

解答:B。III错在“避免”二字。

 

【2010年真题】将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表的存储空间是一个下标从 0 开始的一维数组,散列函数为:H(key) = (key*3) MOD 7,处理冲突采用线性探测再散列法,要求装填(载)因子为 0.7。 
(1) 请画出所构造的散列表。 
(2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。 

参考答案:
(1) 由装载因子 0.7,数据总数为 7,得一维数组大小为 7/0.7=10,数组下标为 0~9。所构造的散列函数值如下所示: 

key

7

8

30

11

18

9

14

H(key)

0

3

6

5

5

6

0

采用线性探测再散列法处理冲突,所构造的散列表为: 

地址

0

1

2

3

4

5

6

7

8

9

关键字

7

14

 

8

 

11

30

18

9

 

(2)查找成功时,是根据每个元素查找次数来计算平均长度,在等概率的情况下,各关键字的查找次数为: 

key

7

8

30

11

18

9

14

次数

1

1

1

1

3

3

2

故,ASL 成功 = 查找次数 / 元素个数 = (1+2+1+1+1+3+3) / 7 = 12/7 
这里要特别防止惯性思维。查找失败时,是根据查找失败位置计算平均次数,根据散列函数 MOD 7,初始 
只可能在 0~6 的位置。等概率情况下,查找 0~6 位置查找失败的查找次数为:

H(key)

0

1

2

3

4

5

6

次数

3

2

1

2

1

5

4

故,ASL不成功 = 查找次数 / 散列后的地址个数 = (3+2+1+2+1+5+4) / 7 = 18 / 7 
 


登录后发布评论

暂无评论,来抢沙发