哈希表
# 引入
哈希表（hash table），又称散列表，它通过建立键key与值value之间的映射，实现高效的元素查询。
向该结构当中插入和搜索元素的过程如下：
- 插入元素： 根据待插入元素的关键码，用此函数计算出该元素的存储位置，并将元素存放到此位置。
- 搜索元素： 对元素的关键码进行同样的计算，把求得的函数值当作元素的存储位置，在结构中按此位置取元素进行比较，若关键码相等，则搜索成功。
此方式对应的就是哈希方法，使用哈希函数来建立映射。
# 哈希函数
# 直接定址法
取关键字的某个线性函数为哈希地址：Hash(Key) = A ∗ Key + B
优点：每个值都有一个唯一位置，效率很高，每个都是一次就能找到。
- 缺点：使用场景比较局限，通常要求数据是整数，范围比较集中。
- 使用场景：适用于整数，且数据范围比较集中的情况。
# 除留余数法
设散列表中允许的地址数为m，取等于m的质数p作为除数，按照哈希函数：Hash(Key) = Key % p (p <= m)
- 优点：使用场景广泛，不受限制。
- 缺点：存在哈希冲突，需要解决哈希冲突，哈希冲突越多，效率下降越厉害。
# 哈希冲突
从本质上看，哈希函数的作用是将所有 key 构成的输入空间映射到数组所有索引构成的输出空间，而输入空间往往远大于输出空间。
因此，理论上一定存在“多个输入对应相同输出”的情况。
# 开放定址法
当发生哈希冲突时，如果哈希表未被装满，说明在哈希表种必然还有空位置，那么可以把产生冲突的元素存放到冲突位置的“下一个”空位置中去。
# 线性探测
下一个位置的计算公式：
Hi=( H0 + i ) % m ( i = 1,2,3 ...)
# 平方探索
下一个位置的计算公式：
Hi=( H0 + i2 ) % m ( i = 1,2,3 ...)
开放定址法就是我的位置被占用，我就去占用别人的位置，并且快接近满的时候就增容。
负载因子 = 表中的数据个数 / 表的大小
一般情况，闭散列的哈希表中，负载因子到0.7就可以开始增容,负载因子越小，冲突概率越低，效率越高。相反，负载因子越大，冲突概率越高，效率越低。 但是负载因子也不敢控制得太小，会导致大量的空间浪费。其实控制负载因子是一种以空间换时间的思路。
# 链地址法
在原始哈希表中，每个桶仅能存储一个键值对。链式地址（separate chaining）将单个元素转换为链表，将键值对作为链表节点，将所有发生冲突的键值对都存储在同一链表中。
值得注意的是，所有元素全部产生冲突，最终都放到了同一个哈希桶中，查询效率很差O(n)。此时可以将链表转换为AVL树或红黑树，从而将查询操作的时间复杂度优化至O(logn)。
