首页 > 试题广场 >

常用的构造哈希函数的方法有哪些？若在哈希表中删除一个记录，应

[问答题]
常用的构造哈希函数的方法有哪些？若在哈希表中删除一个记录，应如何操作？为什么？已知一组关键字为（ 19,14,23,01,68,20,84,27,55,11,10,79 ）按哈希函数 H(Key)=Key MOD 13 和线性探测再散列处理冲突的方法在地址空间 A[0..15] 中构造哈希表。
添加回答
Letitia头像 Letitia

常用构造哈希函数的方法有：

（1）数字分析法该法事先需知道关键字集合，且关键字位数比散列表地址位数多，应选数字分布均匀的位。

（2）平方取中法将关键字值的平方取中间几位作哈希地址。

（3）除留余数法 H（key）=key%p，通常p取小于等于表长的最大素数。

（4）折叠法将关键字分成长度相等（最后一段可不等）的几部分，进行移位叠加或间界叠加，其值作哈希地址。

（5）基数转换法两基数要互素，且后一基数要大于前一基数。

在哈希表中删除一个记录，在拉链法情况下可以物理地删除。在开放定址法下，不能物理地删除，只能作删除标记。 该地址可能是该记录的同义词查找路径上的地址，物理的删除就中断了查找路径。因为查找时碰到空地址就认为是查找失败。

散列地址

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

关键字

14

01

68

27

55

19

20

84

79

23

11

10

比较次数

1

2

1

4

3

1

1

3

9

1

1

3


发表于 2017-05-23 20:21:49 回复(0)
提交观点

问题信息

哈希
上传者：Letitia
难度：
1条回答 2681浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号