哈希表详解及模拟实现（unordered_map）

目录

认识哈希表：

哈希冲突：

除留余数法--(常用)

平方取中法--(了解)

折叠法--(了解)

随机数法--(了解)

泛型编程：

闭散列：

线性探测：

二次探测：

扩容：

查找：

插入：

删除：

开散列：

扩容：

查找：

插入：

删除：

迭代器：

全部代码:

认识哈希表：

哈希表是一种数据结构，也称散列表，主要用于查找，且使用很频繁，可见它的效率相比其他用于查找的数据结构，肯定有优势。之前学习的顺序表和平衡二叉搜索树，查找的时间复杂度为O（n）和O（logn），它们两都需要通过key值一一比较不断缩小查找范围，进而查找到所需数据。而哈希表的优势在于无需比较，只需通过某种函数（哈希函数）计算关键码，通过映射关系可直接找到数据，近似O（1）的时间复杂度。

当向该结构中：

插入元素

根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放

搜索元素

对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置 取元素比较，若关键码相等，则搜索成功

我们将它们放入哈希表key值如何取呢？一般数据是size_t或者能强转成size_t类型的key值直接取该数据，对于无法强转的例如string，则通过哈希函数转换，key值也不是直接当作下标存入哈希表内，不然如果一个数据过大，就要开很大的数组， 一般我们需要将 数据%数组大小来得到对应的下标，这种转换也是哈希函数， 举个例子：数据集合{1，7，6，4，5，9}；

哈希冲突：

还是上面的例子，这时我们有一个数据75要进入哈希表，通过哈希函数计算key值，75 % 10 = 5，但是发现下标为5的位置已经有数据，这就出现了不同的数据对应的相同的下标，这就是所谓的哈希冲突，又称哈希碰撞。

注意哈希冲突是不能完全解决的，只能缓解，鸽巢定理可证，所有的字符串，肯定比size_t的最大值要大，因为不限长度字符串几乎是无限的，所以鸽子比巢多，肯定会有巢有两只以上的鸽子。

缓解哈希冲突主要从两个方面：

1.，第一个方面就是对哈希函数入手，上面这个例子的哈希函数，是用key对数组大小取余，这是直接定址法，这种哈希函数出现哈希冲突的概率还是不小的，先来看看哈希函数的设计原则：

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

再来看看几种常见的哈希函数：

除留余数法--(常用)

假设哈希表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数， 按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址

平方取中法--(了解)

假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址； 再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址 平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况

折叠法--(了解)

折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这 几部分叠加求和，并按哈希表表长，取后几位作为散列地址。

随机数法--(了解)

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

2.第二个方面就是对哈希表的存储结构入手，想必大家见过最多的哈希表结构就是顺序表+链表，其实哈希表也可以单纯用顺序表实现，两种不同的底层结构在于它们如何应对哈希冲突，C++的STL库中使用的是顺序表+链表的方式，没错这种方式的效率是更优的，但是单纯用顺序表的结构也是值得学习的，接下来的内容我会分别介绍并模拟实现这两种哈希表的底层结构。

泛型编程：

在模拟实现中，我的my_unordered_set和my_unordered_map封装了一个哈希表HashTable,但set里面存的是一个数据K，而set里面存的是pair<K,T>,HashTable里面只接受一个data,这就导致了如果是set，data就是K类型，如果是map，data就是pair<K,V>,但我们只有一个哈希表，该怎么解决这种矛盾呢？

仿函数：我们可以分别在set和map里创建一个类，在类里重载运算符（），然后在set中的（）重载中直接返回K，在map中的（）重载中返回pair中的K，也就是pair中的first，然后将这个类传给HashTable，在HashTable中使用data前就调用这个类的括号来取里面的数据：

set：

map：

在HashTable中的使用：（哈希地址的计算中就用到了）

HashFunc和上面讲的一样，主要作用是如果key为其他不是size_t的类型将它们强转成size_t和若为string则通过哈希函数转化成size_t，这种方法就是泛型编程的一种。

