【数据结构】你真的了解哈希表吗？看完你会对数据结构——哈希表，会有更深更全面的认识（理论篇）

本篇会加入个人的所谓鱼式疯言

❤️❤️❤️鱼式疯言:❤️❤️❤️此疯言非彼疯言

而是理解过并总结出来通俗易懂的大白话,

小编会尽可能的在每个概念后插入鱼式疯言,帮助大家理解的.

🤭🤭🤭可能说的不是那么严谨.但小编初心是能让更多人能接受我们这个概念！！！

在这里插入图片描述

前言

在当今这个信息爆炸的时代，数据的快速检索和处理变得尤为重要。想象一下，如果你有一个巨大的图书馆，而你需要在几秒钟内找到特定的一本书，你会怎么做？这正是哈希表的魔力所在。哈希表以其高效的数据检索能力，成为了现代计算机科学中的一个关键技术。本文将深入探讨哈希表的工作原理、它如何优化数据存储和检索，以及它是如何解决数据存储中的冲突问题的。

一. 哈希表的初识

1. 哈希表的理解

什么是哈希表？简单来说

哈希表就是一种把 key值 通过 哈希函数 映射到 数组中指定位置 的方便快速查找，插入，删除的一种数据结构。

这里的 快速 ，可以达到多快呢? 大体上可以达到 O(1) 的时间复杂度的 常数级别 的效率。

其中这里的 Key 值，不仅仅是 整数数据 ，也可以是 字符串 ，包装类类型的数据当做key 然后映射成数组的 索引（下标） ，用来方便查找。

试想一下，如果有一排加了锁的柜子，和手中有一串钥匙。

如果你的都没有标记哪把钥匙对应几号柜子，就需要一个一个的进行比对，这时就需要遍历 每一个把钥匙 来进行开锁，这时的 效率就会很低 。

但是如果你标记了哪把钥匙对应着哪个柜子，比如这把黑色的钥匙上面标记着五号柜子，然后我只要把黑色的钥匙对着五号柜子就可以很快的开锁，不必遍历所有的钥匙来开五号柜子，这样的 效率就会很高 。

在这里插入图片描述

对于 key 怎么利用哈希函数转化成数组索引位置，下面就让我们来看看吧 🥩🥩🥩

鱼式疯言

补充说明 ：

哈希表又称之为 散列表 ，其中散列的英文就是 hash ，而key 的中文名称又称之为 关键码 。

哈希表的快就在于， 关键码不用进行多次比较来找到自身的位置 ，就可以 快速的通过索引的位置 进行操作。

2. 哈希函数

对于哈希函数的设计有常用的两种方式

直接定制法
除留余数法

<1>. 直接定制法

直接定制法，用公式法表示就是

Hash(k) = A* k + B 通过这样的方式，将 key 的值转为通过这样的哈希函数转化为 一个值 。

这个哈希函数我们称之为线性函数，而我们通过这个线性函数得到的这个值我们称之为 哈希值。

小伙伴们可以先写下这道题：

题目：字符串中出现一次的字符

题解代码：

class Solution {public int firstUniqChar(String s) {int []count=new int[26];for(int i=0;i<s.length();i++) {char ch=s.charAt(i);count[ch-'a']++;}for (int i = 0; i < s.length(); i++) {char ch=s.charAt(i);if(count[ch-'a']==1) {return i;}}return -1;}
}

在这道题中，我们就利用这种哈希函数的方式和哈希映射的思维，

通过一个数组来模拟哈希表，由于我们要寻找出现字符的种类和个数，所以我们就 new 一个长度为 26 的数组来模拟哈希表。

count[ch-'a']++;

因为都是 小写字母，我们要把该小写字母映射成 数组的下标 ，并且要从 0 开始映射，我们就要在小写字母的基础上减去一个字符 ‘a’ ，从而可以映射 0~25 位置的字符 , 并且这里数组的元素的值也可以表示次数 。

上面的栗子就可以体现字符通过 == Ak + B 的线性函数== 来映射下标值，其中 A = 1 ， B = - 26 ，从而确定好0~25 的下标范围。

充分体现了 哈希函数的在字符统计搜索 的作用。

鱼式疯言

补充说明：

上述用数组来 模拟哈希表 的作用就在于：

用 下标 来表示字符的种类，用 数组的值 来字符的出现的次数。

线性哈希函数的缺点：适合于数据 范围比较小 且连续的情况
优先: 简单，均匀。

<2>. 除留余数法

对于 保留余数法 ，其实就很简单

先看公式吧：

hash(k) = key % capacity；

其中 key 就是 关键码 ，而 ·capacity 就是实际数组的容量大小。通过上述的方案就讲key转化为哈希值。

在这里插入图片描述

如上图：

利用 key 通过 除留余数法 来获取下标位置，从而确定 查找的位置 。

鱼式疯言

以上的两种哈希函数获取 hashcode (哈希值) 的方法是比较常见的，但是不是说是唯一两种方法的，在获取哈希值的方案是有很多的。

