链地址法中装填因子的求解(附带王道数据结构课后习题) | 您所在的位置:网站首页 › 哈希表的链地址法 › 链地址法中装填因子的求解(附带王道数据结构课后习题) |
1、链地址法中装填因子的定义
链地址法,又称分离链接法,是用于从处理散列函数构造冲突的一种办法。设散列函数得到的散列地址域在区间[0,M-1] ,关键字记录总数为N,则把链地址表中每个链表的平均长度定义为装填因子α,即α=N/M。 NOTICE!!:先要知道散列地址的范围,才能使用链地址法。 [参考]:《数据结构》(第2版),陈越、何钦铭、徐镜春、魏宝刚、杨枨 编著,高等教育出版社,2016年6月 2、相关例题此题来源于2022王道数据结构一书 已知一组关键字为(26,36,41,38,44,15,68,12,6,51,25),用链地址法解决冲突。假设装填因子a=0.75,散列函数的形式为H(key)=key% P,回答下列问题: (1)构造出散列函数,画出散列表。 解答:关键字总数为11,由装填因子α的定义,可知11/p=0.75 ,解得P=15(向上取整)。因此散列地址的范围为【0,14】。因此散列函数为 H(key)=key% 15 相应散列表为: |
CopyRight 2018-2019 实验室设备网 版权所有 |