这篇文章将添加个人所谓的鱼类疯狂言论。
❤️❤️❤️鱼式疯言:❤️❤️❤️这种疯言非彼疯言。
相反，我理解并总结了通俗易懂的白话。
小编会在每个概念之后尽可能多地插入鱼式疯言，帮助大家理解.。
🤭🤭🤭可能没那么严谨，但小编的初衷是让更多的人接受我们的概念 ！！！
当今信息爆炸的时代，快速检索和处理数据尤为重要。想象一下，如果你有一个巨大的图书馆，你需要在几秒钟内找到一本特定的书，你会怎么做？这就是哈希表的魔力所在。哈希表具有高效的数据检索能力，它已成为现代计算机科学的关键技术。本文将深入探讨哈希表的工作原理，如何优化数据存储和检索，以及它如何解决数据存储中的冲突。
哈希表的初识。
哈希冲突。
什么是哈希表？f; 简单来说。
哈希表是一种手柄。
key值。通过。哈希函数。映射到。 指定位置在数组中。的。 快速搜索方便快捷c; 插入， 删除。一种数据结构。
这里的。
快速。， 能达到多快？ 一般可以实现。O(1)。的。 时间复杂。的。 常数级别。的效率。
在这里。 Key 值。， 不仅仅是。
整数数据。， 也可以是。字符串。， 包装类型。作为key的数据 然后映射成数组。索引（下标）， 方便搜索。
想象一下， 如果有一排带锁的柜子， 手里有一串钥匙。
假如你的一切。 哪把钥匙对应几个柜子没有标记。， 需要逐一比较， 此时需要遍历。 每一把钥匙。开锁， 这时的。 效率会很低。。
但是如果你标记了哪把钥匙对应哪个柜子？ ， 例如，标有5号柜和#xff0的黑色钥匙c; 然后我只需要把黑钥匙对着5号柜子就可以快速解锁， 打开5号柜不需要遍历所有钥匙c; 这样的。 效率会很高。。
对于。 key。怎么利用。 哈希函数。转化成。 数组索引位置。， 让我们来看看吧 🥩🥩🥩
补充说明。：
也叫哈希表。 散列表。， 散列的英语是。
hash。， 而key 中文名也叫。关键码。。
哈希表的速度在于， 不需要对关键码进行多次比较找到 自己的位置。， 就可以。
快速通过索引的位置。进行操作。
对于。 哈希函数。有两种常用的设计方法。
直接定制法。
除余数法。
直接定制法 用公式法表示。
Hash(k) = A* k + B。以这种方式， 将。key。通过这样的哈希函数，将值转换为。 一个值。。
我们称之为这个哈希函数。 线性函数。， 我们称之为通过这个线性函数获得的值。
哈希值。。
小伙伴们可以先写这个问题：
题目： 字符串中出现一次。
问题解码：
class Solution。 { 。return。i。;}。}。return。-1。;}。}。在这个问题中， 我们使用这种哈希函数和哈希映射思维，
通过一个数组模拟哈希表， 因为我们要找 字符的类型和数量， 所以我们就 new。 一个长度为 26。模拟哈希表的数组。
count[ch-'a']++;
因为都是。
小写字母。，我们必须这样做。 小写字母。映射成。下标数组。， 并且要从。0开始映射， 我们必须在小写字母的基础上 减去一个 字符。‘a’。， 可以映射。0~25。位置的。 字符。, 而且这里的数组。元素值也可以表示次数。。
上面的栗子可以通过字符反映字符 == Ak + B 线性函数== 映射标值， 其中。
A = 1 ， B = - 26。， 从而确定。0~25。下标范围。
充分体现。 在字符统计中搜索哈希函数。的作用。
补充说明。：
用。
下标。来表示。 字符类型。， 用。数组的值。来。 出现字符的次数。。
- 线性哈希函数的缺点： 适用于数据。
范围比较小。且。 连续。的情况。
优先:。 简单，均匀。。
对于。 保留余数法。， 其实很简单。
先看公式：
hash(k) = key % capacity。；
其中。
key。就是。 关键码。， 而 ·。capacity。就是。 实际数组的容量大小。。 通过上述的 该计划将key转化为哈希值。
如上图所示a;
利用。
key。通过。除余数法。来获取。 下标位置。， 从而确定。 找到的位置。。
以上两种。 哈希函数。获取。 hashcode。(哈希值) 常用的方法是， 但并不是说只有两种方法，在获取。 哈希值方案。有很多。
从以上过程，虽然反映了。 哈希函数。简单易用， 但是使用。哈希函数也会遇到相关问题。。
以上第二个方案： 除了留余数法。
在这个过程中， 以下情况可能发生。
如上图中 ， 56。哈希值是由哈希函数映射出来的。 6。， 而原先的 26 哈希值也是通过哈希值映射出来的。 6。。
上述， 两个不同的关键码。通过。
哈希函数相同。映射出。 哈希值相同。， 我们称之为。哈希冲突。。 又称之为。哈希碰撞。。
出乎意料地出现了。 哈希冲突。这样的问题， 然后我们需要思考如何应对。 哈希冲突。的方案。
在谈到解决哈希冲突之前， 还会产生另一个因素。 哈希冲突。的情况 ， 那就是。 负载因子。。
首先， 我们需要明确什么是负载因素 ？
负载因子。 a = size / capacity。， 其中。 size。表示。 现有数据数量。， capacity。表示。 数组容量大小。。
那么这个。 负荷因子与哈希发生冲突。之间是呈。 什么关系。? ? ?
从上图来看，， 冲突率和负载因子。 正相关。关系， 也就是说。 负载因子越大 冲突率越高。， 产生的可能性越大。 哈希冲突。。
这就是小编所理解的。
size代表关键码的数量， 做分子， 也就是说，对于数组来说，， 插入关键码越多， 对于数组本身， 剩余空间是否越小，已插入的空间位置越多， 然后很容易遇到已经插入的情况。 位置空间的关键码。。
补充说明。：
从上图中� 我们能看到。 两个极端点。：
当。
负载因子为0。时， 冲突率为 0。， 就说明当。 数组中没有元素。了 ， 哈希冲突不会发生。
当。 负载因子为1。时， 冲突率为 1。， 就说明当。 数组中的元素 .>= 数组的大小。时，
哈希冲突肯定会发生。, 所以一定要保证。 数组容量 > 实际元素的大小。。
以下小系列从以上两个可能导致哈希冲突的因素出发 建立两种解决方案。 解决哈希冲突。
由于 负载因子。 a = size / capacity。。
从。 公式的角度。来看看，
size。确定， 我们不能改变。 关键码的数量。， 所以我们只能改变。数组的容量。。
也就是说，� 当负载因子达到一定大小时。， 就需要。 扩大数组的容量。， 使。
capacity。增加， 从而是。 a 减少。， 进而降低。 哈希冲突。的可能。
比如小编后面要讲解的。 Java标准库。实现的。 hashmap。的负载因子 是。 0.75。，当不断对。 hashmap。插入元素时， size。它将继续增加， 当。 a >= 0.75。后， 只是需要进行。扩容操作。
假如发现以下内容。 哈希冲突。。
我们可以去。
下一个。没有存放。 修改关键码的位置。， 如果下一个是存储关键码的哈希地址， 会一直往后走 直到遇到没有关键码的位置。才插入。当前关键码。。
补充说明。：
虽然线性探测很简单，但是有一个缺点， 当出现了。
哈希冲突。，由于。 一直向后。， 就会使。key。一直。 集中在相邻区域。，会使。 关键码比较集中。。
二次探测实际上是利用哈希函数重新找到新位置的一种方法。
H（i） =( h(0) + i ^ 2 ) / capacity。
其中。 H（i）表示。 新的哈希地址。， h（0）发送哈希冲突的地址， i。代表。 探测次数。。
如果。 第一次探测 i 就放置为 1。， 如果探测位置再次遇到 已经。
关键码存在。，那么 i++ ， 就会进行。 第二次探测。， 以此。循环往复。， 找到最终的执行。 可插入的空位。。
如上图所示c; 哈希桶的思维是把数组放在上面。 每个小集合。如上所示。 链表连接。
下标在上图中 6 位置已经有26个数据， 那么如果。 56 要插入 下标6位置。， 尾插需要进行。 26节点后面。。
这种方案的优点是如果发生的话。 哈希冲突。， 额外的关键码可以连接到这个。 链表尾部的索引。， 进行。
尾插。。
这个时候一定有朋友提出疑惑， 这里需要搜索数据 肯定要。 遍历链表。#xff0c; 那么遍历链表的复杂度还是O（1） ？
答案： 还是。
由于负载因子的存在，链表的长度不会太长。， 所以。 到处都是很少的节点。的。
而且对于哈希桶来说，， 一旦。 数组的长度 >= 64。并且。 链表的长度 >= 8。， 链表会变成一个。 红黑树。。
因此，时间的复杂性也可以相似等于。 O（1）。
哈希手表初识：除识哈希表是一种关键码转换 #xff08数组索引;下标）能达到时间复杂度的一种。 O(1) 数据结构。， 并了解常见情况。 两种哈希函数法。： 直接定制法和除留余数法。
#xff1a; 两种可能导致哈希冲突的情况： 设计和哈希函数 负载因子的增加。， 并列出了两种解决哈希冲突的方案： 闭散列。和。 开散列。。
.。
假如觉得小编写的还不错，我们可以支持。 三连。下 (定有回访哦) , 请在评论区进行评论。 指正。
我希望我的文章能给你带来一点收获，哪怕是一点收获 小编创作 的最大。 动力。💖 💖 💖
