一个采用链地址法解决冲突的哈希表,其槽位数为m,当前已存储n个记录,设装载因子为α。若各个槽位上的链表长度的最大值为k,则下列哪一项描述最能体现哈希表的查找性能特征?

答案解析

链地址法中,平均查找长度主要受装载因子 α = n/m 影响。随着 α 的增大,链表平均长度增加,平均查找长度也增加,因此与 α 正相关。而 k 代表链表的最大长度,表示查找失败或找到链表末尾的探测次数上限,属于查找最坏情况的影响因素。平均查找长度取决于槽位链表平均长度,并不会直接受最长链表影响,仅仅最坏情况下的查找次数为k。A选项错误,k对平均查找长度有间接影响而非无关;B选项错误,平均查找长度与装载因子是正相关;D选项错误,平均查找长度与装载因子相关。C选项正确,准确描述了链地址法中α与平均查找长度的关系,以及k代表的意义。
正确答案:C
随机推荐
开始刷题