【数据结构】-----哈希
目录
一、哈希表概念
二、哈希函数
三、哈希冲突
Ⅰ、定义
Ⅱ、解决
①闭散列--开放定址法
线性探测
二次线性探测
②开散列--链地址法（哈希桶）
问题：哈希表何时扩容？
一、哈希表概念
哈希表又称散列表，它是一种数据存储结构，该结构主要是通过某种哈希函数将元素的存储位置与元素的关键码（值）之间建立起一种一一映射的关系。因此在查找时能够通过该哈希函数直接找到对应的元素，效率上明显提高。
例如：存在数据集合{1，3，6，2，4}；
哈希函数设置为：hash(key)=key % capacity。capacity为存储元素底层空间总大小。
假设这里的capacity大小为10，则各元素之间的存储位置如下：
用该方法进行搜索不必进行多次关键码的比较，因此速度会很快！
在理想情况下：哈希表的查找可以达到O(1)。而顺序查找和平衡树中，因为值和位置之间没有直接的关系，查找需要进行多次比较，顺序查找O(N),平衡树查找为树的高度，即O(log_2N)。搜索的效率取决于元素的比较次数，相比于哈希，挺慢！
二、哈希函数
哈希函数设计的原则：
- 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间
- 哈希函数计算出来的地址能均匀分布在整个空间中
- 哈希函数应该比较简单
常见哈希函数：
- 直接定址法(常用)
取关键字的某个线性函数为散列地址：Hash（Key）=key 或者 Hash（Key）= A*Key + B
优点：简单、均匀
缺点：需要事先知道关键字的分布情况
使用场景：适合查找比较小且连续的情况
- 除留取余法（常用）
设散列表中允许的地址数为m（空间总容量），取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址。
优点：使用十分广泛，不受限制。
缺点：存在哈希冲突，哈希冲突越多，效率越低。
- 平方取中
假设关键字为123，平方后15129，抽取中间3位512作为哈希地址。
再如关键字4321，平方后18671041，抽取中间3位671或者710作为哈希地址。
该方法适用于：不知道关键字的分布情况，而位数又不是很大的情况。
- 折叠法
折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这
几部分叠加求和，并按散列表表长，取后几位作为散列地址。适用于：不知道关键字的分布情况，而位数多的情况。
如：123456789 ->分割：123|456|789 ->相加：123+456+789=1368
假设表长为10，那就取后两位68作为哈希地址。
- 随机数法
选择一个随机函数，取关键字的随机函数值为它的哈希地址，即Hash(key) = random(key),其中random为随机数函数。
通常应用于关键字长度不等时采用此法
用得多还是前面两个，其他简单了解即可！
三、哈希冲突
Ⅰ、定义
所谓哈希冲突，就是不同的关键码通过同一个哈希函数计算得到相同的存储地址。即相同位置上存在不同的值的现象。
引起哈希冲突的原因可能就是：哈希函数设计不合理引起的！
例如：在上述例子再插入11，计算后得到的地址为下标1，和原来的1发生的冲突，那么该怎么去解决呢？
Ⅱ、解决
常见两种方法：闭散列 和 开散列
①闭散列--开放定址法
此法又称开放定址法，当发生哈希冲突时，如果哈希表未装满，说明有空位置，那么可以把key存放到冲突位置的下一个空位置去，这里寻找下一个空位置的方法又有两种
-
线性探测
这种方式是从发生冲突的位置开始，依次向后探测，直到发现下一个空位置为止。
H=(Hash0+i)%m ,i=1,2,3……
Hash0：通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置，即Hash(key)
m：散列表长度，这里取余，是为防止越界从而达到循环的效果。。
例如：上述例子插入11，通过哈希函数取余操作后发现和原来的1的位置冲突了，那就要继续向后探测，依次+1，+2，……，直到发现空位置，就放入该位置！
优点：实现简单
缺点：一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”，即：不同
关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降
低。所以需要扩容操作！
-
二次线性探测
这种探测方式能够避免线性探测的数据堆积问题的，它和线性探测的区别就是：依次跨越 个单位，i从1开始。数据之间会相对稀疏。
H=(Hash0+i^2)%m ,i=1,2,3……
上述例子的过程如下：
插入11，发现冲突，第一次探测先加1^2，第二次探测加2^2,发现了空位置直接放入即可
②开散列--链地址法（哈希桶）
开散列法又称为链地址法，当发生哈希冲突时，将相同地址的值归于同一个子集合，每一个子集合称为一个桶，这个桶里面的元素采用链表的方式链接起来。即每一个桶存放的都是冲突的数据！
还是以上述例子举例。插入元素11，发生冲突，采用开散列的方式，无需向后寻找空位置，直接采用头插法。。
问题：哈希表何时扩容？
这里就需要引入负载因子的说法：负载因子=有效数据个数 / 散列表长度。
从上述公式可以看出：当数据个数越多，负载因子越高，冲突率越高，效率就越低；当长度越长，负载因子越低，冲突率越低，效率就越高，但此时空间利用率就越低。
哈希表的平均查找长度是负载因子的函数，即每个元素比较次数总和 / 元素总个数
- 对于闭散列来说，一般严格将负载因子控制在0.7-0.8之间。超过0.8查表时，cpu缓存不命中按照指数曲线上升。因此采用闭散列的方式，保险起见超过0.7就需要扩容操作！
- 对于开散列来说，最好的情况是每个哈希桶中刚好挂一个节点，再继续插入元素时，每一次都会发生哈希冲突，因此，在元素个数刚好等于桶的个数（散列表长度）时，即负载因子等于1时，就可以给哈希表增容。
具体如何扩容，请看下一回实现部分，因为看到这里，您也累了，休息一下咯！
好了，老铁今天的分享内容就到这里，觉得对你有帮助，欢迎点赞+关注！