从上面的过程，虽然体现了 哈希函数 的简便好用，但是使用哈希函数也会遇到相关的问题。

二. 哈希冲突

在我们使用上面第二种方案： 除留余数法

这个过程中，就有可能出现以下的情况

在这里插入图片描述

如上图中， 56 通过哈希函数映射出的哈希值是 6，而原先的 26 通过哈希值映射出来的哈希值也是 6 。

像上述，两个不同关键码通过 相同的哈希函数 映射出 相同哈希值 ，我们就称之为 哈希冲突 。又称之为 哈希碰撞 。

居然出现了 哈希冲突 的这样问题，那么我们就需要思路如何应对 哈希冲突 的方案

2. 负载因子

在谈及解决哈希冲突之前，还有一个因素也会产生 哈希冲突 的情况，那就是 负载因子 。

首先，我们要明确什么是负载因子？

负载因子 a = size / capacity ，其中 size 表示现有数据个数， capacity 表示数组的容量大小。

那么这个负载因子和哈希冲突之间是呈 什么关系 ? ? ?

在这里插入图片描述

从上面图像来看，冲突率与负载因子呈 正相关 的关系，也就是说 负载因子越大，冲突率越高，越容易产生 哈希冲突。

小编是这么理解的

size代表是关键码的个数，是做分子，也就是说对于数组来说，关键码插入的越多，对于数组本身来说，是不是剩余空间就越小，已插入的空间位置就越多，那么就跟容易遇到已经被插入 关键码的位置空间 。

鱼式疯言

补充说明：

从上图中，我们可以看到两个极端的点：

当 负载因子为0 时，冲突率为 0 ，就说明当 数组中没有元素 了，就一定不会产生哈希冲突。

当负载因子为1 时， 冲突率为 1 ，就说明当 数组中的元素 .>= 数组的大小 时， 就一定会产生哈希冲突 , 所以一定要保证数组容量 > 实际元素的大小。

下面小编讲从以上两种可能产生哈希冲突的因素来建立两种解决方案来 解决哈希冲突。

从负载因子的角度来解决

3. 降低负载因子

由于负载因子 a = size / capacity 。

从 公式的角度 来看， size 是确定了，我们无法改变 关键码的个数，所以我们只能改变 数组的容量 。

也就是说， 当负载因子达到一定的大小 ，就需要对数组进行扩容，使capacity 增大，从而是 a 减少，进而降低哈希冲突的可能。

例如小编后面要讲解的 Java标准库 中实现的的 hashmap 的负载因子是 0.75 ，当不断对 hashmap 中插入元素时， size 就会不断增大，当 a >= 0.75 后，就需要进行扩容操作。

从哈希函数的角度来解决

4. 闭散列

<1>. 线性探测

如果发现下面这样的 哈希冲突 。

在这里插入图片描述

我们就可以向 下一个 没有存放关键码的地方进行修改，如果下一个是存放过了关键码的哈希地址，就会一直往后走， 直到遇到没有关键码的位置 才插入 当前关键码 。

鱼式疯言

补充说明 ：

线性探测虽然简单，但是有一个不足的地方，当出现了 哈希冲突 ，由于 一直向后 ，就会使 key 一直 集中在相邻的区域 ，会使关键码比较集中。

<2>. 二次探测

二次探测其实是一个重新利用一个哈希函数来寻找新的位置

H（i） =( h(0) + i ^ 2 ) / capacity

其中 H（i） 表示 新的哈希地址 ， h（0） 表示发送哈希冲突的地址， i 代表探测的次数。

如果 第一次探测就 i 就放置为 1 ，如果探测的位置又遇到了已经 存在关键码，那么 i++ ，就会进行 第二次探测 ，以此 循环往复，最终执行找到可以插入的空位置。

5. 开散列

<1>. 哈希桶

在这里插入图片描述

如上图，哈希桶的思维就是把数组上 每一个小集合 如上所示用一个链表来连接

上图中在下标 6 位置已经存在26这个数据，那么如果 56 要插入到下标6位置，就需要进行尾插到 26节点的后面 。

这种方案的优点就在于如果发生哈希冲突，多出来的关键码就可以连接到该 索引的链表的尾部 ，进行 尾插 。

这时肯定有小伙伴提出疑惑了，这里需要要查找数据，肯定要 遍历链表 吧，那么遍历链表复杂度还是O（1）吗？

答案：还是

因为在由于负载因子的存在，链表的长度不会太长，所以 遍历起来的节点是很少 的
并且对于哈希桶来说，一旦数组的长度 >= 64 并且链表的长度 >= 8 的时候，链表就会变成一颗 红黑树。

所以时间复杂度也可近似等于 O（1）。

总结

哈希表的初识：除识了哈希表是一种讲关键码转化为数组索引（下标）的一种能达到时间复杂度为 O(1) 的数据结构，并通晓了常见的两种哈希函数法：直接定制法和除留余数法
哈希冲突：两种可能产生哈希冲突的情况： 哈希函数的设计和负载因子的增大 ，并列出两种解决哈希冲突的方案： 闭散列 和 开散列。