首页 > 试题广场 >

下列有关哈希查找法,错误的是( )

[单选题]
下列有关哈希查找法,错误的是(      )
  • 哈希表是一种计算式查找法
  • 可以通过改进哈希函数来减少冲突
  • 装填因子α越小,发生冲突的可能性越大
  • 哈希表的平均查找长度与带散列元素数目n无关

A: 哈希表——计算式查找法 定义:哈希法又称散列法、杂凑法或关键字地址计算法等,相应的表称为哈希表或散列表。 方法的基本思想:在元素的关键字 Key 和元素的存储位置 p 之间建立一个对应关系 H,使得 p = H(Key),H 称为哈希函数(散列函数),是一个压缩映象。 当需要查找关键字为 key 的元素时,利用哈希函数计算出该元素的存储位置 p = H(key),从而达到按关键字直接存取元素的目的。所以,哈希法既是一种存储方法,也是一种查找方法。 H(Key) 也称为哈希地址(又称散列地址)。把如此构造的表存储结构称为哈希表。

B,C: 在哈希表存储中,发生哈希冲突的可能性与装填因子α、所采用的哈希函数、解决冲突的哈希冲突函数三个因素有关。这是因为: (1)装填因子α是哈希表中已存入的数据元素n与哈希地址空间大小m的比值,即n/m,显然,当α越小时,冲突的可能性就越小,α越大 (最大可取1)时,冲突的可能性就越大; (2)若哈希函数选择得当,就可使哈希地址尽可能均匀地分布在哈希地址空间上,从而减少冲突的发生;否则,若哈希函数选择不当,就可能使哈希地址集中于某些区域,从而加大冲突的发生; (3)若哈希冲突函数选择得当,可以减少再次发生哈希冲突的可能性。

D: 查找成功时的平均查找长度 = 表中每个元素查找成功时的比较次数之和 / 表中元素个数;

发表于 2024-12-23 10:01:56 回复(0)