哈希表（通常称为哈希映射）是一种实现关联数组抽象数据类型的数据结构，它可以将键映射到值。哈希表通过对元素使用哈希函数计算索引（也称为哈希码），并将其存储在一个桶或插槽的数组中，从中可以找到所需的值。在查找时，对键进行哈希，然后查看哈希表中是否存在相应的值，平均情况下这是O(1)的时间。
哈希是空间-时间权衡的最常见例子。我们不需要像线性搜索数组中的每个元素来确定元素是否存在那样每次都遍历数组，这需要O(n)的时间。相反，我们可以遍历数组一次，并将所有元素哈希到哈希表中。确定元素是否存在只需对元素进行哈希，看看它是否存在于哈希表中，平均情况下这是O(1)的时间。
在哈希冲突的情况下，可以使用多种冲突解决技术。在面试中不太可能被问及冲突解决技术的细节：
- 分离链表 - 每个值使用一个链表，因此它存储了所有冲突的项目。
- 开放寻址 - 所有条目记录都存储在桶数组本身中。当需要插入新条目时，会检查桶，从哈希到的插槽开始，并以某种探测序列进行，直到找到一个未占用的插槽。
学习资源
实现
| 语言 | API |
|---|---|
| C++ | std::unordered_map |
| Java | java.util.Map. 使用 java.util.HashMap |
| Python | dict |
| JavaScript | Object 或 Map |
时间复杂度
| 操作 | 大O表示 | 注意事项 |
|---|---|---|
| 访问 | N/A | 由于哈希码未知，访问不可能 |
| 搜索 | O(1)* | |
| 插入 | O(1)* | |
| 删除 | O(1)* |
* 这是平均情况，但在面试中我们只关心哈希表的平均情况。
样本问题
- 描述一个最少使用缓存实现，并给出其大O表示法。
- 一个涉及API与哈希映射集成的问题，其中哈希映射的桶由链表组成。
基本问题
如果你正在为这个主题学习，这些是你应该练习的基本问题。
推荐练习问题
在你已经为这个主题学习和练习了基本问题之后，推荐你练习这些问题。
推荐课程
import AlgorithmCourses from '../_courses/AlgorithmCourses.md'