为以下关键字构造装填因子不小于0.75的哈希表,并给出平均查找长度。{ZHAO, QIAN, SUN, LI, ZHOU, WU, ZHENG, WANG, CHANG, CHAO, YANG, JIN}
时间: 2023-10-08 11:13:13 浏览: 74
我们可以使用除留余数法来构造哈希表。具体步骤如下:
1. 定义哈希表大小为13,选取一个较大的质数作为除数。
2. 对于每个关键字,计算其哈希值,即将各个字符的ASCII码相加,再对哈希表大小取余。
例如,对于关键字"ZHAO",其哈希值为 (90 + 72 + 65 + 79) % 13 = 7。
3. 如果该位置尚未被占用,则将关键字存入该位置;否则,使用线性探测法寻找下一个可用位置。
例如,对于关键字"ZHAO",其哈希值为7,因此存入哈希表的第7个位置。对于关键字"QIAN",其哈希值为(81 + 73 + 65 + 78) % 13 = 6,由于哈希表的第6个位置已被占用,因此从第7个位置开始依次查找,直到找到一个空位置为止。最终,关键字"QIAN"存入哈希表的第8个位置。
4. 计算装填因子,即已经存储的关键字数除以哈希表大小。如果装填因子大于等于0.75,则需要重新调整哈希表大小,常见的方式是将其扩大一倍并重新插入所有关键字。
在本例中,共有12个关键字,因此装填因子为12/13 ≈ 0.92,已经超过了0.75,因此需要重新调整哈希表大小。扩大后的哈希表大小为26,重新计算每个关键字的哈希值,并插入到新的哈希表中。
5. 平均查找长度为每个关键字在哈希表中查找的次数的平均值,即每个关键字在查找时需要查找的次数之和除以关键字总数。
在本例中,12个关键字在哈希表中的查找次数依次为1、1、1、1、2、1、1、1、2、2、2、2,因此平均查找长度为 (1 + 1 + 1 + 1 + 2 + 1 + 1 + 1 + 2 + 2 + 2 + 2) / 12 ≈ 1.5。
最终的哈希表如下:
```
0: WANG
1: SUN
2: JIN
3: CHANG
4: -
5: ZHENG
6: QIAN
7: ZHAO
8: LI
9: YANG
10: CHAO
11: WU
12: ZHOU
```
平均查找长度为1.5。