【C++】一文搞定哈希表（详细解析，小白一看就懂！！）

本文主要是介绍【C++】一文搞定哈希表（详细解析，小白一看就懂！！），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、前言

二、什么是哈希表？

💧哈希的由来 💧

💧哈希思想💧

💧哈希表的概述 💧

三、哈希冲突

四、哈希函数

🍓哈希函数设计原则

🥝常见的哈希函数

五、哈希冲突解决

🍇 闭散列（开放定址法）

🍅 线性探测

🍅 二次探测

🍋开散列（链地址法）

六、总结

七、共勉

一、前言

哈希（Hash）是一个广泛的概念，其中包括哈希表、哈希冲突、哈希函数等，核心为 元素（键值）与存储位置（哈希值） 之间的映射关系，哈希值 可以通过各种哈希函数进行计算，需要尽量确保 “唯一性”，避免冲突，除此之外，哈希函数还可用于 区块链 中，计算区块头（Head）中的信息，本文将带你认识哈希，学习其中的各种知识

二、什么是哈希表？

💧哈希的由来 💧

在学习过【数据结构】后我们都知道，数组和链表都有它们各自的特点：

数组特点：访问(寻址)速度较快的、但插入、删除操作较慢；
链表特点：访问(寻址)速度较慢的、但插入、删除操作很快；

所以，有些大牛就想着能不能结合这数组、链表的优点，造出一个 访问(寻址)速度较快的、插入、删除操作也很快 的数据结构，后面就造出来一个【哈希表】。

💧哈希思想💧

哈希（Hash） 是一种映射思想，规定存在一个唯一的 哈希值 与键值之前建立映射关系，由这种思想而构成的数据结构称为 哈希表（散列表）

举例说明：

给定 𝑛 个学生，每个学生都有“姓名”和“学号”两项数据。假如我们希望实现“输入一个学号，返回对应的姓名”的查询功能，则可以采用下图所示的哈希表来实现。

💧哈希表的概述 💧

顺序结构 以及 平衡树中，元素关键码 与其 存储位置 之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。而顺序查找时间复杂度为 O ( N ) ，在平衡树中查找的时间复杂度为树的高度即 O(log)，搜索的效率取决于搜索过程中元素的比较次数。

最为理想的搜索方法是，可以不经过任何比较，一次直接从表中得到要搜索的元素，即查找的时间复杂度为 O(1)。

如果构造一种存储结构，能通过某种函数（hashFunc）使元素的存储位置与它的关键码之间能够建立一种映射的关系，那么在查找时通过该函数可以很快找到该元素。

向该结构当中插入和搜索元素的过程如下：

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

该方式即为哈希（散列）方法，哈希方法中使用的 转换函数 称为 哈希（散列）函数，构造出来的结构称为 哈希表（散列表）。

举例说明：

现在有这样一组数据集合 {1, 7, 6, 4, 5, 9}。

把哈希函数设置为：hash(key) = key % capacity（其中 capacity 为存储元素底层空间总的大小）。
然后我们把该集合存储在 capacity 为 10 的哈希表中，则各元素存储位置对应如下：

显然，这个哈希表并没有把所有位置都填满，数据分布无序且分散

因此，哈希表 又称为 散列表

用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快，但是也会存在一些问题。

如果现在向集合中插入元素 66，会出现什么问题？

三、哈希冲突

不同关键字 通过相同 哈希函数 计算出 相同的哈希地址，该种现象称为 哈希冲突 或 哈希碰撞，把具有不同关键码而具有相同哈希地址的数据元素称为 同义词。

如果此时再将元素 66 插入到上面的哈希表，因为元素 66 通过该哈希函数计算得到的哈希地址与元素 6 相同，都是下标为 6 的位置，那么就会产生哈希冲突。

四、哈希函数

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

🍓哈希函数设计原则

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

🥝常见的哈希函数

1、直接定址法（常用）

函数原型：HashI = A * key + B

优点：简单、均匀
缺点：需要提前知道键值的分布情况
适用场景：范围比较集中，每个数据分配一个唯一位置

2、除留余数法（常用）

假设 哈希表 的大小为 m

函数原型：HashI = key % p (p < m)

优点：简单易用，性能均衡
缺点：容易出现哈希冲突，需要借助特定方法解决
适用场景：范围不集中，分布分散的数据

3、平方取中法（了解）

函数原型：HashI = mid(key * key)

适用场景：不知道键值的分布，而位数又不是很大的情况

假设键值为 1234，对其进行平方后得到 1522756，取其中间的三位数 227 作为 哈希值

五、哈希冲突解决

解决哈希冲突有两种常见的方法是：闭散列 和 开散列。

🍇 闭散列（开放定址法）

闭散列，也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把产生冲突的元素存放到冲突位置的下一个空位置中去。

那如何寻找下一个空位置呢？常见的方式有以下两种。

🍅 线性探测

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

查找公式：hashi = hash(key) % N + i。

其中：

hashi：冲突元素通过线性探测后得到的存放位置。
hash(key) % N：通过哈希函数对元素的关键码进行计算得到的位置。
N：哈希表的大小
i 从 1、2、3、4…一直自增
注意：表里面可以存 key，也可以存储 key/value 的 pair 对象。

举个例子，现在有这样一组数据集合 {10, 25, 3, 18, 54, 999} 我们用除留余数法将它们插入到表长为 10 的哈希表中。

现在需要插入新元素 44，先通过哈希函数计算哈希地址，hashAddr 为 4，因此 44 理论上应该插在该位置，但是该位置已经放了值为 4 的元素，即发生哈希冲突。
然后我们使用线性探测的计算公式 hashi = 44 % 10 + 1 = 5 但是下标为 5 的位置已经被占用了，那么继续计算 hashi = 44 % 10 + 2 = 6 下标为 6 的位置没有被占用，那么就把 44 插入到该位置。

