哈希函数
哈希函数（Hash function）又称散列算法、散列函数，是一种从任何一种数据中创建数字指纹的方法。
特征
一个好的哈希函数应该满足以下几种特性：
- 快速：计算速度足够快
- 确定性：对于相同的输入，总是产生相同的输出
- 离散性：对于有规律的数据输入，应该输出无规律的结果
- 不可逆：无法从哈希值逆向推算出原数据
- 难以碰撞：难以找到两个不同的数据计算后输出结果相同（概率很小，小到几乎不可能）
哈希表
哈希表（Hash table）又称散列表，是根据键（Key）而直接访问在记忆体储存位置中值（Value）的数据结构。
创建一个数组，使用哈希函数对所有数据进行压缩生成与之对应的哈希值，再将生成的哈希值与数组长度取模确认数据保存的位置。
哈希碰撞
由于将无限的数据映射到有限的集合中，难免出现多个数据的哈希值相同的情况，这种情况叫做哈希碰撞。
不同的数据出现相同的哈希值，取模的结果也必定是相同的，经典哈希表使用链表将多个数据放在一起
表扩容
随着数据无限插入，链表的长度也会随之增长，链表越长查询效率就会越低。
通常会给哈希表设置一个阈值，当表中元素数量达到阈值时触发扩容机制，将表的大小扩容到原先的 $2$ 倍。
- 创建一个新的数组，长度是原来的两倍
- 便利原先哈希表中所有的元素，重新计算哈希值取模放入新的数组中
- 使用新的数组替换原先的数组，完成哈希表的扩容
时间复杂度
假设阈值为每个链表长度不超过 $2$，输入 $N$ 个数据所需要的扩容次数为 $O(logN)$ 级别。
由于每次扩容都需要将表中所有的元素都遍历一遍，复杂度为 $O(N)$ 级别。
所以整个哈希表扩容的复杂度为 $O(NlogN)$ 级别。
假设链表的长度为 $k$，则理论上查询时的复杂度为 $O(k)$。
如果这个 $k$ 非常小，小到几乎可以忽略不记时，查询的复杂度就能近似的认为是 $O(1)$ 级别
