用关键字序列{1,9,12,11,25,35,17,29}创建一个哈希表,装填因子a=1/2,确定表长m,采用除留余数法构造哈希函数,通过链地址法来处理冲突。 (1)求m的值; (2)画出哈希表; (2)求在等概率情况下,查找成功和查找失败的平均查找长度。
时间: 2024-06-13 10:08:35 浏览: 125
(1)根据装填因子a=1/2,可知每个桶的平均填充因子为0.5,即每个桶最多存放一个关键字。因此,哈希表的长度m应该为关键字个数n的两倍,即m=2n=16。
(2)画出哈希表如下所示:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |10 |11 |12 |13 |14 |15 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| | | | | | | | | | | | | | | | |
(3)在等概率情况下,查找成功的平均查找长度为(1+2)/2=1.5,即查找成功的关键字在哈希表中的位置与其在关键字序列中的位置相同,平均查找长度为1;查找失败的平均查找长度为(1+2+3)/3=2,即查找失败的关键字需要遍历哈希表中的两个桶,平均查找长度为2。
相关问题
有关键字序列{32,53,78,12,25,62,43},哈希函数H(K)=Kmod7,用线性探测再散列方法处理冲突,要求构造一个装填因子为0.7的哈希表,并计算查找成功时的平均查找长度。
对于关键字序列{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。
有关键字序列{32,53,78,12,25,62,43},哈希函数H(K)=K+mod+7,用线性探测再散列方法处理冲突,要求构造一个装填因子为0.7的哈希表,并计算查找成功时的平均查找长度。
根据题意,关键字序列为{32,53,78,12,25,62,43},哈希函数为H(K)=K+mod+7,使用线性探测再散列法处理冲突,要求构造一个装填因子为0.7的哈希表,并计算查找成功时的平均查找长度。
首先,计算哈希表的大小,由于装填因子为0.7,因此哈希表的大小为10。
其次,根据哈希函数,计算每个关键字的哈希地址:
- H(32) = 32 + 7 % 10 = 9
- H(53) = 53 + 7 % 10 = 0
- H(78) = 78 + 7 % 10 = 5
- H(12) = 12 + 7 % 10 = 9(冲突)
- H(25) = 25 + 7 % 10 = 2
- H(62) = 62 + 7 % 10 = 9(冲突)
- H(43) = 43 + 7 % 10 = 0(冲突)
由于发生了冲突,需要使用线性探测再散列法解决。具体方法是,从发生冲突的位置开始,依次向后查找空闲位置,直到找到一个空闲位置或者查找到整个哈希表。如果查找到整个哈希表,就从头开始查找,直到找到一个空闲位置。
- H(12) = 9,发生冲突,从9开始向后查找,直到找到空闲位置3
- H(62) = 9,发生冲突,从9开始向后查找,直到找到空闲位置4
- H(43) = 0,发生冲突,从0开始向后查找,直到找到空闲位置1
因此,哈希表为:[53, 43, 78, 12, 25, 62, 32, None, None, None]
计算查找成功时的平均查找长度,需要先计算查找成功的概率。由于哈希函数是随机的,因此每个关键字的哈希地址是等概率的,查找成功的概率也是相等的。因此,查找成功的概率为1/7。
平均查找长度=查找成功的概率*成功查找所需的比较次数=1/7*1=1/7
阅读全文
相关推荐













