l

o

g

2

N

log_2 N

log2​N)，搜索的效率取决于搜索过程中元素的比较次数

而理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素

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

当向该结构中插入和删除时：

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

那么这种方式即为哈希（散列），哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)

用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快

问题：按照上述哈希方式，向集合中插入元素44，会出现什么问题？ 哈希冲突！

二. 哈希冲突

也叫哈希碰撞：不同关键字通过相同哈希哈数计算出相同的哈希地址，比如在上述的例子中再插入44就会产生哈希冲突，因为44模10后，也等于4

三. 哈希函数

不合理的哈希函数就是引发哈希冲突的重要原因，哈希函数设计的越精妙，产生哈希冲突的可能性越低！

哈希函数的设计遵从三大原则：

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

常见的哈希函数有：

1. 直接定址法（常用）
   取关键字的某个线性函数为散列地址：

优点：简单、均匀
缺点：需要事先知道关键字的分布情况
使用场景：适合查找比较小且连续的情况

2. 除留余数法–(常用)
   设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：(p<=m),将关键码转换成哈希地址

优点：使用广泛，不受限制
缺点：需要解决哈希冲突，冲突越多，效率越低

3. 平方取中法–(了解)
   假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址；
   再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址

平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况

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

折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况

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

数字分析法通常适合处理关键字位数比较大的情况，或事先知道关键字的分布且关键字的若干位分布较均匀的情况。

注意：哈希函数设计的越精妙，产生哈希冲突的可能性越低，但是无法避免哈希冲突。

四. 如何解决哈希冲突？

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

🌏闭散列 —— 开放定址法

H0：通过哈希函数对元素的关键码进行计算得到的位置
Hi：冲突元素通过线性探测后得到的存放位置
m：表的大小

例如，我们用除留余数法将序列{1, 6, 10, 1000, 11, 18, 7, 40}插入到表长为10的哈希表中，当发生哈希冲突时我们采用闭散列的线性探测找到下一个空位置进行插入，插入过程如下：

通过上图可以看出：随着哈希表中数据的增多，产生哈希冲突的可能性也随着增加，最后在40进行插入的时候更是连续出现了四次哈希冲突（踩踏效应）

我们将数据插入到有限的空间中，随着数据的增多，冲突的概率越发越多，冲突多的时候插入的数据，在查找时候效率也会随之低下，为此引入了负载因子：

负载因子 = 表中有效数据个数 / 空间的大小

• 负载因子越大，产生的概率就越多，增删查改的效率越低
• 负载因子越小，产生的概率就越少，增删查改的效率越高，但是越小也意味着空间利用率越低，此时大量空间可能被浪费

如果我们把哈希表增大变成20，可以发现在插入相同数据时，产生的冲突会少

因此我们在闭散列（开放定址法）对负载因子的标准定在了 ，一旦大于 0.8 会导致查表时缓存未命中率呈曲线上升；这就是为什么有些哈希库都有规定的负载因子，Java 的系统库就将负载因子定成了 0.75，超过 0.75 就会自动扩容

😎作总结：

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

2. 二次探索
   线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为：以2的i次方进行探测

Hi=(H0+i*i)%m  ( i = 1 , 2 , 3 , . . . )

H0：通过哈希函数对元素的关键码进行计算得到的位置。
Hi：冲突元素通过二次探测后得到的存放位置。
m：表的大小

接下来举个例子：

但是二次探测没有从本质上解决问题，还是占用式的占用别人位置

🌏开散列——链地址法（拉链法）

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

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

• 开散列的哈希桶，负载因子可以超过1，一般建议控制在[0.0, 1.0]之间

为什么开散列在实际中，更加实用呢？

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

哈希桶的极端情况就是：所以元素全部都挂在一个节点下面，此时的效率为O（N）

一个桶中如果元素过多的话，可以考虑用红黑树结构代替，并将红黑树的根结点存储在哈希表中

这样一来就算是有十亿个数，都只要在这个桶里查找30次，这就是桶里种树

五. 闭散列的实现

在闭散列的哈希表中，每个位置不仅仅要存放数据之外，还要存储当前节点的状态，三大状态如下：

