编程实现二中线性探查法和链地址法的ASL
时间: 2024-05-28 20:13:27 浏览: 34
二次探测法(Quadratic Probing)的平均查找长度(ASL):
ASL = (1 + 1/2 * (1-1/m)) / (1-p)
其中,m为散列表的长度,p为填充因子(哈希表中实际存储的元素个数与散列表长度的比值)。
链地址法(Chaining)的平均查找长度(ASL):
ASL = 1 + p * (1 + p/2) / (1-p)
其中,p为填充因子。
相关问题
编程实现二中线性探查法和链地址法的ASL思路
1. 二次探查法的 ASL 思路:
对于二次探查法,我们需要在哈希表中找到一个空闲位置来存储元素。如果当前位置已经被占用,则我们需要往后探查,直到找到一个空闲位置。具体的探查方法是:在当前位置 $i$ 上探查 $j=1,2,\cdots,m-1$ 步,即从 $i$ 开始分别向后探查 $1^2, 2^2, \cdots, (m-1)^2$ 步,直到找到一个空闲位置或者探查完整个哈希表。如果在探查的过程中找到了一个空闲位置,则把元素存储在这个位置上;否则,就认为哈希表已经满了。
对于二次探查法,它的 ASL 主要受以下两个因素的影响:
- 哈希表中已有的元素数量
- 哈希表的大小
因此,我们可以用以下公式表示二次探查法的 ASL:
$$ASL=\frac{1}{n}\sum_{i=1}^n T_i$$
其中,$n$ 表示哈希表中已有的元素数量,$T_i$ 表示在插入第 $i$ 个元素时进行探查的次数。
2. 链地址法的 ASL 思路:
对于链地址法,我们需要在哈希表中找到对应的链表,然后把元素插入到链表中。如果哈希表中已经存在一个链表,则我们需要遍历这个链表,找到一个空闲位置来存储元素。具体的插入方法是:先对关键字进行哈希,然后在哈希表中找到对应的链表,把元素插入到链表的末尾。
对于链地址法,它的 ASL 主要受以下两个因素的影响:
- 哈希表中已有的元素数量
- 每个链表的长度
因此,我们可以用以下公式表示链地址法的 ASL:
$$ASL=\frac{1}{n}\sum_{i=1}^n T_i$$
其中,$n$ 表示哈希表中已有的元素数量,$T_i$ 表示在插入第 $i$ 个元素时访问链表的次数。注意,访问链表的次数等于链表的长度加上 $1$,因为最后一个元素需要插入到链表的末尾。因此,$T_i$ 可以表示为 $T_i=L_i+1$,其中 $L_i$ 表示插入第 $i$ 个元素时对应链表的长度。
假定对线性表(38,25,74,52,48)进行散列存储,采用H(K)=K%7作为散列函数,若分别采用线性探查法和链接法处理冲突,则对各自散列表进行查找的平均查找长度分别为_
首先,根据散列函数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。