问题 单项选择题

以下关于哈希表的叙述中,错误的是()。

A.哈希表中元素的存储位置根据该元素的关键字值计算得到

B.哈希表中的元素越多,插入一个新元素时发生冲突的可能性就越小

C.哈希表中的元素越多,插入一个新元素时发生冲突的可能性就越大

D.哈希表中插入新元素发生冲突时,需要与表中某些元素进行比较

答案

参考答案:B

解析:

本题考查数据结构中哈希查找的基本概念。

哈希表是通过一个以记录的关键字为自变量的函数(称为哈希函数)得到该记录的存储地址而构造的查找表,所以在杂凑表中进行查找操作时,必须用同一哈希函数计算得到待查记录的存储地址,然后到相应的存储单元里去获得有关信息,再判定查找是否成功。

对于某个哈希函数H和两个关键字K1和K2,如果K1≠K2,而H(K1)=H(K2),则称为冲突。通常情况下,冲突只能尽可能减少而不能完全避免。

在一般情况下,冲突处理方法相同的哈希表,其平均查找长度依赖于哈希表的装填因子。哈希表的装填因子α定义为

[*]

α标志着哈希表的装满程度。直观地看,α越小,发生冲突的可能性就越小;反之,α越大,表中已填入的记录越多,再填记录时,发生冲突的可能性就越大,则查找时,给定值需与之进行比较的关键字的个数也就越多。

多项选择题
单项选择题