哈希表基础理论

哈希表是什么

通过建立键 key 与值 value 之间的映射，实现高效的元素查询。就像每一个人的身份证对应一个人一样。

	数组	链表	哈希表
查找元素	$O(1)$	$O(n)$	$O(1)$
添加元素	$O(n)$	$O(1)$	$O(1)$
删除元素	$O(n)$	$O(1)$	$O(1)$

哈希函数

通过某种算法将 value 映射到 key上。

比如

当我们使用数组实现哈希表时，会将所有的key能映射到数组上对应的索引，数组元素则是对应的value

index = hash(key) % cap

图片来自：hello-algo

哈希冲突

理论上一定存在“多个输入对应相同输出”的情况，将这种情况视为“哈希冲突”。

拉链法

冲突的位置存储在链表中。

线性探测法

在冲突的地方继续往前查询，直到查询到不冲突，就放入对应的索引中。