哈希表

1. 一句话总结

哈希表用哈希函数把 key 映射到桶，以空间换时间，平均实现 O(1) 查找、插入和删除。

2. 通俗解释

哈希表像快递柜：通过手机号算柜号，理想情况下直接开柜；多人算到同一柜号时，就要用拉链法或开放寻址解决冲突。

3. 核心概念

• 哈希函数：把 key 转为桶位置。
• 哈希冲突：不同 key 映射到同一位置。
• 拉链法：桶后挂链表或树。
• 开放寻址：冲突后寻找其他空位。
• 负载因子：元素数量和桶数量的比例。
• 扩容：桶不足时重新分配并 rehash。

4. 底层原理

• 哈希表快的前提是哈希函数分布均匀、负载因子合理。
• 负载因子过高会增加冲突，查找可能变慢。
• 扩容要重新计算位置，单次成本高但可摊还。
• 哈希表本身不按 key 大小有序。
• 可变对象不适合做 key，因为哈希值应稳定。

5. 面试标准回答

哈希表的核心是通过哈希函数把 key 映射到数组下标，从线性扫描变成直接定位。它的平均查找、插入、删除复杂度接近 O(1)，但这个结论依赖哈希函数分布均匀和负载因子合理。发生冲突时，常见处理方式有拉链法和开放寻址法；元素增多后，哈希表会扩容并重新哈希。面试中不能只说哈希表 O(1)，还要说明冲突、扩容、内存开销和最坏退化。

6. 高频追问

追问 1：哈希表面试第一句话怎么答？

先给结论：哈希函数：把 key 转为桶位置。 再补充它解决的问题和使用场景，避免一上来背长定义。

追问 2：它为什么需要底层机制支撑？

哈希表快的前提是哈希函数分布均匀、负载因子合理。 面试官追问时要把“现象”落到“机制”和“代价”。

追问 3：常见误区是什么？

不要把平均情况说成绝对结论，也不要忽略边界条件、退化情况和工程成本。

追问 4：如果继续追问怎么展开？

可以沿着“定义 → 原理 → 对比 → 场景 → 缺点 → 优化”展开，重点说清：负载因子过高会增加冲突，查找可能变慢。

追问 5：实际开发中怎么体现？

Redis dict 用于键空间。 这类联系能把基础知识从“背概念”变成“解释工程选择”。

追问 6：回答时怎么收尾？

最后用一句话总结适用条件和代价，说明什么时候该用、什么时候不该用。

7. 易混淆点

8. 实际开发联系

• Redis dict 用于键空间。
• Python dict/set 是刷题高频工具。
• Java HashMap 常追问数组、链表、红黑树和扩容。

9. 背诵速记

哈希表空间换时间：哈希函数定位桶，冲突用拉链或开放寻址，负载因子高就扩容。平均 O(1)，冲突严重会退化。回答要补冲突、扩容、负载因子和无序特性。