假定有一个 7 个槽的散列表(槽从 0 到 6 编号)。如果使用散列函数 h(k) = k mod 7 和线性探查,在插入值为 3、12、9、2 的关键码后,列出每一个空槽作为下一个被填充槽的概率。并给出理由
时间: 2023-06-06 09:06:53 浏览: 98
散列表的大小为7,散列函数h(k) = k mod 7。在线性探查法下,依次插入关键码3, 12, 9, 2。
在插入3时,h(3) = 3 mod 7,3被存放在槽3。此时槽0、槽1、槽2、槽4、槽5、槽6均为空。
在插入12时,h(12) = 12 mod 7,12被存放在槽5。此时槽0、槽1、槽2、槽4、槽6均为空,槽3中有3,槽5中有12。
在插入9时,h(9) = 9 mod 7,9被存放在槽2。此时槽0、槽1、槽4、槽6均为空,槽3中有3,槽5中有12,槽2中有9。
在插入2时,h(2) = 2 mod 7,2被存放在槽2(发生了冲突,进行线性探查,先检查槽3,槽3已被占用,继续检查槽4,槽4为空,2被存放在槽4)。此时槽0、槽1、槽6均为空,槽3中有3,槽5中有12,槽2中有9,槽4中有2。
因此,下一个被填充的空槽分别为:
槽0:填充的概率为0,因为哈希函数h(k)对10取模所得的值为0的元素不可能再被填充进散列表。
槽1:填充的概率为0,因为哈希函数h(k)对10取模所得的值为1的元素不可能再被填充进散列表。
槽2:填充的概率为1/7,因为要填充到槽2的元素只有9和2,但是2已经占用了槽4,因此只有9能够填充到槽2。
槽3:填充的概率为0,因为槽3已经被填充了。
槽4:填充的概率为1/7,因为要填充到槽4的元素只有2,但是2已经占用了槽4,因此概率为1/7。
槽5:填充的概率为0,因为槽5已经被填充了。
槽6:填充的概率为0,因为哈希函数h(k)对10取模所得的值为6的元素不可能再被填充进散列表。
理由如上。
相关问题
假定有一个 7 个槽的散列表(槽从 0 到 6 编号)。如果使用散列函数 h(k) = k mod 7 和线性探查,作用于一组数字 3、12、9、2,给出每次插入数字后的散列表,并给出示意图
好的,我理解了你的要求。下面是对于给定数字的插入过程中的散列表和示意图:
1. 插入数字 3:
散列表:
[ , , , , , ,3]
0 1 2 3 4 5 6
示意图:
| | | | | | |3|
|0 |1 |2 |3 |4 |5 |6|
2. 插入数字 12:
散列表:
[ , ,12, , , ,3]
0 1 2 3 4 5 6
示意图:
| | |12| | | |3|
|0 |1 |2 |3 |4 |5 |6|
3. 插入数字 9:
散列表:
[ ,9,12, , , ,3]
0 1 2 3 4 5 6
示意图:
| |9 |12| | | |3|
|0 |1 |2 |3 |4 |5 |6|
4. 插入数字 2:
散列表:
[2,9,12, , , ,3]
0 1 2 3 4 5 6
示意图:
|2 |9 |12| | | |3|
|0 |1 |2 |3 |4 |5 |6|
希望以上能帮到你,有什么问题可以随时向我提出。
假定对线性表(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。
相关推荐
![sh](https://img-home.csdnimg.cn/images/20210720083646.png)
![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)