深度剖析哈希

一. 哈希概念

C++11中引进了unordered系列的四个容器，而之所以这几个容器效率如此之高，是因为运用到了哈希的思想。

1.1 哈希概念

顺序结构以及平衡树中，元素关键码与其存储位置没有对应的关系，所以在插入和查找操作时，需要遍历结构，这样造成的时间复杂度太高。

而我们的哈希就是通过某种函数，让元素的关键码与元素的存储位置构建起一一映射关系。这就是哈希的概念。

当向该结构中：

• 插入元素：根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放
• 搜索元素：对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置 取元素比较，若关键码相等，则搜索成功

哈希中使用的函数叫做哈希函数，通过哈希构建的结构称为哈希表或者散列表。

特别注意：以上不论是顺序搜索，还是平衡树搜索或者哈希搜索，得到的key值都不能相同。​​​​​​​

1.2 哈希冲突

什么是哈希冲突呢？其实啊就是不同的关键码通过相同的哈希函数得到相同的映射位置。

这种就叫哈希冲突或者哈希碰撞。发生哈希冲突并具有相同映射位置的不同的关键码就叫同义词。

1.3 哈希函数

引起哈希冲突的原因也可能是：哈希函数设计不合理。

我们的哈希函数需要满足：

• 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值 域必须在0到m-1之间
• 哈希函数计算出来的地址能均匀分布在整个空间中
• 哈希函数应该比较简单

我们有下面常见的哈希函数：

1、直接定址法(常用)

直接定址法字面上来说就是通过关键码直接得到映射位置。最多再加一个倍数变换，也就是取关键字的某个线性函数为散列地址。

直接定址法的优点是简单并且消除哈希冲突，但是需要事先知道数据的分布情况，因为直接定址法适用于数据集中且数据小的情况，如下：

2、除留余数法(常用)

如果我们设散列表允许的地址数为m，取一个不大于m，但最接近或者等于m的质数作为除数。

简单来说，就是将关键码除以散列表的大小得到的余数作为映射的位置。除留余数法的优点是可以处理分散的数据，缺点是会导致哈希冲突，例如对于{1,4,5,614}。

可以看见是会发生哈希冲突的。

3、平方取中法(了解)

假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址； 再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址。平方取中法适用于不知道关键字分布，但是数据又不是很大的时候。

4、折叠法(了解)

折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这 几部分叠加求和，并按散列表表长，取后几位作为散列地址。折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况。

5. 随机数法(了解)

选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中

random为随机数函数。随机数法适用于关键词长度不等的情况。

6. 数学分析法(了解)

设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定 相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只 有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散 列地址。数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的 若干位分布较均匀的情况。

二. 闭散列

闭散列：也叫开放地址法，当发生哈希冲突时，如果哈希表未被填满，说明哈希表中必然还有空位置，那么可以把key存放到冲突位置的下一个空位置中去，为什么说是空位置呢？下面我们会讲解。

2.1 线性探测法

这里我们采用线性探测的方法：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

我们来看看实例，假设我们要将arr映射到Hash表中，而表的大小为10，那么：

那么就应该如下：

注意：当元素本来该在的位置被占用时，需要往后找下一个空位置。比如：4先进入表，就把4的位置占住了，那么当14再进去的时候，由于下标是4的地方已经被占住了，所以向后找到下标为5的位置，插入。而如果此时再来一个28，那么就插入下标为9的地方，而如果再来了一个29，我们可以看到后面的表已经满了，那么就要从头开始查找插入，结果就应该是：

2.2 引进状态

那么好，我们现在已经知道插入一个元素时，先用他的值对表的大小取模，得到位置，如果该位置为空，那么就插入；如果不为空，就向后找下一个空位置。那么大家有没有考虑过我先删掉一个元素再插入呢？

例如我先删除14，再插入54呢？可以看到有两个问题：

1. 删除之后，我们该将删除之后位置的值变成多少呢？好像多少都不合适，因为无论你变成多少，都有可能会有新插入的元素值跟他一样！
2. 我们插入54之后，按理来说我们应该插入到删除的14的位置，因为实际上来说删除了元素之后，那里就没有元素了，可是我们代码又如何去看该位置是不是空呢？因为第一个问题就是删除之后不知道该把值变为多少。

那么其实我们的解决方法就是，为每个位置引进一个state状态(EXIST,DELETE,NULL)。

2.3 闭散列的查找、插入、删除操作

那么我们就可以进行查找、插入、删除操作了：

1. 查找：现根据哈希函数查找到该元素本来该在的位置，然后再考虑发生过哈希冲突的情况，那我们就要依次向后找不为空的位置，直到找到该元素且状态为存在。
2. 插入：对于插入来说，我们要先根据哈希函数来获取插入元素在哈希表中的位置。如果该位置没有元素则插入，如果该位置有元素发生了哈希冲突，则向后依次找下一个空位置。如果负载因子(哈希表中的元素个数/哈希表的大小)超过给定的大小，则需要对哈希表进行扩容。
3. 删除：采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素 会影响其他元素的搜索。先查找到位置，然后将该位置的状态变为DELETE。​​​​​​​

