Day4 - Hash Table Pre-Knowledge

Day4 - 哈希表前置知识

1. 哈希表介绍

1.1. 哈希映射

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

1.2. 哈希表原理

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

1.3. 哈希冲突及解决

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

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

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

2. 哈希表实现

语言	实现接口（API）
C++	std::unordered_map
Java	java.util.HashMap
Python	dict
JavaScript	Object 或 Map

3. 时间复杂度

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

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