设哈希（ Hash ）表的地址范围为 0 ～ 17 ，哈希函

[问答题]

设哈希（ Hash ）表的地址范围为 0 ～ 17 ，哈希函数为： H （ K ）＝ K MOD 16 。 K 为关键字，用线性探测法再散列法处理冲突，输入关键字序列：

（10，24，32，17，31，30，46，47，40，63，49）造出Hash表，试回答下列问题：

⑴画出哈希表的示意图；

⑵若查找关键字63，需要依次与哪些关键字进行比较？

⑶若查找关键字60，需要依次与哪些关键字比较？

⑷假定每个关键字的查找概率相等，求查找成功时的平均查找长度。

阿奻_

（ 1 ）画表如下：

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
32	17	63	49					24	40	10				30	31	46	47

（2）查找63,首先要与H(63)=63%16=15号单元内容比较，即63 vs 31 ,no;

然后顺移，与46,47,32,17,63相比，一共比较了6次！

（3）查找60,首先要与H(60)=60%16=12号单元内容比较，但因为12号单元为空（应当有空标记），所以应当只比较这一次即可。

（4）对于黑色数据元素，各比较1次；共6次；

对红色元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，

所以ASL=1/11（6＋2＋3×3）＝17/11=1.5454545454≈1.55

发表于 2017-05-07 09:21:52 回复(3)

提交观点

问题信息

哈希

上传者：阿奻_

难度：

1条回答 5收藏 12975浏览

扫一扫，把题目装进口袋