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

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

Ⅰ.增大装填(载)因子

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

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


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

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

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

在王道中的版本如下:


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

最后,这道题我尊重王道编者的观点,但说实话,大部分人应该都会选择Ⅱ和Ⅲ,建议不要去钻牛角尖,通过这道题学会知识并且充分理解才是正道。
编辑于 2020-01-05 06:50:18 回复(0)
散列因子,又叫装填(装载)因子,用来描述哈希表的密集程度。
a = 元素个数 / 哈希表长度
a 越大,产生冲突的概率就越大,a越小,空间浪费就大,散列因子一般控制在0.7~0.8左右。
并不是越大越好,也不是越小越好。如果仅仅是单一为了提高查找效率,散列因子越小,查找效率越高。
发表于 2020-04-08 01:19:10 回复(0)
填充因子越多,越容易产生冲突
发表于 2020-03-20 06:03:57 回复(0)
刚刚
发表于 2019-05-26 07:53:56 回复(0)
影响散列表性能:
散列表是否均匀;
处理冲突的方法:链地址法处理冲突不会产生任何堆积,因而具有更加平均查找性能;
散列表的装填因子:填入表中记录越多,装填因子越大,产生冲突的可能性越大
发表于 2019-04-20 22:36:17 回复(0)