本文主要是介绍一个用于白名单服务的布隆过滤器(bloom filter)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
bloom filter这种数据结构用于判断一个元素是否在集合内，当然，这种功能也可以由HashMap来实现。bloom filter与HashMap的区别在于，HashMap会储存代表这个元素的key自身(如key为"IKnow7"，那么HashMap将存储"IKnow7"这12个字节(java)，其实还需要包括引用大小，但java中相同string只存一份)，而bloom filter在底层只会使用几个bit来代表这个元素。在速度上，bloom filter对比与HashMap相差不大，底层同样是hash+随机访问。由于bloom filter对空间节省的特性，bloom filter适合判断一个元素是否在海量数据集合中。
bloom filter的一些概念
bloom filter并非十全十美。bloom filter在添加元素时，会将对象hash到底层位图数组的k个位上，对这些位，bloom filter会将其值设为1。由于hash函数特性以及位图数组长度有限，不同的对象可能在某些位上有重叠。bloom filter在检查元素是否存在时，会检查该对象所对应的k个位是否为1，如果全部都为1表示存在，这里就出现问题了，这些位上的1未必是该元素之前设置的，有可能是别的元素所设置的，所以会造成一些误判，即原本不在bloom filter中的一些元素也被判别在bloom filter中。bloom filter的这种误判被称为"积极的误判"，即存在的元素的一定会通过，不存在的元素也有可能通过，而不会造成对存在的元素结果为否的判定。
可以简单猜测，误判的概率与hash的选择、位图数组的大小、当前元素的数量以及K(映射位的个数)有关。一般来说，hash值越平均、位图数组越大、元素数量越少那么误判的概率就越低。
这是一个大牛写的关于bloom filter设计与误判率的理论分析，大伙可以去看看： http://www.cnblogs.com/allensun/archive/2011/02/16/1956532.html。
bloom filter在web上的应用
在web应用中我们经常需要使用白名单来过滤一些请求，用以避免一些无效的数据库访问或者恶意攻击。对于允许一些误判率且存在海量数据的白名单来说，使用bloom filter是不二的选择。
使用bloom filter实现一个支持增量请求的白名单
白名单通常是需要更新的，更新的方式一般有全量和增量更新。全量不必说，重新定义个bloom filter将当前所有数据放入其中即可。增量更新的话，一般会提供一段时间内新增和删除的数据，所以需要在白名单中将数据进行合并，该添加的添加，该删除的删除。
可是...... 原生的bloom filter并不支持元素的删除操作，因为某一位可能为多个元素所用。一种不切实际的想法是为bloom filter的每一位设置一个引用计数，每删除一个元素减1。
这篇关于一个用于白名单服务的布隆过滤器(bloom filter)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
