请分别画出散列表，并计算ASL。

[问答题]

设有关键字序列{25,40,33,47,12,66,72,87,94,22,5,58}，散列表长12，散列函数为h(key)=key%11,用链地址法处理冲突，请分别画出散列表，并计算ASL。

小游侠UnoW

由 H(key) = key % 11, 可得出下列关系

key	25	40	33	47	12	66	72	87	94	22	5	58
H(key)	3	7	0	3	1	9	6	10	6	0	5	3

可由此关系，H(key) 对应地址，依次填入表，哈希冲突使用链地址法处理冲突：

由上图可知，查找时也对应其探测次数

key	25	40	33	47	12	66	72	87	94	22	5	58
探测次数	2	1	1	1	1	2	1	1	2	3	1	3

则其平均查找长度为：

ASL = (1*7 + 2 * 3 + 3 * 2) / 12 = 19 / 12

发表于 2020-03-12 12:52:00 回复(0)

牛客newbie

19/12

发表于 2020-01-08 15:40:57 回复(0)

杰克蛋

ASL = 16

发表于 2019-11-04 15:01:54 回复(0)

提交观点

问题信息

哈希

上传者：城市里的养猫者

难度：

3条回答 3收藏 2471浏览

扫一扫，把题目装进口袋