问题
单项选择题
以下关于哈希表的叙述中,错误的是()。
A.哈希表中元素的存储位置根据该元素的关键字值计算得到
B.哈希表中的元素越多,插入一个新元素时发生冲突的可能性就越小
C.哈希表中的元素越多,插入一个新元素时发生冲突的可能性就越大
D.哈希表中插入新元素发生冲突时,需要与表中某些元素进行比较
答案
参考答案:B
解析:
本题考查数据结构中哈希查找的基本概念。
哈希表是通过一个以记录的关键字为自变量的函数(称为哈希函数)得到该记录的存储地址而构造的查找表,所以在杂凑表中进行查找操作时,必须用同一哈希函数计算得到待查记录的存储地址,然后到相应的存储单元里去获得有关信息,再判定查找是否成功。
对于某个哈希函数H和两个关键字K1和K2,如果K1≠K2,而H(K1)=H(K2),则称为冲突。通常情况下,冲突只能尽可能减少而不能完全避免。
在一般情况下,冲突处理方法相同的哈希表,其平均查找长度依赖于哈希表的装填因子。哈希表的装填因子α定义为
[*]
α标志着哈希表的装满程度。直观地看,α越小,发生冲突的可能性就越小;反之,α越大,表中已填入的记录越多,再填记录时,发生冲突的可能性就越大,则查找时,给定值需与之进行比较的关键字的个数也就越多。