首页 > 试题广场 > 题目来源于王道论坛 为提高散列(Hash)表的查找效率
[单选题]
题目来源于王道论坛

为提高散列(Hash)表的查找效率,可以采取的正确措施是()。

Ⅰ.增大装填(载)因子

Ⅱ.设计冲突(碰撞)少的散列函数

Ⅲ.处理冲突(碰撞)时避免产生聚集(堆积)现象


  • 仅Ⅰ
  • 仅Ⅱ
  • 仅Ⅰ、Ⅱ
  • 仅Ⅱ、Ⅲ
推荐

Hash表的查找效率取决于散列函数、处理冲突的方法和装填因子。显然,冲突的产生概率与装填因子(表中记录数与表长之比)的大小成正比,即装填得越满越容易发生冲突,Ⅰ错误。Ⅱ显然正确。采用合适的处理冲突的方式避免产生聚集现象,也将提高查找效率,例如用拉链法解决冲突时就不存在聚集现象,用线性探测法解决冲突时易引起聚集现象,Ⅲ正确。

发表于 2018-09-03 20:25:50 回复(1)
这道题在2020年的王道中有进行更正。
王道的版本如下:

在天勤中的版本如下:


个人看法:
    首先,这道题非常的骚气。
    确实像王道上所述,“冲突不可避免”,所以一定程度上Ⅲ不是很严谨。
    但是我要是改成“处理冲突时 尽!量!避免产生堆积效应”,那我反而认为它是对的。
    正常情况下我们利用线性探测法,遇到冲突会后移一位进行探测,最后很有可能后移多位;但是,如果选择平方探测呢?一定程度上其实是可以缓和堆积效应的,这样的话,也是有可能减少它的查找次数的,所以说“尽量避免产生堆积”这句话我觉得就相对来说更严谨一些,就差了“尽量”两个字。

最后,这道题我尊重王道编者的观点,但说实话,大部分人应该都会选择Ⅱ和Ⅲ,建议不要去钻牛角尖,通过这道题学会知识并且充分理解才是正道。
发表于 2019-05-17 20:58:12 回复(0)
刚刚
发表于 2019-05-26 07:53:56 回复(0)
影响散列表性能:
散列表是否均匀;
处理冲突的方法:链地址法处理冲突不会产生任何堆积,因而具有更加平均查找性能;
散列表的装填因子:填入表中记录越多,装填因子越大,产生冲突的可能性越大
发表于 2019-04-20 22:36:17 回复(0)