假定对线性表(38,25,74,52,48)进行散列存储,采用H(K)=K%7作为散列函数,若分别采用线性探查法和链接法处理冲突,则对各自散列表进行查找的平均查找长度分别为_
时间: 2024-04-05 09:32:47 浏览: 224
haxibiao.rar_MOD_哈希表 平均查找长度
5星 · 资源好评率100%
首先,根据散列函数H(K)=K%7,可以得到以下散列表:
|位置|线性探查法|链接法|
|:-:|:-:|:-:|
|0| | |
|1| | |
|2| | |
|3|52| |
|4|25|48->38|
|5|74| |
|6| | |
其中,线性探查法是指当发生冲突时,依次向后查找下一个位置,直到找到空位置为止。链接法是指将散列到同一位置的元素以链表的形式存储在该位置上。
平均查找长度是指查找某个元素时,需要访问的节点数的期望值。对于线性探查法,平均查找长度可以通过以下公式计算:
ASL = (1+1/2+1/3+...+1/m)*(1/(1-a))
其中,m为散列表的长度,a为填充因子(已存储元素个数/散列表长度)。将数据填入公式中,得到:
ASL(linear) = (1+1/2+1/3+1/4+1/5)*(1/(1-5/7)) = 2.4
对于链接法,平均查找长度可以通过以下公式计算:
ASL = 1+a/2
其中,a为填充因子。将数据填入公式中,得到:
ASL(linked) = 1+(5-1)/2 = 2
因此,采用线性探查法处理冲突时,对散列表进行查找的平均查找长度为2.4;采用链接法处理冲突时,对散列表进行查找的平均查找长度为2。
阅读全文