你不知道的查找算法之布隆过滤器_模糊查询能用布隆过滤器嘛

目录

布隆过滤器简述

缘何要使用布隆过滤器

抛砖

引玉

布隆过滤器原理预热知识之哈希函数

布隆过滤器的核心原理

布隆过滤器特点

布隆过滤器本质

布隆过滤器使用条件

HBase读取数据之布隆过滤器

面试题之布隆过滤器

具体的实现过程

---

布隆过滤器简述

• 布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。（百度百科）
• 简单来说，布隆过滤器是一种算法，有点类似hashmap，可以用来判断某个元素（key）是否存在于集合当中。优点是节省空间（因为它不需要存储key的值）和查询效率高；缺点是有一定的误判（主要原因是哈希碰撞）

缘何要使用布隆过滤器

抛砖

先来看一下下面几个例子

• 字处理软件中，需要检查一个英语单词是否拼写正确
• 在 FBI，一个嫌疑人的名字是否已经在嫌疑名单上
• 在网络爬虫里，一个网址是否被访问过
• yahoo, gmail等邮箱垃圾邮件过滤功能

这几个例子有一个共同的特点： 如何判断一个元素是否存在一个集合中？

最直接也最容易想到的是将集合中全部的元素存在计算机中，遇到一个新元素时，将它和集合中的元素直接比较即可。

但大家一般都不会将这个元素在集合当中进行轮询判断是否存在，而且一般随着实际业务的需要，容器中的元素也越来越多，有时候甚至是嵌套集合，这样轮询就显得异常的笨拙了，

不仅查询效率低下，内存占用也是非常的高。

于是出现了相应的数据结构和算法相结合的方法，来解决查询和存储问题。

比如：

数据存储在：

• 数组  【通过索引定位元素非常快】
• 链表
• 树、平衡二叉树
• Map (红黑树)
• 哈希表

算法：

快排、冒泡派、二分查找等等。。。。

但你有没有想到当存储的数据达到百TB、PB级别时，这个时候常规的数据结构的问题就凸显出来了。

引玉

数组、链表、树等数据结构会存储元素的内容，一旦数据量过大，消耗的内存也会呈现线性增长，最终达到瓶颈；存储空间的节省和查询效率的提高就很难很难保证了。

这个时候，布隆过滤器（Bloom Filter）就应运而生了。

布隆过滤器原理预热知识之哈希函数

哈希函数本质就是个function，它可以将任意大小的数据转换成特定大小的数据的函数，转换后的数据称为哈希值或哈希编码。

可以明显的看到，原始数据经过哈希函数的映射后称为了一个个的哈希编码，数据得到压缩。哈希函数是实现哈希表和布隆过滤器的基础。

布隆过滤器的核心原理

以上图为例，假设集合中有三个元素x,y,z ，则存在三个哈希函数。首先会将位数组进行初始化，里面每个数据都是二进制的bit，初始值都设置为0；

而对于集合中的每一个元素，将依次通过三个哈希函数进行计算并映射，每次映射都会产生一个哈希值，这个值对应位数组上面的一个点，然后将位数组对应的位置标记为1

如果我们要查询w元素是否在集合当中，他将通过3个哈希函数将w映射成位阵列中的三个点，只需要查看这三个点对应的值是0还是1

但凡存在一个0.则这个集合中一定不存在w，如果全是1，则这个集合极有可能存在w元素

为什么说是w元素呢，我们都知道哈希值，是有可能重复的，这个元素可能是个字符串，不同字符串的哈希值是可能相同的，就会产生哈希碰撞

 

简言之，在初始化这个位阵数组时，我们就把它看做是一个数组，里面的值都是一个0或者1个1。初始时都为0。添加元素时，元素通过若干个哈希函数计算出n个值，映射为

位阵数组上某个点（可以理解为数组的索引），并且把这个点的位置设置为1

在查找元素时，统一使用若干个哈希函数计算出值（索引），去这个位阵数组相应的位置上找值，如果至少存在一个0，则一定不存在这个元素，如果全是1，则极有可能存在这个元素。

