哈希 & 布隆过滤器（转载）

心已赠人 2023-07-20 08:19 13阅读 0赞

转：[https://blog.csdn.net/duoduo18up/article/details/80573040][https_blog.csdn.net_duoduo18up_article_details_80573040]

# 哈希函数： #

常见的功能就是 打乱分布 均匀随机 输入无穷大 输出却在一定范围内

即使出现碰撞 但是每个输出对应的输入个数 概率均匀分布 没有太大偏向

**一个重要的性质**： 如果在input域上均匀分布 那么经过哈希并%m 运算后（在0~m-1范围内) 在输出域上同样均匀分布

![70][]

# 哈希表： #

**经典结构：**

根据key算出具体的hashcode值（h)----决定了value的存放位置

若 h 位置处为空 则直接将key1-value1 放入

若h位置处不为空 检查是否已有key1 若已有 则更新其对应value值 否则 直接按照链表格式，节点连在上一节点后面

![70 1][]

**经典应用：**

**场景题：**  如果现在有一个超级大的文件，需要统计其中重复的字符串 ，我们要怎么办？

**目前已知的：** 可以供给1000台计算机 读取细节不用关心 只需要设计大概系统

**思路** ：哈希的分流特性

**具体操作：** 将大文件读取很多行 每一行都计算哈希值 并模1000 则这些字符串均匀分布在0-999范围内

给电脑编号0-999 对应分布在一个范围内的一些字符串用同一台电脑进行处理 达到大数据分流的效果（类似于分布式）

每台电脑只统计自己处理的重复字符串 最后将结果进行汇总即可

![70 2][]

**总结**：

大数据相关的问题 有一半都是借助于哈希来解决 因为哈希具有“相同的肯定相同 不同的均匀分布”特性

在桶不够用时可以进行扩容 代价也还可以接受 一般是O(lognN)

## 设计一个RandomPool结构： ##

![70 3][]

**思路：**

因为 getRandom()函数要求等概率随机返回结构中的任意一个key

所以 一张哈希表在小样本情况下无法做到随机 需要至少两张哈希表

**举例：**

现在有26个字符串

分别按照顺序放入两个表中 两个表的key value 是对应的

用size统计此时表中数据个数 最后getRandom()时候直接 Math.random()\*26 来获取map2中对应key的value

![70 4][]

**部分代码：**

![70 5][]

**解决难点：** 删除过程中会在原有随机结构中出现好多洞 导致随机性变差 如何解决此问题？

**思路：**

![70 6][]

![70 7][]

**z最终的总代码：**

![70 8][]

![70 9][]

# 布隆过滤器： #

## 初识布隆过滤器： ##

**举例：** 假如有一个100亿 的url的黑名单，希望用户在搜索这些url时，会将 在黑名单中的url 过滤出去，不进行显示。

每个url都是64字节。 应该如何实现这个操作？

最直观的想法: 就是查找用户搜索的url 是否在黑名单中，根据具体情况返回布尔值 true or false.

![70 10][]

**思路1 ：**

考虑直接用哈希表 进行存储。 不用存value，直接存key ,则至少需要内存为 6400亿字节的hashset 数据结构（即640G）

这个内存很大，实际中我们可能需要多台电脑来操作（分布式）。

或利用哈希函数进行分流 但仍然很麻烦。

**思路2 ：**

布隆过滤器（某种类型的集合，但是存在失误率）

存在的唯一失误率： 如果确实在黑名单里的url肯定能够正确判断 但可能出现： 不在黑名单中的url但是它返回true 的情况~

**一般这种类型的题目：**

最好先说 哈希表的经典解法 ------多台电脑分流之类的

改进： 因为经典方法耗费内存太大----那询问是否允许较低的失误率----允许的话则可以采用布隆过滤器

## 布隆过滤器的细节： ##

**结构：**其实是一个bit数组 数组中存的是bit(0/1)

![70 11][]

**举例：**

![70 12][]

新建int数组 但其实相当于32000长度的bit数组

想要将第30000bit位上的数组描黑 -----则先确定在哪个大桶内-----再确定在那个桶中的哪个位上---原来数字和第bitIndex bit位上为1 的数字进行位或-----即得结果

**实现：**

拿基础类型即可实现

![70 13][]

要想再大 可以拿矩阵来表示 直接如上1000\*1000\*64bit

**黑名单问题的解决：**

![70 14][]

![70 15][]

![70 16][]

1 先准备一个长度为m bit 的数组 （范围为0--m-1)

