哈希表的概念

哈希表（Hash Table）是一种基于数组实现的数据结构，通过哈希函数将键映射到数组的索引位置，从而实现高效的数据存储和检索。哈希表的主要特点包括：

• 快速查找：在理想情况下，哈希表的查找、插入和删除操作的时间复杂度为 O(1)。
• 键值对存储：哈希表以键值对的形式存储数据，允许通过键快速访问对应的值。
• 哈希函数：哈希函数用于将键转换为数组的索引，好的哈希函数能够均匀分布键，减少冲突。
• 冲突处理：当多个键映射到同一个索引时，需要采用冲突处理机制，如链地址法或开放地址法。

哈希表的基本参数

1. $T$： 哈希表 键 的个数
2. $b$： 哈希表 桶 的个数
3. $s$： 一个桶中 槽 的个数
4. $n$： 哈希表中 键值对 的个数
5. $\alpha = \dfrac{n}{b \times s}$： 哈希表的 负载因子，表示每个槽平均存储的键值对数量，用于衡量哈希表的拥挤程度。

哈希函数

哈希函数

$$x \rightarrow h(x) \in [0, b-1]$$

将键 $x$ 映射到哈希表的桶索引 $h(x)$。

哈希表的冲突处理

当多个键映射到同一个桶时，称为哈希冲突。常见的冲突处理方法有：

1. 开地址法：在发生冲突时，寻找下一个空闲的槽进行存储。

• 线性探测：依次检查下一个槽，直到找到空闲槽。
• 二次探测：按照二次方的间隔检查槽，减少聚集现象，$h(x) + i^2, i \in 0, 1, -1, 2, -2, \ldots$
• 双重哈希：使用第二个哈希函数计算探测间隔，进一步减少冲突。

2. 链地址法：每个桶存储一个链表，所有映射到同一桶的键值对都存储在该链表中。

例题： 已知哈希表大小为 11，哈希函数 $h(x) = x \mod 11$

1. 使用线性探测插入以下键值对：23, 34, 15, 38, 47, 12, 56
2. 使用二次探测插入以下键值对：23, 34, 15, 38, 47, 12, 56
3. 已知另一个哈希函数 $h_2(x) = 7 - (x \mod 7)$，使用双重哈希法插入以下键值对：23, 34, 15, 38, 47, 12, 56

解答：

1. 线性探测插入结果：

• 插入 23：$h(23) = 1$，存储在索引 1
• 插入 34：$h(34) = 1$，冲突，存储在索引 2
• 插入 15：$h(15) = 4$，存储在索引 4
• 插入 38：$h(38) = 5$，存储在索引 5
• 插入 47：$h(47) = 3$，存储在索引 3
• 插入 12：$h(12) = 1$，冲突，依次检查索引 2, 3, 4, 5，最终存储在索引 6
• 插入 56：$h(56) = 1$，冲突，依次检查索引 2, 3, 4, 5, 6，最终存储在索引 7 最终哈希表状态：

Index: 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
Value: - |23 |34 |47 |15 |38 |12 |56 | - | - | -

2. 二次探测插入结果：

• 插入 23：$h(23) = 1$，存储在索引 1
• 插入 34：$h(34) = 1$，冲突，存储在索引 $1 + 1^2 = 2$
• 插入 15：$h(15) = 4$，存储在索引 4
• 插入 38：$h(38) = 5$，存储在索引 5
• 插入 47：$h(47) = 3$，存储在索引 3
• 插入 12：$h(12) = 1$，冲突，依次检查索引 $1 + 1^2 = 2$, $1 - 1^2 = 0$, 最终存储在索引 0
• 插入 56：$h(56) = 1$，冲突，依次检查索引 $1 + 1^2 = 2$, $1 - 1^2 = 0$, $1 + 2^2 = 5$, $1 - 2^2 = -3 = 8 ( \mod 11)$, 最终存储在索引 8 最终哈希表状态：

Index: 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
Value: 12|23 |34 |47 |15 |38 | - | - |56 | - | -

3. 双重哈希法插入结果：

• 插入 23：$h(23) = 1$，存储在索引 1
• 插入 34：$h(34) = 1$，冲突，计算步长 $h_2(34) = 7 - (34 \mod 7) = 7 - 6 = 1$，存储在索引 $1 + 1 = 2$
• 插入 15：$h(15) = 4$，存储在索引 4
• 插入 38：$h(38) = 5$，存储在索引 5
• 插入 47：$h(47) = 3$，存储在索引 3
• 插入 12：$h(12) = 1$，冲突，计算步长 $h_2(12) = 7 - (12 \mod 7) = 7 - 5 = 2$，存储在索引 $1 + 2 = 3$（冲突），继续 $3 + 2 = 5$（冲突），继续 $5 + 2 = 7$，存储在索引 7
• 插入 56：$h(56) = 1$，冲突，计算步长 $h_2(56) = 7 - (56 \mod 7) = 7 - 0 = 7$，存储在索引 $1 + 7 = 8$ 最终哈希表状态：

Index: 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
Value: - |23 |34 |47 |15 |38 | - |12 |56 | - | -