计算散列函数查找不成功的平均查找长度

Question

1．设散列函数H(k)=k % 13,设关键字系列为{22,12,24,6,45,7,8,13,21},要
求用线性探测法处理冲突。(6分)
(1) 构造HASH表。
(2) 分别求查找成功和不成功时的平均查找长度。

它这个查找不成功是不是不对啊，不应该是（3+2+10+9+8+7+6+5+4)吗

Answer 1

不知道你这个问题是否已经解决, 如果还没有解决的话:

• 以下回答来自chatgpt: 解决方案: 首先，我们需要根据散列函数 H(k) = k % 13 来构造一个基于散列函数的HASH表。 1.构建哈希表: 我们可以定义一个大小为13的数组来表示哈希表。根据散列函数，我们可以将所有关键字依次插入到哈希表中。如果发生冲突，我们使用线性探测法。 具体步骤如下： a. 首先，我们将大小为13的数组（下标从0开始）初始化为-1，表示哈希表中的槽位都是空的。 b. 然后，我们使用散列函数将第一个关键字22插入哈希表中。由于22 % 13 = 9，所以我们将它插入槽位为9的位置。此时，哈希表变为：[-1, -1, -1, -1, -1, -1, -1, -1, -1, 22, -1, -1, -1]。 c. 接着，我们使用同样的方法将其他关键字插入到哈希表中。当我们发现某个位置已经被占用时，我们就沿着哈希表顺序查找下一个空的槽位，并将关键字插入到那里。如果到达哈希表的尾部时还没有找到空的槽位，我们就回到哈希表的开头继续查找。当所有关键字都插入到哈希表中时，哈希表变为：[6, 12, 7, -1, -1, -1, -1, -1, -1, 22, 8, 13, 24]。 实现代码如下： ```python hash_table = [-1] * 13 keys = [22, 12, 24, 6, 45, 7, 8, 13, 21] # Insert keys into the hash table for key in keys: index = key % 13 while hash_table[index] != -1: index = (index + 1) % 13 hash_table[index] = key print(hash_table) ``` 2.计算平均查找长度: 接下来，我们需要计算成功查找和不成功查找时的平均查找长度。平均查找长度是指在查找一个元素时，需要访问的关键字的个数的期望值。我们可以根据公式 L = (f_1*d_1 + f_2*d_2 + ... + f_n*d_n) / S 来计算平均查找长度，其中 f_i 是查找第i个关键字的概率，d_i 是查找第i个关键字时需要访问的关键字的个数，n 是总共要查找的关键字的个数，S 是哈希表的大小。 对于不成功的查找，我们可以通过插入一个不存在的元素来模拟。在这种情况下，我们需要查找的所有关键字都是哈希表中不存在的元素，这意味着它们都需要访问哈希表中的所有槽位。 因此，不成功查找时的平均查找长度为 (13+1)/2=7。 对于成功查找，我们需要计算每个关键字被访问的概率以及访问它们时需要访问的关键字的个数。我们可以模拟单次查找过程，记录下每个关键字被遍历的情况，然后计算概率。 具体步骤如下： a. 对于每个关键字，我们首先计算它在哈希表中的位置，然后沿着这个位置顺序查找下一个关键字。如果我们找到了目标关键字，我们就停止查找并记录遍历的关键字个数。如果没有找到目标关键字，我们就沿着哈希表的顺序继续查找下一个关键字，直到找到目标关键字或者哈希表的结尾。 b. 计算每个关键字被访问的概率。由于关键字是随机插入的，因此每个关键字被查找的概率相等，即 1/n。 c. 计算每个关键字被访问时需要访问的关键字的个数。这个数量等于该关键字在哈希表中的位置与它被找到时的位置之间相隔的关键字个数。因此，如果一个关键字被找到时的位置为 i，它在哈希表中的位置为 j，那么访问该关键字时需要遍历的关键字个数为 (i-j+13)%13。 d. 计算平均查找长度。按照公式 L = (f_1*d_1 + f_2*d_2 + ... + f_n*d_n) / S 计算即可。 实现代码如下： ```python # Compute the average search length of successful searches total_length = 0 for key in keys: index = key % 13 distance = 0 while hash_table[index] != key: index = (index + 1) % 13 distance += 1 distance += 1 total_length += distance * 1/len(keys) print("The average search length of successful searches is:", total_length) # Compute the average search length of unsuccessful searches total_length = sum([(i+1)/2 for i in range(len(hash_table))]) / len(hash_table) print("The average search length of unsuccessful searches is:", total_length) ``` 提示: 1. 在代码实现中，我们可以使用哈希表来存储每个关键字的位置，而不是使用线性探测法来查找它们。这样可以避免在计算平均查找长度时重复计算相同的距离。 2. 在使用线性探测法解决冲突时，我们需要注意哈希表的大小和关键字的分布情况，以避免出现太多的冲突。在这个例子中，由于哈希表的大小为13，而关键字序列中的最大值为45，因此可以保证最多只有一次冲突。如果关键字的分布情况更为集中，可能需要使用更大的哈希表来降低冲突的概率。

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^