编程实现二中线性探查法和链地址法的ASL思路
时间: 2024-05-31 21:14:13 浏览: 9
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$ 个元素时对应链表的长度。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)