哈希表 链地址法 装填因子

哈希表是一种常用的数据结构，用于实现快速的查找和插入操作。其中，链地址法是一种解决哈希冲突（即多个关键字映射到同一个哈希桶）的方法之一，通过在哈希表的每个桶中使用链表来存储冲突的元素。

装填因子是衡量哈希表负载程度的一个指标，定义为当前哈希表中已存储元素个数与总桶数之比。装填因子越大，表示哈希表中元素越多，可能导致冲突的概率增加，查找和插入操作的平均时间复杂度也会增加。通常情况下，当装填因子超过一个设定的阈值时，需要进行哈希表的扩容操作，以保持较低的装填因子，提高哈希表的性能。

相关问题

简述哈希表中的装填因子

哈希表中的装填因子是指哈希表中已经存储的元素数量与哈希表大小的比值。它可以用来衡量哈希表的空间利用率和性能。装填因子越大，表示哈希表中已经存储的元素越多，空间利用率越高，但同时也会增加哈希冲突的概率，导致性能下降。装填因子越小，表示哈希表中已经存储的元素较少，空间利用率较低，但哈希冲突的概率较小，性能相对较好。

通常情况下，装填因子的取值范围为0到1之间。当装填因子超过某个阈值（如0.7或0.8）时，就需要对哈希表进行扩容操作，以保持较低的装填因子，从而提高哈希表的性能。

装填因子的计算公式为：
装填因子 = 哈希表中已存储元素的数量 / 哈希表的大小

用关键字序列{1，9，12，11，25，35，17，29}创建一个哈希表，装填因子a=1/2，确定表长m，采用除留余数法构造哈希函数，通过链地址法来处理冲突。 （1）求m的值； （2）画出哈希表； （2）求在等概率情况下，查找成功和查找失败的平均查找长度。

（1）根据装填因子a=1/2，可知每个桶的平均填充因子为0.5，即每个桶最多存放一个关键字。因此，哈希表的长度m应该为关键字个数n的两倍，即m=2n=16。

（2）画出哈希表如下所示：

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |10 |11 |12 |13 |14 |15 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| | | | | | | | | | | | | | | | |

（3）在等概率情况下，查找成功的平均查找长度为(1+2)/2=1.5，即查找成功的关键字在哈希表中的位置与其在关键字序列中的位置相同，平均查找长度为1；查找失败的平均查找长度为(1+2+3)/3=2，即查找失败的关键字需要遍历哈希表中的两个桶，平均查找长度为2。