如果随着哈希表中数据的增多，产生哈希冲突的可能性也随着增加，假设现在要把 33 进行插入，那么会连续出现四次哈希冲突。

我们将数据插入到有限的空间，那么空间中的元素越多，插入元素时产生冲突的概率也就越大，冲突多次后插入哈希表的元素，在查找时的效率必然也会降低。因此，哈希表当中引入了负载因子（载荷因子）：

散列表的载荷因子定义为：α＝填入表中的元素个数／散列表的长度
负载因子越大，产出冲突的概率越高，增删查改的效率越低。
负载因子越小，产出冲突的概率越低，增删查改的效率越高。

假设我们现在将哈希表的大小改为 20，再把上面的数据重新插入，可以看到完全没有产生的哈希冲突：

但是，如果负载因子越小，也就意味着空间的利用率越低，此时大量的空间实际上都被浪费了。对于开放定址法，荷载因子是特别重要因素，应严格限制在 0.7~0.8 以下。超过 0.8 时，查表时的 CPU 缓存不命中（cache missing）按照指数曲线上升。
因此，一些采用开放定址法的 hash 库，如 Java 的系统库限制了荷载因子为 0.75，超过此值将 resize（增容）散列表。

总结：

线性探测优点：实现非常简单，
线性探测缺点：一旦发生哈希冲突，所有的冲突连在一起，容易产生数据堆积，即：不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低。

如何缓解呢？

🍅 二次探测

线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为：hashi = hash(key) % N + i^2（i = 1、2、3、4…）

hashi：冲突元素通过线性探测后得到的存放位置。
hash(key) % N：通过哈希函数对元素的关键码进行计算得到的位置。
N：哈希表的大小
i 从 1、2、3、4…一直自增，每次加的是i^2

举个例子，现在有这样一组数据集合 {10, 21, 25, 18, 999} 我们用除留余数法将它们插入到表长为 10 的哈希表中。

现在需要插入新元素 60，先通过哈希函数计算哈希地址，hashAddr 为 0，因此 60 理论上应该插在该位置，但是该位置已经放了值为 10 的元素，即发生哈希冲突。
然后我们使用线性探测的计算公式 hashi = 60 % 10 + 0^2 = 0 但是下标为 0 的位置已经被占用了，那么继续计算 hashi = 60 % 10 + 1^2 = 1 下标为 1 的位置也被占用，那么继续计算 hashi = 60 % 10 + 2^2 = 4 下标为 4 的位置没有被占用，那就把 60 插入到该位置。

采用二次探测为产生哈希冲突的数据寻找下一个位置，相比线性探测而言，采用二次探测的哈希表中元素的分布会相对稀疏一些，不容易导致数据堆积。

和线性探测一样，采用二次探测也需要关注哈希表的负载因子，例如，采用二次探测将上述数据插入到表长为 20 的哈希表种，产生冲突的次数也会有所减少：

研究表明：当表的长度为质数且表装载因子不超过 0.5 时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子不超过 0.5，如果超出必须考虑增容。

因此：闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷。

🍋开散列（链地址法）

开散列，又叫链地址法（开链法或者哈希桶），首先对关键码集合用哈希函数计算哈希地址，把具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。

举个例子：

现在有这样一组数据集合 {40, 5, 10, 21, 66, 55, 50, 18, 27} 我们用除留余数法将它们插入到表长为 10 的哈希表中，当发生哈希冲突时我们采用开散列的形式，将哈希地址相同的元素都链接到同一个哈希桶下，插入过程如下：

【闭散列】解决哈希冲突，采用的是一种报复的方式，“我的位置被占用了我就去占用其他位置”。而【开散列】解决哈希冲突，采用的是一种乐观的方式，“虽然我的位置被占用了，但是没关系，我可以挂在这个位置下面”。

与闭散列不同的是，这种将相同哈希地址的元素通过单链表链接起来，然后将链表的头结点存储在哈希表中的方式，不会影响与自己哈希地址不同的元素的增删查改的效率，因此开散列的负载因子相比闭散列而言，可以稍微大一点。

闭散列的开放定址法，负载因子不能超过 1，一般建议控制在 0.0 ~ 0.7 之间。
开散列的哈希桶，负载因子可以超过 1，一般建议控制在 0.0 ~ 1.0 之间。

在实际中，开散列的哈希桶结构比闭散列更实用，主要原因有两点：

哈希桶的负载因子可以更大，空间利用率高。
哈希桶在极端情况下还有可用的解决方案。

哈希桶的极端情况就是，所有元素全部产生冲突，最终都放到了同一个哈希桶中，此时该哈希表增删查改的效率就退化成 O ( N )

这时，我们可以考虑将这个桶中的元素，由单链表结构改为红黑树结构，并将红黑树的根结点存储在哈希表中。

在这种情况下，就算有十亿个元素全部冲突到一个哈希桶中，我们也只需要在这个哈希桶中查找 30 次左右，这就是所谓的 桶里种树 。

为了避免出现这种极端情况，当桶当中的元素个数超过一定长度，有些地方就会选择将该桶中的单链表结构换成红黑树结构。
在JDK1.7中，HashMap 由 数组 + 链表 组成，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的。

在 JDK1.8 中，HashMap 由数组 + 链表 + 红黑树组成。当链表过长，则会严重影响 HashMap 的性能，红黑树搜索时间复杂度是 O ( l o g N )，而链表是 O ( n ) 。因此，JDK1.8 对数据结构做了进一步的优化，引入了红黑树，链表和红黑树在达到一定条件会进行转换：当链表超过 8 且数组长度（数据总量）超过 64 才会转为红黑树。