首页 > 试题广场 >

设哈希表长为8，哈希函数为Hash (key)=key%7。

[单选题]

设哈希表长为8，哈希函数为Hash (key)=key%7。初始记录关键字序列为(32，24，15，27，20，13)，用链地址法作为解决冲突方法的平均查找长度是（）

查看答案及解析

梅梅201803241656278

链地址法作为解决冲突方法：冲突以后变成链表，查询次数增加

32%7=4（查一次）

24%7=3（查一次）

15%7=1（查一次）

27%7=6（查一次）

20%7=6（查两次）

13%7=6（查三次）

ASL=(1*4+2*1+3*1)/6=1.5

发表于 2018-12-29 17:21:03 回复(5)

白起丶

哈希表长度为8，故存储的位置分别是0、1、2、3、4、5、6、7.

根据哈希函数，可以得到关键字序列(32，24，15，27，20，13)存储的位置分别为：4、3、1、6、6、6.

解决冲突的方式是链地址法，故20和13存储在27的下边，三者构成一个链表结构，第一个元素为27，最后一个元素为13.

哈希表中查找一个元素的复杂度为O（1）,故32、24、15、27分别查找一次即可找到，而20和13在链表结构中，需要从27开始往下遍历，分别需要额外的一次和两次才能找到，即20需要两次，13需要三次。

故最终的平均查找长度为总查询次数 / 关键字个数=（1+1+1+1+2+3）/ 6 = 1.5

编辑于 2020-07-12 11:33:37 回复(0)

提交观点

问题信息

C++工程师 iOS工程师系统工程师运维工程师前端工程师算法工程师测试开发工程师测试工程师哈希 2019 360集团 Java工程师

来自：360公司-2019校...

上传者：小小

难度：

2条回答 274收藏 5876浏览

扫一扫，把题目装进口袋