闭散列：

闭散列，又称开放定址法，也就是上面提到的单纯使用顺序表的方法来实现哈希表，它应对哈希冲突的方法是如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去，那么如何找到“下一个”空位置呢？

线性探测：

回到最开始的例子，我们需要插入75，通过哈希函数计算下标为5，但下标为5的位置已经被占用。

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

所以最后我们能找到8下标位置为空位置，然后进行插入数据。 注意往后探测过程中不能超过数组长度，所以我们每向后走一次就需要%数组长度，以保证当超过数组长度时，下标能回到数组开头。

如何判断这个位置是否为空，只需将每个位置里面存入一个状态值（枚举类型），总共有三个状态：EMPTY，EXIST，DELETE，分别表示空，存在数据，之前有数据但被删除

这部分代码只需理解线性探测思路就行，其他不理解的地方，需结合全部代码。

二次探测：

虽然线性探测能解决哈希冲突，但可以发现这样冲突的数据大部分都聚在了一起，不离散,如图：

为了避免这种情况，线性探测时hashi每次向后走1步，我们采用二次探测，也就是每次向后走i的平方步，每次i++，也就是依次走1，4，9，16，25......步，实现很简单，这里不演示。

扩容：

闭散列的扩容不是满了才扩容，我们先引入一个概念：负载因子，负载因子 = 存在的元素/数组的容量，简单来说负载因子就是占用率，当负载因子>=0.7的时候我们才进行扩容。

扩容思路：

我们可以直接开一个新的hash表，将新表的大小设为旧表的2倍，再将旧表的元素一个个插入到新表，最后用swap函数交换新旧表。 这样写的好处：不必销毁新表，因为新表是局部对象，函数结束后自动销毁了。

查找：

通过key查找某个节点：

先通过key用哈希函数算出对应哈希地址，再从哈希地址开始往后线性探测，找到后返回节点：

插入：

分析一下插入，当插入一个数时该如何做呢？

1.先用查找函数判断能否找到，若找到了，代表原哈希表里有，直接返回false。 2.用负载因子判断是否需要扩容，需要就进行扩容。 3.通过key和哈希函数，算出哈希地址。 4.哈希地址上有值就往后线性探测。

删除：

因为之前，我们在每个节点上都设置了三种状态：EMPTY，EXIST，DELETE，所以现在删除一个数就非常简单了：

只需先通过哈希函数和线性探测找到该节点，再将该节点的状态改为DELETE即可。

开散列：

开散列也就是C++STL库哈希表实现方法，说明它相比闭散列还是有一定的优越性的，开散列应对哈希冲突的方法就是在冲突数据下面用链表进行连接。

扩容：

开散列的扩容条件就是_n == 数组大小的时候：

相比闭散列的扩容方法，开散列只要扩容条件不同，其他差不多，只有旧表中每个桶的数据要依次头插到新表对应的哈希地址。

查找：

如果对应的哈希地址里面有数据，就沿着该地址的链表遍历，找到即可。

插入：

1.先用查找函数判断能否找到，若找到了，代表原哈希表里有，直接返回false。 2.判断是否需要扩容，需要就进行扩容。 3.通过key和哈希函数，算出哈希地址。 4.在该哈希地址的链表处进行头插。

删除：

1.先通过查找函数找到key对应的哈希地址 2.遍历该哈希地址的链表。 3.找到后连接该节点的上一个和下一个节点。 4.注意如果是头删要特殊处理，因为上一个节点为空。

迭代器：

迭代器功能都比较简单，这里我只讲++的思路，其他功能可以到文章最后看全部代码。

++：

1.到一个哈希地址时要先判断存不存在冲突数据，也就是链表。 2.若有冲突数据，直接走向链表的next即可。 3.链表走到尾部，就需要从这个链表的哈希地址开始往后线性探测，直到找到下一个有有效数据的哈希地址或者哈希表走完。

全部代码:

my_ordered_set.h

my_unordered_map.h

HashTable.h