面试中需要熟知的哈希表知识

哈希表介绍

哈希表(又称为哈希映射)是一种可以将键映射到值的数据结构。哈希表使用哈希函数计算出一个哈希码，该哈希码指向一个槽位，从中可以找到所需的值。

使用哈希表是最常用的空间换时间的方式。我们可以遍历数组一次，并将所有元素散列到一个哈希表中，而不是每次线性搜索数组以确定元素是否存在。一次数组的搜索需要花费O(n)时间复杂度，而使用哈希表的平均时间复杂度为0(1)。

在哈希冲突的情况下，可以使用许多方法来冲突。在面试中，你有可能被问到冲突解决的具体方法，常见的方法如下：

• 链地址法，每个哈希码对应一个链表，链表中存储所有的冲突项。

• 开放寻址法, 所有数据都存储在哈希表的槽中。如果存在哈希冲突，从冲突的槽开始，按照某种探测顺序（线性探测、平方探测等），直到找到一个未被占用的槽。

不同语言对应的实现

语言	实现接口
c++	std::unordered_map
java	java.util.HashMap
python	dict
javascript	Object 或 Map

不同操作的时间复杂度

操作	平均时间复杂度
查找	O(1)
插入	O(1)
删除	O(1)

在面试中涉及到的一般都是平均时间复杂度。