已知哈希函数为:H(k)=k%11,表长为11,采用线性探测再散列解决冲突,对下列关键字序列{21,66,99,98,2,49} (1)构造哈希表; (2)求出等概率下查找成功时的平均查找长度。
时间: 2024-03-30 12:33:54 浏览: 47
选取哈西函数h(k)=k%11,用线性探测在散列方法处理冲突。是
5星 · 资源好评率100%
好的,我来回答你的问题。
首先,根据给出的哈希函数和表长,我们可以得到哈希表的下标范围为0~10。
(1) 接下来,我们按照线性探测再散列的方法,将关键字序列插入哈希表中。
首先,将21插入哈希表中,计算其哈希值为10,将其插入哈希表中的第10个位置。
然后,将66插入哈希表中,计算其哈希值为0,但是0位置已经有了关键字21,因此需要进行线性探测再散列。按照线性探测的规则,依次往后查找,直到找到一个空位置插入。因此,将66插入哈希表中的第1个位置。
接下来,将99插入哈希表中,计算其哈希值为10,但是10位置已经有了关键字21和66,因此需要进行线性探测再散列。依次往后查找,直到找到一个空位置插入。因此,将99插入哈希表中的第2个位置。
然后,将98插入哈希表中,计算其哈希值为9,将其插入哈希表中的第9个位置。
接着,将2插入哈希表中,计算其哈希值为2,将其插入哈希表中的第2个位置。
最后,将49插入哈希表中,计算其哈希值为5,将其插入哈希表中的第5个位置。
因此,构造出的哈希表如下所示:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|----|
|66 |99 |2 | | |49 |21 | | |98 |21 |
(2) 接下来,我们需要求出等概率下查找成功时的平均查找长度。这里我们可以采用公式ASL = (1/λ)*Σ(pi*(1+di)),其中λ为填入表中的记录数与表长的比值,pi为查找表中第i个记录的概率,di为查找表中第i个记录的查找长度减1。
由于等概率下每个关键字被查找的概率都相等,因此pi=1/6。
计算λ的值为n/m,其中n为填入表中的记录数,m为表长。由于填入表中的记录数为6,表长为11,因此λ=6/11。
接下来,我们需要计算每个关键字的查找长度。以关键字21为例,它在哈希表中的位置为10和0,因此它的查找长度为(1+1)/2=1。同理,我们可以求出其他关键字的查找长度。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|----|
|66 |99 |2 | | |49 |21 | | |98 |21 |
|1 |1 |1 | | |1 |1 | | |1 |1 |
最后,代入公式ASL = (1/λ)*Σ(pi*(1+di))中,我们可以得到等概率下查找成功时的平均查找长度为(1/6)*[(1+1)+(1+1)+(1+1)+(1+1)+(1+1)+(1+1)]=2。
因此,该哈希表等概率下查找成功时的平均查找长度为2。
阅读全文