介绍
1. 引言
我们知道检查一个元素是否在某一个集合中，使用HashSet是比较好的选择，因为在不发生Hash碰撞的情况下它的时间复杂度为常数级别，但是在数据量比较大的情况下，使用HashSet将会占用大量的内存空间。举个例子，长城防火墙有100亿个需要屏蔽的网址，来自计算机的每一次请求都要经过防火墙的过滤判断请求URL是否在黑名单中，如果我们使用HashSet来实现过滤的话，我们假设每个URL的大小为64B，那么100亿个就至少需要大约640GB的内存空间，这显然是不符合实际情况的。另一种解决方案是我们可以将URL存入关系型数据库，每次计算机发起请求我们对数据库进行exits查询，然而这种方案适用于并发量比较小的情况，若并发量较大，那么我们就需要对数据库进行集群。
以上俩种方案都有一定的局限性，为了解决大数据量检查问题，布隆过滤器就粉墨登场了。
2. 原理
先来简单了解一下布隆过滤器，我们可以把它看做一个会产生误判并且占用空间极少的HashSet。它的结构是一个Bit数组（数组中每个位置只占用一个bit，每个bit位有0和1两种状态）和一系列Hash函数的集合，我们将输入域通过上述一系列Hash函数进行Hash运算得到n个key值，将这n个值对数组的长度进行取余，然后将bit数组中对应的位置bit位设为1。在数组足够大，hash碰撞足够小的情况下，每个输入域都会在数组中不同的位置将其bit位置为1，我们把集合中所有的元素都按照这个方式来一遍的话一个布隆过滤器就生成好了。
那么如何判断一个元素是否在布隆过滤器中呢，原理和生成布隆过滤器的过程差不多，我们将要判断的值通过布隆过滤器的n个Hash函数计算出n个值，对数组长度取余得到bit数组中n个位置，接下来判断这n个位置的bit位是否都为1，若都为1，则说明该元素在集合中，若有一个为0，则该元素肯定不在集合中。
-
可能在
image.png
-
一定不在
image.png
3. 误判
了解了布隆过滤器的生成过程，相信大家已经看出来了，这样会产生一定的误判，假如输入对象不再集合中，而由于元素过多并且bit数组过小导致数组中的大部分位置bit位都为1，那么有可能会误判该元素在集合中。但是如果输入对象本就在集合中，那么数组中的bit位肯定都为1，布隆过滤器是一定不会产生误判的，这就是所谓的“宁可错杀三千，绝不放过一个”。
对于已经发现的误判元素，我们可以把他放入HashSet中，在经过布隆过滤器之前先行判断一下，这部分元素较少不会占用多少内存，也在一定程度解决了布隆过滤器的误判问题。
-
可能在(误判)
image.png
网友评论