目录
一、前言
二、什么是哈希表？
?哈希的由来 ?
?哈希思想?
?哈希表的概述 ?
三、哈希冲突
四、哈希函数
?哈希函数设计原则
?常见的哈希函数
五、哈希冲突解决
? 闭散列（开放定址法）
? 线性探测
? 二次探测
?开散列（链地址法）
六、总结
七、共勉
一、前言
哈希（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 的哈希表中。
hashi = 44 % 10 + 1 = 5 但是下标为 5 的位置已经被占用了，那么继续计算 hashi = 44 % 10 + 2 = 6 下标为 6 的位置没有被占用，那么就把 44 插入到该位置。 
我们将数据插入到有限的空间，那么空间中的元素越多，插入元素时产生冲突的概率也就越大，冲突多次后插入哈希表的元素，在查找时的效率必然也会降低。因此，哈希表当中引入了负载因子（载荷因子）：
散列表的载荷因子定义为：α＝填入表中的元素个数／散列表的长度负载因子越大，产出冲突的概率越高，增删查改的效率越低。负载因子越小，产出冲突的概率越低，增删查改的效率越高。假设我们现在将哈希表的大小改为 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…）
举个例子，现在有这样一组数据集合 {10, 21, 25, 18, 999} 我们用除留余数法将它们插入到表长为 10 的哈希表中。
和线性探测一样，采用二次探测也需要关注哈希表的负载因子，例如，采用二次探测将上述数据插入到表长为 20 的哈希表种，产生冲突的次数也会有所减少：
因此：闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷。
?开散列（链地址法）
开散列，又叫链地址法（开链法或者哈希桶），首先对关键码集合用哈希函数计算哈希地址，把具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。
举个例子：
现在有这样一组数据集合 {40, 5, 10, 21, 66, 55, 50, 18, 27} 我们用除留余数法将它们插入到表长为 10 的哈希表中，当发生哈希冲突时我们采用开散列的形式，将哈希地址相同的元素都链接到同一个哈希桶下，插入过程如下：
与闭散列不同的是，这种将相同哈希地址的元素通过单链表链接起来，然后将链表的头结点存储在哈希表中的方式，不会影响与自己哈希地址不同的元素的增删查改的效率，因此开散列的负载因子相比闭散列而言，可以稍微大一点。
闭散列的开放定址法，负载因子不能超过 1，一般建议控制在0.0 ~ 0.7 之间。开散列的哈希桶，负载因子可以超过 1，一般建议控制在 0.0 ~ 1.0 之间。 在实际中，开散列的哈希桶结构比闭散列更实用，主要原因有两点：
哈希桶的负载因子可以更大，空间利用率高。哈希桶在极端情况下还有可用的解决方案。哈希桶的极端情况就是，所有元素全部产生冲突，最终都放到了同一个哈希桶中，此时该哈希表增删查改的效率就退化成 O ( N )
将链表转换成红黑树前会判断，如果当前数组的长度小于64，那么会选择先进行数组扩容，而不是转换为红黑树，以减少搜索时间。
但有些地方也会选择不把桶中的单链表结构换成红黑树结构，因为随着哈希表中数据的增多，该哈希表的负载因子也会逐渐增大，最终会触发哈希表的增容条件，此时该哈希表当中的数据会全部重新插入到另一个空间更大的哈希表，此时同一个桶当中冲突的数据个数也会减少，因此不做处理问题也不大。
六、总结
哈希表总结：
哈希表（Hash Table）：通过键 key 和一个映射函数 Hash(key) 计算出对应的值 value，把关键码值映射到表中一个位置来访问记录，以加快查找的速度。
哈希函数（Hash Function）：将哈希表中元素的关键键值映射为元素存储位置的函数。
哈希冲突（Hash Collision）：不同的关键字通过同一个哈希函数可能得到同一哈希地址。
哈希表的两个核心问题是：「哈希函数的构建」 和 「哈希冲突的解决方法」。
常用的哈希函数方法有：直接定址法、除留余数法、平方取中法、基数转换法、数字分析法、折叠法、随机数法、乘积法、点积法等。
常用的哈希冲突的解决方法有两种：开放地址法 和 链地址法。
哈希表的结构：
JDK1.8以前哈希表是由数组+链表组成
JDK1.8开始哈希表是由数组+链表+红黑树组成
加入红黑树的好处：
链表的特点是增删快，查询慢。所以链表越长就会导致查询越慢，而红黑树恰好解决这一问题。
数组长度：未定义数组长度会创建一个初始化长度为16的数组。
七、共勉
以下就是我对 【C++】哈希表的理解，如果有不懂和发现问题的小伙伴，请在评论区说出来哦，同时我还会继续更新【C++】，请持续关注我哦！！！