2 布隆过滤器 预先准备多个hash函数 （hash1 ---hash2---hash3....hashk)

3 将黑名单中的url1(假设为第一条url) 分别经过上述k 个hash函数 计算出对应的k个 哈希值 ---并在数组中对应位置上描黑

4 将黑名单中所有的url都进行第3步操作 记录完毕

**如何判断用户搜索的url是否在黑名单中？**

同样将url经过第3步操作去看计算出的k个值对应的位置上是否都被描黑 若有一个不符合 则不是黑名单中的 否则 就在黑名单中

![70 17][]

![70 18][]

**相关的参数大小:**

![70 19][]

![70 20][]

![70 21][]

**如何解决误判问题：**

![70 22][]

### **相关问题：** ###

![70 23][]

![70 24][]

# 一致性哈希： #

![70 25][]

一般应用在服务器集群上 用以实现数据缓存

### **应用场景举例：** ###

![70 26][]

前端收到大量用户请求 ，该如何让后台的服务器进行储存和处理呢？

使用哈希---计算出对应哪个服务器处理----查询时---计算哈希---去找对应的服务器去查找

### **具体原理：** ###

![70 27][]

### 可能出现的问题及解决方法： ###

![70 28][]

![70 29][]

### 具体确定归属的细节： ###

![70 30][]

![70 31][]

### 增加机器时候的处理方法： ###

![70 32][]

![70 33][]

![70 34][]

### 机器负载不均时的处理（虚拟节点机制）： ###

![70 35][]

![70 36][]

![70 37][]

一致性哈希常用于负载均衡 分布式 服务器~~

#    并查集： #

### 并查集中集合的初始化过程： ###

![70 38][]

### 并查集的代表节点 ###

###    在并查集中查一个节点属于哪个集合？ ###

![70 39][]

### 如何路径压缩？ ###

![70 40][]

![70 41][] ![70 42][]

### 集合如何合并？ ###

![70 43][]

![70 44][]

### 代码： ###

**1 .初始化并查集：**

![70 45][]

**2 .查找某个节点所在集合的代表节点：**

![70 46][] **非递归版本代码** ![70 47][]

**3 .集合的合并**

![70 48][]

### 用途： ###

![70 49][]![70 50][]

## 岛问题： ##

![70 51][]

**正常方法（递归法）：**

**设置一个感染函数G 假设遇到一片1（可能上下左右均有） 则均感染为2 并计数+1 继续前进**

![70 52][]

![70 53][]

![70 54][]

总结：此方法类似于DFS，就是深度搜索 没有什么新意

而且矩阵一旦特别大则不实用 仅适合单cpu运行

如何能够多cpu并行运行，提高速度和效率呢？

并查集方法：

考虑分别的岛个数 和 边界处可能 合并的岛个数：

![70 55][]

大概原理： 分别统计各自部分的岛个数----在边界处标明是受哪个元素“感染”的，然后检查集合并合并 ，总数-1

![70 56][]

此处用并查集的优势： 涉及到大量集合合并 判断是否是一个集合的运算

![70 57][]

总结：

用多个cpu 分成多个部分 最终就只要每一个负责统计自己部分 的岛个数 并记录四周的边界情况即可

![70 58][]

