布隆过滤器原理

如果说要存储 1 亿个网站的 URL，你会使用什么样的数据结构？

我们需要方便对应查找，因此 query 的时间复杂度不能过高，在正常的，我们经常接触的数据结构中，你可能会想到的是散列表、平衡二叉树、跳表等数据结构。

我们来看看散列表，时间的话平均时间复杂度是 O(1)，注意我这里说的是平均时间复杂度，哈希是会存在冲突的情况，这是你就要对比两个字符串上面的每个字符，完全符合条件才行，不符合还和继续找，继续对比；另外就是散列的存储空间，假如一个 URL 是 64 Bytes，那么 1 亿个 URL 大概是 6GB 的样子，但是对于散列来说的话这还没完，如果要尽量减少冲突的话，散列的实际 size 要比实际存储的数据的 size 要大，散列是这样，其他的数据结构，二叉树，跳表也都会有一些额外的开销，这些额外的开销都会导致实际存储当中不可避免的资源消耗。

上面讲到的散列表其实就是数组，我们之前提到的位图也是数组，但是我们说到了字符串如何存储的问题，这时我们就需要借助哈希函数了，哈希函数会根据输入参数的特性返回一个数组 index，我们直接去这个 index 上查看即可。

但是结合实际情况，我们有必要直接将整个 URL 存储起来吗？和位图的功能类似，布隆过滤器也仅仅是需要判断这个 URL 是不是在内存中，我们需要的答案是 “是” 或者 “不是”。

但是这里有个问题，只要是哈希函数都会有冲突的问题，假如说我们之前标记了一个 URL 存在，但是这个时候冲突产生了，一个本身不存在的 URL 我们通过哈希函数发现其存在，这个时候就会产生误判，但是你要知道的是，这个误判也只是单向的，对于不同的 URL，哈希函数可能返回相同的值，但是如果说返回的这个值是不存在 的话，那么表示一定是不存在的，如果是存在的话，可能是存在，因为这时有可能是相同哈希值的 URL 存在，并不是当前的 URL 存在，这是就是我们说的误判的情况，简而言之就是 “false always false，true maybe true”。