代码实现如下：

2.4 闭散列插入时的扩容

可以看到，我们表的大小是有限的，不可能插入无数个数，所以不可避免的会发生扩容操作。

​​​​​​​

我们可以回忆一下数组的扩容，我们是直接在原来的数组上直接多开辟空间。那么同样的方法在这里行不行得通呢？

答案是否定的，因为我们这里要符合哈希函数的映射，如果我们扩容后映射条件是会改变的，比如表的大小从10扩容到20，那么同样的17，原来应该是在下标为7的地方，扩容后就应该在下标17的地方，所以扩容前后的映射条件是不同的。

那我们是不是要等到表满了才扩容呢，其实并不是，如果满了再扩容就有点局促了，没有一点的缓冲的地方，所以我们要规定，插入的元素达到表的多少就扩容。我们定义一个载荷因子。

我们这里定义载荷因子为0.7。

所以扩容具体操作如下：

2.4 仿函数

我们上面考虑的情况都是插入的值为整数的情况，那么如果插入的是字符串呢？

按道理来讲我们要先将字符串转换为整数，再进行插入。那我们能不能把求映射位置的表达式换成这样呢？

很显然是不能的，这样又只能满足字符串，那么编译器又不知道你要插入什么类型的元素，万一你插入整型，而整型又不能取[]，又会显得鸡肋。

这种问题还得是需要仿函数这位大哥来解决。我们可以为不同的类型定义不同的处理方式：

那么对于字符串这种特殊情况，就有很多人去研究具体该如何定义他的映射函数才是更完美的。那么其中最好的就是BKDR哈希字符串算法，也就是将每一位的字符乘以131或者特定的数字，最后相加。

2.5 整体代码

三. 开散列

开散列法又叫做链地址法，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中(我们这里采用头插的方式)。

2.1 闭散列节点定义

闭散列的各个元素之间不会互相影响，所以就不用为每个节点定义状态了。而且每个节点里面都是链表节点。

2.2 开散列的插入查找删除操作

开散列所用的结构已经与闭散列不相同了，所以对应的操作也应该作出变换。

1. 插入：还是先根据哈希函数算出该插入的位置，用该值创建一个新节点，我们这里采用的是头插的方式插入新节点，因为尾插还要找到尾部，影响了效率。
2. 查找：根据哈希函数算出这个值所在的位置，从头结点开始遍历，一直遍历到某个节点的值等于要查找的值为止。
3. 删除：现根据查找函数找出要删除的节点，如果该节点前面没有节点，则直接删除，然后让哈希表该位置的值为空，如果前面还有值，就先记录前面与后面的节点，删除节点之后，链接这两个节点。

2.3 开散列插入时的扩容

与闭散列同样的道理，开散列的插入操作也涉及到扩容操作。因为当我们插入元素时，每个桶中的节点个数会增加，那么极端情况下，可能某个桶下面会挂炒鸡多的节点，这样会影响查找和删除操作的效率。我们就需要进行扩容操作。

我们该什么时候扩容呢？哈希表最好的情况是每个下面都挂一个节点，所以当插入元素个数等于表的大小的时候就进行扩容，此时载荷因子大小为1：

代码如下：

此处我们无需再去跟开放地址法一样创建一个HashTable对象，然后再根据所有的值各自创建节点插入到扩容后的新表中，因为这样导致新节点的创建，旧节点的销毁。这样是得不偿失的。

我们采用的是直接取出旧表中的节点插入到新表中(注意：不能将整个桶直接插入到新表，因为同样的值对于新表来说映射结果可能改变了)，然后交换旧表与新表即可，这样节约了大量的时间。

2.4 整体代码

四. 素数做除数和哈希表结构问题

我们上面在介绍除留余数法时给出的定义是这样的：设哈希表中允许的地址数为m，取一个不大于m，但最接近或者等于m的素数p作为除数，按照 哈希函数 Hash(key) = key % p (p<=m), 将关键码转换成哈希地址；

这里为什么要选择素数来作为除数呢？因为这样能减少哈希冲突发生的概率。

所以我们C++中就有人专门去研究了哪些素数最合适作为除数。那么STL源码如下：

这里还有一个问题，我们设定的是当载荷因子达到1的时候就进行扩容，这样保证哈希表中的每个位置下面挂着三五个节点，保证了效率。

但是极端情况下，例如经历某些特殊攻击的时候(专门插入位于同一种哈希碰撞情况的素数)，那么机会导致某个链表很长，这里我们就要对链表这个数据机构做出变换，可以把它换成红黑树，红黑树可以保证查找、插入和删除操作的时间复杂度都是 O(log n)，比链表快得多。

所以在极端情况下，可以用红黑树来作为存储结构，而普通情况下就采用链表来存储就可以了。

总结

好了，到这里今天的知识就讲完了，大家有错误一点要在评论指出，我怕我一人搁这瞎bb，没人告诉我错误就寄了。

祝大家越来越好，不用关注我（疯狂暗示）