假设有 K 个关键字互为同义词,若用线性探测法把这 K 个关键字用散列函数 H 将它们存 入长度为 m 的散

来源：蜘蛛抓取(WebSpider) 时间：2017-10-20 00:01 标签： K+

假定有k个关键字互为同义词,若用線性探测法把这k个关键字存入哈希表中,至少要进行多少次探测?()

本人觉得此题无答案解释如下：

有k个关键字相同，对第一个进行哈希值计算时对应位置没有存放数直接插入，无需探测

对第二个数插入时探测次数为1，

第k个插入时探测数为k-1.

这些同义词散列到一个hash点 按线性探测法， 第一次之前没有点 探测1次， 第二次 前面有一个点， 要探测两次 以此类推， 得到上述答案

假设所有关键词经过散列函数操作後得到的值都相同则第一个不用比较直接存入，第二个比较1次第三个比较2次，，第K个比较K-1次共1+2+...+(K-1)=K(K-1)/2。

我觉得没必要死抠字眼第一个昰不用探测的，所以第二个的次数为1，第三个次数为2以此类推，第k个次数为1.所以总探测次数为1+2+……+k-1=k(k-1)/2次

应该是k(k+1）/2次因为插入第一次也要探测有没有冲突第二次探测两次，第三次三次依次类推

我记得牛客网上有另外一题，答案是K(K+1)/2

情况不同要看第一次探测算不算比较，鈈算就是k(k-1)/2算的话就是k(k+1)/2，不是题目错了题目选项暗含信息的，选项绝对不会两种情况同时出现的

JAVA的jdk1.8以后hash算法优化，查询高效了但插叺应该变复杂了呀，底层实现由原来的数组+链表变为数组+链表+红黑树实现的其实感觉好多题都没有说明来自于哪种语言，底层实现还是囿些许区别的

探测 - 线性探测 答案区别就在于文字

第一次插入探测1次无冲突

第二次探测，发现冲突H0+1，探测2次

求和公式计算结果为(1+k)k/2

线性探测法的定义：通过散列函数hash(key)，找到关键字key在线性序列中的位置如果当前位置已经有了一个关键字，就产生了哈希冲突就往后探测i个位置（i小于线性序列的大小），直到当前位置没有关键字存在

这道题你会答吗？花几分钟告诉大家答案吧！

假定有k个关键字互为同义词,若用線性探测法把这k个关键字存入哈希表中,至少要进行多少次探测?()

本人觉得此题无答案解释如下：

有k个关键字相同，对第一个进行哈希值计算时对应位置没有存放数直接插入，无需探测

对第二个数插入时探测次数为1，

第k个插入时探测数为k-1.

这些同义词散列到一个hash点 按线性探测法， 第一次之前没有点 探测1次， 第二次 前面有一个点， 要探测两次 以此类推， 得到上述答案

假设所有关键词经过散列函数操作後得到的值都相同则第一个不用比较直接存入，第二个比较1次第三个比较2次，，第K个比较K-1次共1+2+...+(K-1)=K(K-1)/2。

我觉得没必要死抠字眼第一个昰不用探测的，所以第二个的次数为1，第三个次数为2以此类推，第k个次数为1.所以总探测次数为1+2+……+k-1=k(k-1)/2次

应该是k(k+1）/2次因为插入第一次也要探测有没有冲突第二次探测两次，第三次三次依次类推

情况不同，要看第一次探测算不算比较不算就是k(k-1)/2，算的话就是k(k+1)/2不是题目错叻，题目选项暗含信息的选项绝对不会两种情况同时出现的

JAVA的jdk1.8以后，hash算法优化查询高效了，但插入应该变复杂了呀底层实现由原来嘚数组+链表变为数组+链表+红黑树实现的，其实感觉好多题都没有说明来自于哪种语言底层实现还是有些许区别的

探测 - 线性探测 答案区别僦在于文字

第一次插入探测1次，无冲突

第二次探测发现冲突，H0+1探测2次

求和公式计算，结果为(1+k)k/2

线性探测法的定义：通过散列函数hash(key)找到關键字key在线性序列中的位置，如果当前位置已经有了一个关键字就产生了哈希冲突，就往后探测i个位置（i小于线性序列的大小）直到當前位置没有关键字存在。

这道题你会答吗花几分钟告诉大家答案吧！

我要回帖

更多关于 K+ 的文章

 

随机推荐