[https_blog.csdn.net_duoduo18up_article_details_80573040]: https://blog.csdn.net/duoduo18up/article/details/80573040
[70]: /images/20230528/94b5d4c1afef43ad8ed3a0ca3b1efe46.png
[70 1]: /images/20230528/13fa44e804e74f83a6aa69793a96fe54.png
[70 2]: /images/20230528/a2ea30d53b274569a1e58f63f36ab7e0.png
[70 3]: /images/20230528/0807853848f24979be1f2c091bc3a320.png
[70 4]: /images/20230528/b8c704ecb90f4fabbbfce9abbe8b5d03.png
[70 5]: /images/20230528/4ba9b7720bb44cdcb0e64360ae88ad3f.png
[70 6]: /images/20230528/9a44cfa6aa064c4c9ef2fe743ce18f7c.png
[70 7]: /images/20230528/c0685f36f7b94eacab82cdc549f1042d.png
[70 8]: /images/20230528/983f917251f14ef6a64280daa7c52577.png
[70 9]: /images/20230528/fd06a826e406461f9fb5e97612df1669.png
[70 10]: /images/20230528/2da78ec81a8a480b8e8fb1e46e62534b.png
[70 11]: /images/20230528/ed522bc30b4b4ca7bc928bc50ddb4b2c.png
[70 12]: /images/20230528/b5438b3745a4491889d31f7c3a7f73c8.png
[70 13]: /images/20230528/6a846d99e07c4350ac909223ad48600d.png
[70 14]: /images/20230528/68d38eb16abf4d56af4c50ae5a218311.png
[70 15]: /images/20230528/b89be5388cc248aba133b7ed6998505c.png
[70 16]: /images/20230528/a6812cf3c480430f913f0610bb17dfe6.png
[70 17]: /images/20230528/ae5fd4ca1054441990e8d6b6ee9840aa.png
[70 18]: /images/20230528/c26231c73f4d424b9c083d205f1da794.png
[70 19]: /images/20230528/7652221f7cfb420f96b72768d95edbc1.png
[70 20]: /images/20230528/fcbf1eb4cdcf426ea3ff580099125552.png
[70 21]: /images/20230528/392ee0d272034a7b848bed249dfff87e.png
[70 22]: /images/20230528/bcd37457fd914cf08afc789aa5fe1c59.png
[70 23]: /images/20230528/7362c9f8079f4c3ab1814ff4e3089a86.png
[70 24]: /images/20230528/469f6f0ba6d74459a8a5edd42f93c7b9.png
[70 25]: /images/20230528/55539939871444278e8c8ad3073433f4.png
[70 26]: /images/20230528/afae1d06c7454fb98a17c0ef5d86eb75.png
[70 27]: /images/20230528/6c4b513ddc394abb9a83a1749bf3270b.png
[70 28]: /images/20230528/e411c53824544488b635c8386b254063.png
[70 29]: /images/20230528/67ae649f3a424e54ad23b950727c8b3c.png
[70 30]: /images/20230528/ab5105182534482db09f48d621ec5f38.png
[70 31]: /images/20230528/7d32277bb43347cf95ffbcfe260b0295.png
[70 32]: /images/20230528/51dc9371d9fa4ffa9df778dee8b3432a.png
[70 33]: /images/20230528/7e3ca15a90014550b0bd16b4a9335253.png
[70 34]: /images/20230528/b32b9939528a4dd2b03ff4142300eb2e.png
[70 35]: /images/20230528/30375ee8fcc342fdbb8a3e11a0964f9b.png
[70 36]: /images/20230528/3f1d4aebd3d74557ad2bfe7e3ccba36a.png
[70 37]: /images/20230528/a5848767d7f04a3d8a91961ea3b0ea28.png
[70 38]: /images/20230528/dad5657571634667888f3b4242a7d98e.png
[70 39]: /images/20230528/87c8517edbb149c4b337f090e70ac52e.png
[70 40]: /images/20230528/2b8d45d2ba184d3999fe300573989ad7.png
[70 41]: https://img-blog.csdn.net/20180606151549227?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2R1b2R1bzE4dXA=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 42]: /images/20230528/c2d415fdd28b41df9dd307b774457092.png
[70 43]: /images/20230528/dce4cee2e3754c508aa3ff2a25fbd258.png
[70 44]: /images/20230528/122fdb1950bd497ea178e914b27b736c.png
[70 45]: /images/20230528/b093848f01494f9d99c0f814bc7a25df.png
[70 46]: https://img-blog.csdn.net/20180606111433959?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2R1b2R1bzE4dXA=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 47]: /images/20230528/fb63556a57eb4d709e6a50c1b493eeca.png
[70 48]: /images/20230528/8d78490f396f458195397fd2d60cb9ab.png
[70 49]: https://img-blog.csdn.net/20180606201252823?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2R1b2R1bzE4dXA=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 50]: /images/20230528/6b1db9f46b20403aba08d098f776ef40.png
[70 51]: /images/20230528/b3d36d7e0cd8425397f736909a55e18d.png
[70 52]: /images/20230528/76b2e84c5b5b4606a6205cb1b4019b0e.png
[70 53]: /images/20230528/46ea20bc3d474d45ad71624ba168bebb.png
[70 54]: /images/20230528/7ee4822cab83476fa159383a27bf1595.png
[70 55]: /images/20230528/11dae5fa2bc84491ad26d6fc85b5ce99.png
[70 56]: /images/20230528/cdb2e69908614d22ade49748565b5f87.png
[70 57]: /images/20230528/77886f82643542f589c8ebe7ae133f17.png
[70 58]: /images/20230528/5de4e090ad8a4eacb4612dbc64d561dc.png