首页 > 试题广场 >

解决hash冲突的方法描述错误的有？

[单选题]

解决hash冲突的方法描述错误的有？

开放定址法解决冲突的做法是：当冲突发生时，使用某种探查(亦称探测)技术在散列表中形成一个探查(测)序列。沿此序列逐个单元地查找，直到找到给定 的关键字，或者碰到一个开放的地址(即该地址单元为空)为止。

拉链法解决冲突的做法是：将所有关键字为同义词的结点链接在同一个单链表中

拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短

当结点规模较大时，开放定址法较为节省空间

推荐

飞鸟_11

与开放定址法相比，拉链法有如下几个优点：
(1)拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
(2)由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
(3)开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；
(4)在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表，删除结点不能简单地将被删结点的空间置为空，否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中，空地址单元(即开放地址)都是查找失败的条件。因此在用开放地址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点。

编辑于 2018-05-24 11:00:15 回复(2)

revivedSuN

具有相同函数值的关键字对该哈希函数来说称为同义词

发表于 2015-09-05 16:57:59 回复(0)

本命年的Offer！

一言不合就看错题，错误的是。。。

发表于 2017-10-08 08:44:30 回复(2)

国航

答案：D。 ①拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短； ②由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况； ③开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间。

发表于 2015-09-14 00:24:32 回复(0)

天尊墨宇

选D
与开放定址法相比，拉链法有如下几个优点：
(1)拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
(2)由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
(3)开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；
(4)在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表，删除结点不能简单地将被删结点的空间置为空，否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中，空地址单元(即开放地址)都是查找失败的条件。因此在用开放地址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点。

发表于 2020-07-18 06:47:45 回复(0)