哈希关键字冲突 查找的平均长度

哈希关键字冲突查找的平均长度是指在哈希表中查找一个关键字时，需要查找的次数的平均值。它与哈希表的装载因子有关，装载因子越大，冲突的概率就越大，平均查找长度也就越大。因此，在设计哈希表时，需要合理选择哈希函数和调整哈希表的大小，以尽可能减少冲突的发生，提高查找效率。

相关问题

[问题描述] 为班级30个人的姓名设计一个哈希表，平均查找长度的上限为2，完成相应的建表和查表 [基本要求] 姓名使用汉语拼音表示，用除留余数法构造哈希函数，用线性探测再散列法处理冲突; 可以显示哈希表，输入人名后，查找成功则显示姓名、关键字、存储位置及平均查找长度等信息，找不到给出对应提示。

好的，我会针对你的问题进行回答。

首先，根据你的要求，我们需要设计一个哈希表来存储30个人的姓名，且平均查找长度的上限为2。为了实现这个目标，我们可以采用除留余数法构造哈希函数，用线性探测再散列法处理冲突。

具体步骤如下：

1. 首先确定哈希表的大小，由于我们只需要存储30个人的姓名，可以选择哈希表的大小为31，因为31是一个质数，有利于减少冲突的发生。

2. 然后根据哈希函数，将每个人的姓名映射到哈希表中的一个位置上。假设我们使用汉语拼音表示每个人的姓名，那么可以将每个姓名的首字母的ASCII码值相加，然后取余数得到该姓名在哈希表中的位置。具体公式如下：

   hash(key) = (key[0] + key[1] + ... + key[n-1]) % 31

其中，`key`表示每个人的姓名。

3. 如果发生冲突，即两个人的姓名映射到了同一个位置上，我们可以使用线性探测再散列法来解决。具体的做法是，从发生冲突的位置开始，依次向后查找，直到找到一个空闲位置或者查找了整个哈希表。如果找到了空闲位置，就将该姓名存储在该位置上；否则，就重新计算哈希值，继续查找下一个位置，直到找到一个空闲位置为止。

4. 最后，为了保证平均查找长度的上限为2，我们需要控制哈希表的装载因子。装载因子是指已经存储的数据占哈希表总大小的比例。通常情况下，装载因子不宜超过0.7，否则会导致冲突的频率过高，影响查找效率。因此，在本例中，我们可以设置哈希表的最大容量为43（31/0.7），当哈希表中已经存储了43个人的姓名时，就需要重新构建一个更大的哈希表来存储数据。

完成建表后，我们可以输入人名进行查找。具体操作如下：

1. 输入要查找的人名，将其转换为哈希表中的位置。

2. 如果该位置上存储的姓名与要查找的姓名相同，说明查找成功，输出该人名、关键字、存储位置及平均查找长度等信息。

3. 如果该位置上存储的姓名与要查找的姓名不同，说明发生了冲突，需要继续向后查找，直到找到空闲位置或者查找了整个哈希表。

4. 如果找到空闲位置，说明要查找的人名不存在，给出对应提示。

5. 如果查找了整个哈希表，仍然没有找到要查找的人名，也给出对应提示。

最后，为了方便查看哈希表中的存储情况，可以编写一个显示哈希表的函数，将哈希表中每个位置上存储的数据都输出到屏幕上。

设哈希表的地址范围为0～17，哈希函数为：H（key）=key。用线性探测法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49），构造哈希表，试回答下列问题： ① 画出哈希表的示意图； ② 若查找关键字63，需要依次与哪些关键字进行比较？ ③ 若查找关键字60，需要依次与哪些关键字比较？ ④ 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。

好的，我来回答你的问题：

① 画出哈希表的示意图：

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
|---|---|---|---|---|---|---|---|---|---|----|----|----|----|----|----|----|----|
| | | | | | | | | | | 10 | | | | | 24 | 17 | 31 |
| 30| 32| | | | | | | 40| | | | | | 46 | 47 | | |
| | | 63| | 49| | | | | | | | | | | | | |

其中，横向的行表示哈希表的地址范围，纵向的列表示哈希表中存储的关键字。

② 若查找关键字63，需要依次与哪些关键字进行比较？

首先，根据哈希函数 H（key）=key % 18，可以计算出关键字63的哈希地址为 H（63）= 63 % 18 = 9。在哈希表中，第9个位置存储的是空的，因此需要继续往后查找。依次比较的关键字为：10，24，32，17，31，30，46，47，40，63。

③ 若查找关键字60，需要依次与哪些关键字比较？

同样地，根据哈希函数 H（key）=key % 18，可以计算出关键字60的哈希地址为 H（60）= 60 % 18 = 6。在哈希表中，第6个位置存储的是空的，因此需要继续往后查找。依次比较的关键字为：32，17，31，30，46，47，40，63，10，24。

④ 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。

设哈希表的长度为m，关键字的个数为n，则哈希表的装载因子为α = n / m。

由于使用的是线性探测法，当发生冲突时，需要依次查找下一个空闲位置，因此平均查找长度为：

ASL = (1/α) * ln(1/(1-α)) ≈ 5.55

因此，当查找成功时，平均需要比较5.55个关键字。