用于编码面试的散列表清单
原文：https://www.techinterviewhandbook.org/algorithms/hash-table/
简介
哈希表(通常称为哈希映射)是一种实现关联数组抽象数据类型的数据结构，这种结构可以将键映射到值。哈希表使用元素上的哈希函数来计算桶或槽数组中的索引，也称为哈希代码，从中可以找到所需的值。在查找过程中，对键进行哈希运算，得到的哈希表示相应值的存储位置。
哈希是时空权衡最常见的例子。我们可以遍历数组一次，将所有元素散列到一个散列表中，而不是每次都线性搜索数组来确定元素是否存在，这需要 O(n)时间。确定元素是否存在是一个简单的问题，即散列元素并查看它是否存在于哈希表中，这平均为 O(1)。
在哈希冲突的情况下，有许多冲突解决技术可以使用。在面试中，你不太可能被问到冲突解决技术的细节:
- 独立链接 -每个值使用一个链表，这样它就存储了所有冲突的条目。
- 开放寻址 -所有条目记录都存储在桶数组本身中。当需要插入一个新条目时，将检查存储桶，从散列到的槽开始，按某种探测序列进行，直到找到一个未被占用的槽。
学习资源
实现
| 语言 | 应用程序接口 |
|---|---|
| C++ | T2std::unordered_map |
| Java 语言(一种计算机语言，尤用于创建网站) | java.util.Map 。使用 java.util.HashMap 或 java.util.TreeMap (首选) |
| 计算机编程语言 | T2dict |
| Java Script 语言 | Object 或 Map |
时间复杂度
| 操作 | 大 O | 注意 |
|---|---|---|
| 接近 | 不适用的 | 由于哈希码未知，无法访问 |
| 搜索 | o(1)* | |
| 插入 | o(1)* | |
| 去除 | o(1)* |
** 这是平均情况，但是在采访中我们只关心哈希表的平均情况。*
样题
- 描述一个最少使用的缓存的实现，以及它的 big-O 符号。
- 一个涉及 API 与 hash map 集成的问题，其中 hash map 的桶由链表组成。
基本问题
如果你在学习这个话题，这些是需要练习的基本问题。
推荐练习题
这些是在你为题目学习并练习了基本问题后推荐练习的问题。
推荐课程
AlgoMonsterT3】
AlgoMonster 旨在帮助你在最短的时间内通过技术面试。由谷歌工程师开发的 AlgoMonster 使用数据驱动的方法来教你最有用的关键问题模式，并有内容帮助你快速修改基本的数据结构和算法。最重要的是，AlgoMonster 不是基于订阅的——支付一次性费用，就可以获得终身访问。 今天加入七折优惠→
寻找编码面试:编码问题的模式
设计大师的这门课程扩展了推荐练习题中的问题，但从问题模式的角度来进行练习，这是一种我也同意的学习方法，我个人也使用这种方法来更好地编写面试代码。本课程允许你用 Java、Python、C++、JavaScript 来练习选定的问题，并提供这些语言的示例解决方案以及一步一步的可视化。学习和理解模式，而不是背答案！ 现在获得终身使用权→
掌握编码面试:数据结构+算法
这本 Udemy 畅销书是评分最高的面试准备课程之一(4.6 星，21.5k 评分，135k 学生)，包含了价值 19 个小时的内容。像技术面试手册一样，它超越了编码面试，涵盖了简历，非技术面试，谈判。是一个全包！请注意，JavaScript 用于编码演示。 结账→