布隆过滤器特点

• 巴顿.布隆于一九七零年提出
• 一个很长的二进制向量 （位数组）   【标识】----->  2进制的bit
• 一系列随机函数 (哈希)
• 空间效率和查询效率高
• 有一定的误判率（哈希表是精确匹配）

布隆过滤器本质

本质上布隆过滤器是一种数据结构（位阵数组）比较巧妙的概率型数据结构（probabilistic data structure），特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”。  布隆过滤器可以用于检索一个元素是否在一个集合中。

优点：占用空间小，查询快 
缺点：有误判，不可能100%准确， 删除困难。

布隆过滤器使用条件

1）数据量巨大

2）可以容忍一定量的失误

3）空间比较严格（不管是存储空间还是内存运算）

HBase读取数据之布隆过滤器

之前我们讲过Hbase的读取数据，我们讲在客户端找hbase查询数据时，通常是向regionrerver查询数据，而regionserver先从自己的数据块缓存blockCache和内存memoryStore中找，找不到的话会找hdfs要数据。

而我们知道hfile实质上是储存在hdfs的cf列族文件夹下的，而这个文件夹下有很多很多很多个，regionserver不可能在cf文件夹下遍历每个hfile，又在里面查找某个键，这无疑很耗费内存运算资源，很容易造成内存溢出，影响效率。而它就是使用的布隆过滤器。先通过n个哈希算法计算你要查找的rowkey的值，并映射到hfile上的位列数组的某些点，但凡存在一个0，则一定没有这行数据，如果全是1，则极有可能存在rowkey这行数据。

一般hfile中存有这个位列数组。这使得我们可以快速从大量的hfile中查询出可能存在我们需要数据的文件，尽管可能存在误差，但这是我们所允许的误差，而且也大大提高了查询效率。

面试题之布隆过滤器

不安全网页的黑名单包含 100亿个黑名单网页， 每个网页的URL最多占64字节，现在想要实现一种网页过滤系统，可以根据网页的URL判断该网页是否在黑名单上， 请设计该系统。 要求该系统允许有万分之一一下的判断失误率，并且使用的额外控件不要超过30G。

具体的实现过程

我们准备k个哈希函数， 这些哈希函数都很优秀，且彼此独立，给定一个m， 输出域 >= m 。

再准备一个长度为 m 的 bitarray  用来存储信息。里面每一个位置表示一个 bit ，  0值代表白  1值 代表黑。

对于每一个黑名单中的URL 都经过下列的流程， 经过k个哈希函数后， 各自对m取模 ，得到 k 个值， 映射到 bitarray 上， 将对应的位置涂黑。 也就是说， 对应位置值为1 时 不变， 值为0， 则变成1。

在将所有的URL都处理完毕后， bitarray就变成了如下的样子：

其中大部分位置，都被涂黑，也有一部分的位置仍为白。

至此， 一个布隆过滤器就算是设置好了。 那么如何使用来检验一个新的URL是否在黑名单内呢。

我们只要再次经过 k 个 hash函数并且取模， 这样得到的 k个值  与 bitarray进行对比， 只要存在一个值 i  使得 bitarray[i] 这个位置是白色， 那么就可以知道 该 URL 必然不在黑名单之内。但是，绝对不会漏掉黑名单内的URL， 因为如果一个URL在黑名单内了， 那么bitarray中对应的k个位置一定是被涂黑的。

但是， 如果k个值对应的区域都是黑色，也不能说明，URL一定就在这个黑名单之内。因为如果这个bitarray 长度过小，同时黑名单内的URL数量又很多， 势必导致这个bitarray 的绝大部分都是已经被涂黑的。 这样一个URL进来，很可能会被误判为是在黑名单内。故总结一下： 会误判，但是绝对不会漏掉一个！宁可错杀一千，不会放过一个！

部分内容借鉴网上资料，更多文章、面试笔记尽在微信公众号：Hadoop大数据开发