• EMPTY（空位置）
• EXIST（已经存放数据了）
• DELETE（原本有数据，但被删除）

对此我们可以用枚举实现：

那么状态的存在意义是什么？

💢举个例子：当我们需要在哈希表中查找一个数据40，这个数据我用哈希函数算出来他的位置是 0 ，但是我们不知道是不是存在哈希冲突，如果冲突就会向后偏移，我们就需要从 0 这个位置开始向后遍历，但是万万不能遍历完整个哈希表，这样就失去了哈希原本的意义

• 通过除留余数法得知元素在哈希表中的地址0
• 从0下标开始向后进行查找，若找到了40则说明存在，找到空位置判定为不存在即可

但是这样真的行得通吗？如果我是先删除了一个值1000，空出的空位在40之前，查找遇到空就停止了，此时并没有找到元素40，但是元素40却在哈希表中存在。

因此我们必须要给哈希表中的每个节点设置一个状态，有三种可能：当哈希表中的一个元素被删除后，我们不应该简单的将该位置的状态设置为EMPTY，而是应该将该位置的状态设置为

这样一来在查找的时候，遇到节点是或者的都要继续往后找，直到遇到空为止；而当我们插入元素的时候，可以将元素插入到状态为EMPTY或是DELETE的位置

所以节点的数据不仅仅要包括数据，还有包括当前的状态

为了要在插入的时候算好负载因子，我们还要记录下哈希表中的有效数据，数据过多时进行扩容

🎨数据插入

步骤如下：

1.查找该键值对是否存在，存在则插入失败
2.判断是否需要扩容：哈希表为空 & 负载因子过大 都需要扩容
3. 插入键值对
4. 有效元素个数

其中扩容方式如下：

• 如果是哈希表为空：就将哈希表的初始大小增大为10
• 如果是负载因子大于0.7： 先要创建一个新的哈希表（大小是原来的两倍），遍历原哈希表，旧表的数据映射到新表（此处复用插入），最后两个哈希表互换。

此处要注意：是将 旧表的数据重新映射到新表，而不是直接把原有的数据原封不动的搬下来，要重新计算在新表的位置，再插入

产生了哈希冲突，就会出现踩踏事件，不断往后挪，又因为每次插入的时候会判断负载因子，超出了就会扩容，所以哈希表不会被装满！

🎨数据查找

步骤如下：

1. 先判断哈希表大小是否，如果为零查找失败！
2. 通过除留余数法算出对应的哈希地址
3. 从哈希地址开始向后线性探测，直到遇到 位置还没找到则查找失败，如果遇到状态是的话，也要继续往后探测，因为该值已经被删掉了

💢注意：key相同的前提是状态不能是：删除。必须找到的是位置状态为 且 值匹配，才算查找成功（不然找到的数据相同的，确实被删除了的）

🎨数据删除

删除的步骤比较简单：修改状态 —— 减少元素个数

1. 检查哈希表中是否存在该元素
2. 如果存在，把其状态改成即可
3. 哈希的有效元素个数

注意：我们这里是伪删除：只是修改了数据的状态变成，并没有把数据真正的删掉了，因为插入时候的数据可以覆盖原有的 —— 数据覆盖

🎨仿函数

如果我们统计的是字符串的出现次数呢？还能取模吗？怎么样转化string呢 —— 其实大佬早就帮我们想到了

仿函数转化成一个可以取模的值

• 将key数据强制类型转换成，如果key是string类型的就走string类型的特化版本
• 这样就可以不用显示的传属于哪个Hashfunc

涉及到了BKDR算法，因为ascll码值单纯地加起来，可能会出现相同现象，大佬推算出了这个算法

特化：符合string类型的优先走string类型

template
struct Hashfunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};

//特化版本
template<>
struct Hashfunc
{
//BKDR算法
size_t operator()(const string& key)

[外链图片转存中…(img-f1TcRUxq-1714179355216)]
[外链图片转存中…(img-58Qcvdod-1714179355217)]

网上学习资料一大堆，但如果学到的知识不成体系，遇到问题时只是浅尝辄止，不再深入研究，那么很难做到真正的技术提升。

需要这份系统化资料的朋友，可以戳这里获取