二、知识总结

✨ 核心思想

哈希表（Hash table），也称为散列表，是一种使用哈希函数组织数据以支持快速插入和搜索的数据结构。哈希表通过将键映射到表中的一个位置来访问记录，这使得每次查找的时间复杂度接近 O(1)，这是哈希表的最大优点。

✨ 算法原理

哈希表的工作原理基于哈希函数和数组的组合。键通过哈希函数转换为数组的一个索引，该索引决定了记录的存储位置。理想情况下，哈希函数会将每个键均匀分布到数组的每个位置，但实际上，不同的键可能会产生相同的索引，这种情况称为"冲突"。

✨ 处理冲突

由于多个键可能映射到同一位置，因此需要一种方法来解决这种冲突。

常见的冲突解决方法包括：

1. 链地址法（Separate Chaining）：
   • 每个数组索引处不单独存储一个元素，而是存储一个数据结构（如链表或二叉搜索树），用于存储所有映射到该索引的元素。
   • 当发生冲突时，元素将被添加到对应索引的数据结构中。
2. 开放寻址法（Open Addressing）：
   • 所有的元素都存储在数组里，当发生冲突时，通过探查序列寻找另一个空闲的位置。
   • 常用的探查技术有线性探查、二次探查和双重散列。

✨ 哈希函数的设计

哈希函数的设计至关重要，它应尽可能将键均匀分布在哈希表中，减少冲突的概率。

好的哈希函数通常具备：

• 快速计算：哈希函数应该容易计算，以保持整体的高性能。
• 均匀分布：哈希函数应尽量减少冲突，将数据均匀分布在哈希表中。

✨ 动态调整大小

为了维持操作的高效性，当哈希表中的元素过多或过少时，可能需要调整哈希表的大小。这通常涉及到创建一个更大或更小的新哈希表，并将所有现有元素重新散列到新表中。

✨ 应用场景

哈希表被广泛用于实现数据库索引、关联数组（字典）、集合数据结构等。在编程语言中，如 Python 的字典（dict）和 JavaScript 的对象（Object），内部都是通过哈希表实现的。

✨ 执行示例

以一个大小为 7 的哈希表为例，哈希函数为 h(key) = key % 7，依次插入元素：10, 22, 31, 4, 15, 28, 17。

使用链地址法：

1插入 10: h(10) = 3  → 位置 3: [10]
2插入 22: h(22) = 1  → 位置 1: [22]
3插入 31: h(31) = 3  → 位置 3: [10, 31]  （冲突！挂在链表后面）
4插入 4:  h(4)  = 4  → 位置 4: [4]
5插入 15: h(15) = 1  → 位置 1: [22, 15]  （冲突！挂在链表后面）
6插入 28: h(28) = 0  → 位置 0: [28]
7插入 17: h(17) = 3  → 位置 3: [10, 31, 17]  （再次冲突！）

最终哈希表状态：

查找元素 31： h(31) = 3，访问位置 3 的链表，比较 10（不匹配）→ 比较 31（匹配），查找成功，比较了 2 次。

使用线性探查法（开放寻址）：

1插入 10: h(10) = 3  → 位置 3 空，放入位置 3
2插入 22: h(22) = 1  → 位置 1 空，放入位置 1
3插入 31: h(31) = 3  → 位置 3 已占，探查位置 4（空），放入位置 4
4插入 4:  h(4)  = 4  → 位置 4 已占，探查位置 5（空），放入位置 5
5插入 15: h(15) = 1  → 位置 1 已占，探查位置 2（空），放入位置 2
6插入 28: h(28) = 0  → 位置 0 空，放入位置 0
7插入 17: h(17) = 3  → 位置 3、4、5 都已占，探查位置 6（空），放入位置 6

✨ 解题步骤详解

例题：统计数组中每个元素出现的次数

给定数组 [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]，统计每个元素的出现次数。

使用哈希表的解题思路：

1. 创建哈希表：用 C++ 的 unordered_map 存储 \<元素, 出现次数\>
2. 遍历数组：对每个元素，在哈希表中查找并更新计数
3. 输出结果：遍历哈希表，输出每个元素及其出现次数

1#include <iostream>
2#include <unordered_map>
3#include <vector>
4using namespace std;
5
6int main() {
7    vector<int> arr = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
8    unordered_map<int, int> count;
9
10    for (int x : arr) {
11        count[x]++;  // 自动初始化为0，然后加1
12    }
13
14    for (auto& p : count) {
15        cout << p.first << " 出现了 " << p.second << " 次" << endl;
16    }
17    return 0;
18}

✨ 常见错误

1. 哈希函数设计不当：如果哈希函数让大量键映射到同一位置，哈希表退化为链表，查找变成 O(n)
2. 忘记处理冲突：直接覆盖相同位置的元素会导致数据丢失
3. 数组越界：使用取模运算时，注意负数取模的结果可能为负数（C++ 中 -7 % 5 = -2），需要加上表大小后再取模
4. 哈希表大小选择不当：哈希表大小最好选择质数，可以减少冲突概率
5. 混淆 map 和 unorderedmap：map 基于红黑树（有序，O(log n)），unorderedmap 基于哈希表（无序，平均 O(1)）