首页 > 试题广场 >

下述有关hash冲突时候的解决方法的说法，错误的有？

[单选题]

通常有两类方法处理冲突：开放定址(Open Addressing)法和拉链(Chaining)法。

开放定址更适合于造表前无法确定表长的情况

在用拉链法构造的散列表中，删除结点的操作易于实现

拉链法的缺点是：指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间

查看正确选项

yunyang088

由于拉链法中各链表上的结点空间是动态申请的,故它更适合于造表前无法确定表长的情况

发表于 2015-03-27 21:08:08 回复(0)

sunlight_run

A：处理冲突方法：开放地址法和拉链法

B：拉链法的节点空间动态申请更适合无法确定表长的情况

C：想象其中有链表

D：规模较小，查找比较容易，用开放地址法能省空间

编辑于 2017-06-17 16:11:06 回复(0)

选择困难症2333

一个关键字会映射到同一个位桶中的情况，这种情况就就叫做哈希冲突。

1. 解决哈希冲突的方法包括拉链法（也叫作链接法、链地址法），开放地址法等。

2. 在每个位桶实现的时候，我们采用链表的数据结构来去存取发生哈希冲突的输入域的关键字。主要的操作包括
1）插入操作：在发生哈希冲突的时候，我们输入域的关键字去映射到位桶中时，先检查带插入元素x是否出现在表中，查找所用的次数不会超过装载因子（n/m:n为输入域的关键字个数，m为位桶的数目），它是个常数，所以插入操作的最坏时间复杂度为O(1)的。

2）查询操作：和1）一样，在发生哈希冲突的时候，我们去检索的时间复杂度不会超过装载因子，也就是检索数据的时间复杂度也是O(1)的

3）删除操作：如果在拉链法中我们想要使用链表这种数据结构来实现位桶，那么这个链表一定是双向链表，因为在删除一个元素x的时候，需要更改x的前驱元素的next指针的属性，把x从链表中删除。这个操作的时间复杂度也是O(1)的。

3. 开放地址法将所有输入的元素全部存放在哈希表里，位桶的实现是不需要任何的链表，哈希表的装载因子不会超过1。它的实现是在插入一个元素的时候，先通过哈希函数进行判断，若是发生哈希冲突，就以当前地址为基准，根据再寻址的方法（探查序列），去寻找下一个地址，若发生冲突再去寻找，直至找到一个为空的地址为止。所以这种方法又称为再散列法。
有几种常用的探查序列的方法：线性探查、二次探查、伪随机探测等。

4. 对比：拉链法的优点 1）拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；2）对于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；3）开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；4）在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。
拉链法的缺点：指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放定址法中的冲突，从而提高平均查找速度。

ACD正确。B，拉链法更适合无法确定表长的情况。