首页 > 试题广场 >

设哈希表长为14，哈希函数是H(key)=key%11,表中

[单选题]

设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15,38,61,84共四个，现要将关键字为26的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是

M、beat℡菇凉

选B

H(15)=15%11=4

H(38)=38%11 = 5

H(61)=61%11 = 6

H(84)=84%11 = 7

H(26)=26%11=4

关键字26的结点和关键字为15 的结点都放在哈希表4的位置，产生冲突

利用二次探测再散列法公式H(key)=（key+dii）%11 dii=12 ，-12，22，-22.....

当dii取12时：

H(26)=（26+12）%11 = 5

和 H(38)=38%11 =5 冲突

当dii取-12时：

H(26)=（26-12）%11 = 3 不与其他关键字的哈希地址冲突，故将关键字26的结点放在表3位置

发表于 2019-09-07 14:07:20 回复(0)

今天打算吃什么

二次再散列法是用来解决哈希冲突的，二次再散列法包括"开放地址法"和"开链法"。(开链法可以百度)

拿这个题来举例：通过哈希函数H(key)=key%11 构造哈希表：

通过二次探测再散列法解决哈希冲突的话，刚开始的位置为产生冲突的位置，之后每次会在当前寻找的位置基础之上±n²(n从1开始，1，2，3.....)，如果这个位置有空位，那就给冲突的元素填进去，否则就继续往后寻找。

第一步：通过哈希函数是H(key)=key%11 ，计算出关键字26的位置为H(26)=26%11=4，很明显产生了冲突，所以紧接着下面第二步。

第二步：设寻找的位置下标为：loc

第一次寻找：loc = 4+1²=5；下标为5的位置已经有元素，所以继续寻找；

第二次寻找：loc=4-1²=3；下标为3的位置没有元素，所以给该元素放到这个位置。寻找结束。

编辑于 2020-01-09 12:44:44 回复(0)

天尊墨宇

选B

发表于 2020-07-15 10:39:06 回复(0)

提交观点

问题信息

哈希

上传者：星辰大海的碎片

难度：

3条回答 6收藏 6580浏览