有关键字序列{32,53,78,12,25,62,43},哈希函数H(K)=Kmod7,用线性探测再散列方法处理冲突,要求构造一个装填因子为0.7的哈希表,并计算查找成功时的平均查找长度。
时间: 2024-06-13 13:08:47 浏览: 98
Hash表存储数据,用再散列来解决地址冲突问题,计算平均查找长度,还可以通过Key值查找对应的value
对于关键字序列{32,53,78,12,25,62,43},哈希函数H(K)=Kmod7,用线性探测再散列方法处理冲突,要求构造一个装填因子为0.7的哈希表,并计算查找成功时的平均查找长度。
首先,根据装填因子为0.7,我们可以计算出哈希表的大小为10(即7/0.7向上取整)。
接下来,我们需要对关键字序列进行哈希。根据哈希函数H(K)=Kmod7,我们可以得到以下哈希地址:
32 -> 4
53 -> 4(冲突,线性探测再散列,+1后为5)
78 -> 1
12 -> 5
25 -> 4(冲突,线性探测再散列,+2后为6)
62 -> 6
43 -> 1(冲突,线性探测再散列,+3后为4)
因此,得到的哈希表为:
[None, 78, None, None, 32, 53, 43, 12, None, 62]
接下来,我们需要计算查找成功时的平均查找长度。由于这里只有7个关键字,我们可以直接枚举每个关键字进行计算。假设我们要查找的关键字为K,其哈希地址为i,那么平均查找长度为:
(1/7) * [(1/1) + (2/2) + (1/3) + (1/1) + (2/2) + (1/1) + (3/3)] = 1.857
因此,当装填因子为0.7时,查找成功时的平均查找长度为1.857。
阅读全文