哈希表（Hash Table）是一种通过**哈希函数**将键（key）映射到数组索引，从而实现平均 $O(1)$ 时间复杂度的**插入、查找、删除**的数据结构。 下面以最常用的语言 C++ 和 Python 为例，带你从零入门： --- ### ✅ 一、核心思想 给定一个键 `key`，哈希函数 $h(key)$ 计算出一个整数索引（如 `h("apple") → 3`），把对应值存到数组位置 `3` 上。为处理冲突（不同 key 映射到同一索引），主流语言内部采用**开放寻址**或**链地址法**（如每个桶是链表），你无需手动实现——直接用封装好的容器即可。 --- ### ✅ 二、常用语言写法 #### 🔹 C++：`std::unordered_map`（无序映射） ```cpp #include <unordered_map> #include <string> #include <iostream> using namespace std; int main() { unordered_map<string, int> mp; // key=string, value=int mp["Alice"] = 25; // 插入/修改 mp["Bob"] = 30; if (mp.find("Alice") != mp.end()) { // 查找存在性 cout << mp["Alice"] << endl; // 输出 25 } mp.erase("Bob"); // 删除 cout << mp.size(); // 当前元素个数 } ``` #### 🔹 Python：`dict`（字典，底层即哈希表） ```python # 创建 mp = {} # 插入/修改 mp["Alice"] = 25 mp["Bob"] = 30 # 查找（推荐用 get 避免 KeyError） print(mp.get("Alice", -1)) # 存在返回 25，不存在返回 -1 # 判断是否存在 if "Alice" in mp: print("Found!") # 删除 del mp["Bob"] # 或 mp.pop("Bob", None) print(len(mp)) # 元素个数 ``` --- ### ✅ 三、典型应用场景（初学者必练） | 场景 | 示例问题 | 关键操作 | |------|-----------|----------| | **去重** | 统计数组中出现次数 ≥2 的数 | `unordered_set<int>` 或 `dict` 记频次 | | **配对查找** | 两数之和：找 `nums[i] + nums[j] == target` | 遍历中用哈希表存 `target - nums[i]`，查是否已见 | | **字符串计数** | 统计字符频次（如“hello”→ h:1, e:1, l:2, o:1） | `map<char, int>` 或 `Counter` | --- ### ✅ 四、注意事项（避坑提醒） - ❌ 哈希表**不保证顺序**（C++ `unordered_map` / Python `dict` 在 Python 3.7+ 保持插入序，但这是实现细节，**逻辑上不应依赖**）；若需有序，请用 `map`（C++红黑树）或 `sorted(dict.items())`（Python）。 - ⚠️ 键必须是**可哈希类型**：C++ 要求 `key` 有合法 `hash` 和 `==`；Python 中 `list`、`dict` 不可作 key（因可变），但 `tuple`（元素都不可变）可以。 - 🧮 最坏情况（大量哈希冲突）时间退化为 $O(n)$，但实际极少发生；现代实现自动扩容（负载因子 > 0.75 时 rehash），你无需干预。 --- ✅ **下一步建议练习题（难度递进）：** 1. [LeetCode 1. 两数之和](https://leetcode.cn/problems/two-sum/) —— 理解“边遍历边查”的思维 2. [LeetCode 387. 字符串中的第一个唯一字符](https://leetcode.cn/problems/first-unique-character-in-a-string/) —— 结合频次统计与顺序扫描 3. [LeetCode 217. 存在重复元素](https://leetcode.cn/problems/contains-duplicate/) —— 快速去重判断 需要我为你逐题讲解解法或提供带注释的代码，随时告诉我！ 🌟