从 hashtable 到 bloomfilter

哈希表

提到哈希表，稍微有点编程基础的人都会对其非常熟悉。哈希表一种键值对的数据结构。那么回到最开始的位置，如果要我们来实现一个哈希表的，我们会怎么实现。

首先回到我们最常见的应用场景，我们使用哈希表添加一个键值对的时候，我们会怎么做，我们首先会判断当前哈希表里边有没有这个键。如果没有的话进行添加，有的话我们进行其他逻辑。

回到问题本身，哈希表是怎么去判断一个键值存在，直接相当的就是我们可以进行一个遍历呀，把所以哈希表遍历一遍，找到就有，没找到就没有。

但是这样太慢了，我们需要速度！为了这样，我们需要一个哈希函数。

哈希函数

首先需要明确目标，我们希望通过哈希函数达成这样的目标：

1、我们的键 key 经过哈希函数处理后，他的结果尽可能均匀散布在我们的哈希表中，这样我们的哈希表就能存储更多的数据。

2、我们的哈希函数尽可能的计算简单，不至于为了计算消耗太大的性能。

这里我们就用我们平时手机号取快递的例子，我们平时取快递都是用的尾号后四位取快递，那么这么多人，手机号相当于我们的 key， 经过取后四位这个哈希函数后，我们得到了我们后四位，他标记在我们的快递包裹中。

但是万一有人的后四位手机号和另一个人一摸一样怎么办？这就设计哈希冲突了。

哈希冲突

哈希冲突就是两个 key 经过哈希函数处理后得到结果一样，在我们的例子里边就是两个人的手机后四位一摸一样了。

那么这个时候怎么办？

首先我们可以做的激进一点，我们重新设计一个哈希函数，不是取后四位吗？我取后五位，后五位不行，我取后六位。这样做可不可以，可以，但是如果我们一有冲突就换函数也不是办法，毕竟我们现实这种冲突多了去了。

另一种就保守一点，哈希函数不是用很多空间吗？当前定位的空间不是满了吗？我把这个冲突的 key 存到你的下一个位置，在不行就是下下个位置，这样我只是在查找和插入的代码变化一下就行了，这就是开放寻址法

再一种就是我可以设计多个哈希函数呀，第一个哈希函数冲突，我用第二个哈希函数，第二个不行我用第三个。这就是二度哈希，学过语文的都知道，二是约数。

最后一种就是我们 Java 中的 hashmap 实现了，我把相同哈希值的 key 用链表连接起来，链表不管用了就加一个红黑树。

哈希函数

本来不打算说一些哈希函数处理，但是哈希函数的一些处理思想在大数据和分布式中有大量应用，所以简单说一下几种哈希函数设计思想。

第一种就是除法哈希法，简单来说就是将 key 想办法处理成一个数字，比方说对 key 每个字符相加，得到的数字对哈希表大小取模。这种思想在 redis 分布式应用和一些大数据应用场景都有看见。

第二种就是乘法哈希法，就是将 key 乘以一个 0-1 的随机数，得到结果取整数。这个就是随机性较强。

最后一种跟二度哈希有点类似，叫做全域哈希，就是在众多哈希函数中随机取一个进行哈希，得到结果进行存储，其好处就是当存储数据量太大，而哈希表又无法扩容，防止哈希表编程一个数组指针类型，但是这种无法判断 key 之前是否存过.，一般不用。

接下来就是我们主角布隆过滤器了，本次就简单说一下设计一个布隆过滤器的思想，之后再上代码。

布隆过滤器

首先确定一下，布隆过滤器是一种数据结构，布隆过滤器是一种数据结构，布隆过滤器是一种数据结构。

他是人为设计，然后设计后需要添加各种函数对其进行操作。

既然是一种数据结构，那就有规范，不能那个什么东西来了都说是布隆过滤器。

这几年大模型非常火，带动着很多做数据的公司发了财。那做数据就要有爬虫，如果只做一个网站爬虫那很容易，但是如果好几个爬虫同时爬，我怎么知道这个网站我之前爬过，这时候就是布隆过滤器的作用了。

布隆过滤器就是告诉你，这个网站我爬过，那个我没有爬过的的东西。注意他是没有办法存储 key 的 value 的，他只能告诉你有没有 key 这个值。

原理

布隆过滤器原理很简单，首先就是需要一个位数组。

位数组

位数组，顾名思义，每一个位就是一个数组元素，这也是布隆过滤器开销比哈希表笑的原因。

假如最开始的时候，这个位数组所有位数都是 0 ,那么我们设计 k 个哈希函数，根据 k 个哈希函数处理 key 得到 k 个值，我们将这个 k 个值位都设置为 1 。

那么再有 key 过来,我们判断一下,他计算的结果那 k 的位都是 1 吗，如果都是，那么表示这个 key 之前有，如果有一个不是，那表示这个 key 之前没有。

一些指标

布隆过滤器在性能上有一些指标的，这里简单聊一下。

首先我们说一个概念，一个就是误判率 p ，什么意思，就是两个不同的 key 但是计算出来的的所有结果都一样，这个就是误判率。

然后我们规定几个内容，首先就是布隆过滤器的大小有 m bits，我们设计了 k 个 hash 函数，同时我们大概总共可能会插入 n 个元素进行重复性判断。

我们假设设计的哈希函数载 m 中分布均匀，不存在偏袒那一块区域。

那么对于一个特定位来说，插入一个函数哈希值的时候没有被置为 1 的概率是

那么 k 个哈希函数都没有计算到其内容概率是

加入 n 个元素就是：

这里因为编辑原因加了两个括号。

最后就是我们出现 k 个元素都冲突的情况:

对上述化简之后得到。

而：

根据上边两个式子，我们就可以根据，我们想要的误判率和我们大概需要判断的数据量来估算我们布隆过滤器需要多少位和需要设计多少哈希函数了。

明白上述指标之后，一些布隆过滤器的除开哈希的计算函数都可以看明白了，后边如果有时间就上代码实现一个。当然会参考一些别人设计的结构。