哈希---闭散列和开散列_闭散列法

闭散列法和开散列法解决哈希冲突

闭散列：
也叫开放定址法，当发生哈希冲突时，寻找合适的空位置
找空位置的方法：

1. 线性探测法
   从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止

线性探测优点：实现简单
线性探测缺点：哈希冲突容易堆积，使得寻找某关键码需要多次比较，搜索效率低

2. 二次探测法
   假设空位置为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++目前还没有。

开散列最好的情况是：每个哈希桶中刚好挂一个节点，在元素个数刚好等于桶的个数时，可以给哈希表增容

开散列增容可以新建大容量的哈希表，如何把旧表的各个节点移动即可，不需要创建节点。

闭散列必须保持大量的空闲空间以确保搜索效率，开散列则是需要额外存指向下一个元素的指针。总体上来说，如果数据集比较小，选择闭散列占用内存可能更低，有时候所有的键值对提前知道，之后不会发生变化，可以设计一个不产生冲突的完美哈希函数，此时闭散列的性能也是高于开散列。但如果数据量比较庞大，闭散列的表项其实比开散列的指针占用的空间更多。还有就是元素分布不均匀的时候更倾向于选择开散列来保证效率。