数据结构哈希函数的取构造，装填因子

哈希函数的构造方法有很多种，常见的有以下几种：

1. 直接定址法：直接将关键字作为哈希值，即 H(key) = key。适用于关键字分布比较均匀的情况。

2. 数字分析法：通过对关键字进行分析，找出关键字中的规律或者特征，然后将其作为哈希值。例如，对于电话号码，可以选择后几位作为哈希值。

3. 平方取中法：将关键字平方后取中间的几位作为哈希值。适用于关键字分布不均匀的情况。

4. 除留余数法：H(key) = key mod p，其中 p 为一个不大于哈希表长度的质数。适用于关键字分布比较均匀的情况。

5. 随机数法：随机选择一个哈希函数，将关键字映射到哈希表中。适用于关键字分布不可预测的情况。

装填因子（Load Factor）是指哈希表中已存放数据元素个数与哈希表长度的比值，即 Load Factor = n / m，其中 n 为已存放数据元素个数，m 为哈希表长度。

装填因子的选择会影响到哈希表的性能，一般来说，装填因子越小，冲突的概率越低，但是空间利用率也会降低；装填因子越大，空间利用率越高，但是冲突的概率也会增加。

通常情况下，装填因子的选择在 0.5 到 0.8 之间比较合适，当装填因子超过某个阈值时，可以考虑进行扩容操作，以降低冲突的概率。

相关问题

为以下关键字构造装填因子不小于0.75的哈希表，并给出平均查找长度。{ZHAO, QIAN, SUN, LI, ZHOU, WU, ZHENG, WANG, CHANG, CHAO, YANG, JIN}

为了构造装填因子不小于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: 

其中，箭头表示冲突解决后插入的位置。

为以下关键字构造装填因子不小于0.75的哈希表，并给出平均查找长度。ZHAO,QIAN,SU N,L,ZHOU, WU,ZHENG,WANG,CHANG, CHAO,YANG,JIN}

我们可以使用哈希函数 h(key) = key % 13，其中 % 表示取模运算，将关键字映射到哈希表的位置。这样，我们可以得到以下哈希表：

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

插入关键字时，我们先计算哈希函数的值，然后将关键字插入到对应位置。如果该位置已经有其他关键字，我们采用开放地址法中的线性探测，即向后依次查找空闲位置，直到找到一个空闲位置或者查找了整个哈希表。

具体地，我们可以得到如下哈希表：

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|------|---|-----|---|---|---|---|---|---|----|----|----|
| Z | QIAN | | | | L | | | | | | | |
| | | | | | | | | | | ZHAO| | |
| | | |ZHENG| | |WU | | | | | | |
| | | | | | | | | | | |JIN | |
|ZHOU| | | | | | | | | | | | |
| |YANG | | | | | | | | | | | |
| | | | | | | | | |CHAO| | | |
| | | | | | | | | | | | |WANG|
| | | | | | | |CHANG| | | | | |
| | | | | | | | | | | | | |
| | | | |SU | | | | | | | | |
| | | | | | | | | | | | | |

平均查找长度为：

(1+1+1+2+1+1+2+1+1+1+1+2+1)/13 ≈ 1.31