闭散列法和开散列法解决哈希冲突
闭散列：
也叫开放定址法，当发生哈希冲突时，寻找合适的空位置
找空位置的方法：
- 线性探测法
从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止
线性探测优点：实现简单
线性探测缺点：哈希冲突容易堆积，使得寻找某关键码需要多次比较，搜索效率低
- 二次探测法
假设空位置为H：
H = (H0 +i ^2)% m
或者：H = ( H0- i^2)% m
其中：i = 1,2,3…， H0是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置，m是表的大小
有的哈希结构只采用H = (H0 +i ^2)% m，有的哈希结构H = (H0 +i ^2)% m和H = ( H0- i^2)% m交替使用
超出了表长后可以按循环队列的思想回到表头（表尾）进行再循环
二次探测缓解了冲突堆积的问题，但是闭散列都有的缺点就是空间利用率低
闭散列需要额外存储哈希表每个位置的状态，如果不这样做，发生哈希冲突的元素删除掉，会影响其他元素的查找，例如：
如果删除4，查找44时认为44不存在
状态有三种：空，满，已删除
如果查找时状态为已删除，不能认为元素不存在
插入时状态不为满就插入
在闭散列中查找某元素，若找到空认为不存在，所以闭散列也不允许哈希表为满
解决方法就是通过扩容控制载荷因子：
闭散列扩容可以新建需要的容量的哈希表，重新插入元素。
开散列：
开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码
归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。
随着元素的不断插入，每个桶中元素的个数不断增多，极端情况下，可能会导致一个桶中链表节点非常多，会影响的哈希表的性能，因此有时需要对哈希表进行增容
如果某个下标下的单链表过长，为提高搜索效率可以把该单链表转换成红黑树，java是这样做的，C++目前还没有。
开散列最好的情况是：每个哈希桶中刚好挂一个节点，在元素个数刚好等于桶的个数时，可以给哈希表增容
开散列增容可以新建大容量的哈希表，如何把旧表的各个节点移动即可，不需要创建节点。
由于闭散列必须保持大量的空闲空间以确保搜索效率，而表项所占空间又比指针大，所以使用开散列反而比闭散列节省存储空间。
如果所有的键值对提前知道，之后不会发生变化，可以设计一个不产生冲突的完美哈希函数，此时闭散列的性能就高于开散列。