为以下关键字构造装填因子不小于0.75的哈希表,并给出平均查找长度。{ZHAO, QIAN, SUN, LI, ZHOU, WU, ZHENG, WANG, CHANG, CHAO, YANG, JIN}
时间: 2023-07-27 14:17:37 浏览: 64
为了构造装填因子不小于0.75的哈希表,我们需要选取合适的哈希函数和合适数组长度。这里我们选择哈希函数为除留余数法,数组长度为16(大于关键字数目12的最小素数)。
具体构造过程如下:
1. 定义哈希函数:h(key) = key % 16。
2. 创建长度为16的哈希表,并初始化为空。
3. 将每个关键字插入哈希表中:
- 插入关键字ZHAO,h(ZHAO) = 11,将ZHAO插入哈希表的第11个位置。
- 插入关键字QIAN,h(QIAN) = 14,将QIAN插入哈希表的第14个位置。
- 插入关键字SUN,h(SUN) = 13,将SUN插入哈希表的第13个位置。
- 插入关键字LI,h(LI) = 6,将LI插入哈希表的第6个位置。
- 插入关键字ZHOU,h(ZHOU) = 0,将ZHOU插入哈希表的第0个位置。
- 插入关键字WU,h(WU) = 11,将WU插入哈希表的第11个位置,由于第11个位置已经有一个关键字ZHAO,因此需要使用开放地址法(线性探测)解决冲突,将WU插入哈希表的第12个位置。
- 插入关键字ZHENG,h(ZHENG) = 2,将ZHENG插入哈希表的第2个位置。
- 插入关键字WANG,h(WANG) = 8,将WANG插入哈希表的第8个位置。
- 插入关键字CHANG,h(CHANG) = 4,将CHANG插入哈希表的第4个位置。
- 插入关键字CHAO,h(CHAO) = 2,将CHAO插入哈希表的第2个位置,由于第2个位置已经有一个关键字ZHENG,因此需要使用开放地址法(线性探测)解决冲突,将CHAO插入哈希表的第3个位置。
- 插入关键字YANG,h(YANG) = 2,将YANG插入哈希表的第2个位置,由于第2个位置已经有两个关键字ZHENG和CHAO,因此需要使用开放地址法(线性探测)解决冲突,将YANG插入哈希表的第4个位置。
- 插入关键字JIN,h(JIN) = 3,将JIN插入哈希表的第3个位置。
4. 插入完成后,哈希表中的关键字顺序为:{ZHOU, ZHENG, CHAO, YANG, QIAN, SUN, JIN, LI, WANG, CHANG, ZHAO, WU}。
5. 平均查找长度为:(1+2+3+4+5+6+7+8+9+10+11)/12 = 6.5。
因此,构造的装填因子不小于0.75的哈希表为:
```
0: ZHOU
1:
2: ZHENG -> CHAO -> YANG
3: JIN
4: CHANG
5:
6: LI
7:
8: WANG
9:
10: ZHAO
11: WU
12:
13: SUN
14: QIAN
15:
```
其中,箭头表示冲突解决后插入的位置。