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。一种可行的做法是，另外使用一个map来保存已删除的元素，在判断元素是否存在时先判断在该deletemap中是否存在，如果存在，直接false。如果不存在，再通过bloom filter进行判断。在新添加元素时，如果deletemap中存在，删除该deletemap中的该元素，再添加到bloom filter中。在实际应用中，使用白名单的场景需要删除的元素一般是较少的，所以这种方式从效率是可行的。这种方式存在一个问题，当deletemap中元素过多时，势必会造成bloom filter的误判率上升，因为某些原本被删除元素设置为1的位并没有被归0。该问题的解决措施是，当deletemap的容量到达的一个界线时，使用全量同步更新该bloom filter。

白名单bloom filter的实现

这类构件复用性很强，可以轻松的集成到现有的代码之上。下面直接贴出来：

public class BloomFilter
  
    implements Serializable {
    
    private static final long serialVersionUID = 3507830443935243576L;
    private long timestamp;//用于时间戳更新机制
    private HashMap
   
     deleteMap ; //储存已删除元素 private BitSet bitset;//位图存储 private int bitSetSize; // expected (maximum) number of elements to be added private int expectedNumberOfFilterElements; // number of elements actually added to the Bloom filter private int numberOfAddedElements; private int k; //每一个元素对应k个位 // encoding used for storing hash values as strings static Charset charset = Charset.forName("UTF-8"); // 
    MD5 gives good enough accuracy in most circumstances. // Change to SHA1 if it's needed static String hashName = "MD5"; static final MessageDigest digestFunction; static { // The digest method is reused between instances to provide higher entropy. MessageDigest tmp; try { tmp = java.security.MessageDigest.getInstance(hashName); } catch (NoSuchAlgorithmException e) { tmp = null; } digestFunction = tmp; } /** * Constructs an empty Bloom filter. * * @param bitSetSize defines how many bits should be used for the filter. * @param expectedNumberOfFilterElements defines the maximum * number of elements the filter is expected to contain. */ public BloomFilter(int bitSetSize, int expectedNumberOfFilterElements) { this.expectedNumberOfFilterElements = expectedNumberOfFilterElements; this.k = (int) Math.round( (bitSetSize / expectedNumberOfFilterElements) * Math.log(2.0)); bitset = new BitSet(bitSetSize); deleteMap = new HashMap
    
     (); this.bitSetSize = bitSetSize; numberOfAddedElements = 0; } /** * Generates a digest based on the contents

一个用于白名单服务的布隆过滤器(bloom filter)(一)

bloom filter的一些概念

bloom filter在web上的应用

使用bloom filter实现一个支持增量请求的白名单

白名单bloom filter的实现