布隆过滤器 (Bloom Filter)：用于超大数据量时检索一个元素是否存在

一时失言乱红尘 2022-11-27 00:49 26阅读 0赞

相信大家在开发过程中，经常会遇到**判断一个字符串（或其他类型的变量值）是否已经出现过**的需求，这个时候一般使用`HashMap`可以解决，先将出现过的字符串存于HashMap对象的keySet中，下次只要判断HashMap对象的keySet是否含有该字符串，就能知道是否其已经出现过。

但是，当我们HashMap存放的数据越多，查询速度就会越慢，而且占用内存也会越大。  
为什么查询速度会变慢呢？  
**知道HashMap底层原理的就不难想到，key的hashcode分布不均匀，可能很多key的hashcode被分配到同一个位置的链表中，就算jdk1.8之后引入红黑树，当数据很多的时候，对树进行遍历的速度也不会很理想。**

# 布隆过滤器 #

这种情况下，布隆过滤器就可以上场了：`占用内存非常小，查询速度快，但是存在很低的误判率`。  
它的原理其实很简单：如下图，

1.  我们创建一个长度为m的bit数组即位数组（bit占用内存较小），初设值为0；
2.  设计k个散列函数即hash函数；
3.  通过散列函数将字符串映射到0至n-1的k个数值；
4.  将这个k个数值作为索引，**如果bit数组在这个k个索引位置上的值都为1的话，则该字符串已经出现过，反之，则未出现过**；
5.  最后，更新bit数组，将bit数组对应的k个索引位置上将其修改为1。  
    ![在这里插入图片描述][20200812205853150.png_pic_center]

# 误判率 #

布隆过滤器的误判率是指，当一个元素没有出现过时，会存在一定的概率将其误判为已经出现过。  
（以下摘自维基百科）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70_pic_center]

# java实现 #

import java.io.Serializable;
    import java.util.BitSet;
    
    public class BloomFilter implements Serializable{ 
    	 private static final int BIT_SIZE = 2 << 28 ;//二进制向量的位数，相当于能存储1000万条url左右，误报率为千万分之一
    	    private static final int[] seeds = new int[]{ 3, 5, 7, 11, 13, 31, 37, 61};//用于生成信息指纹的8个随机数，最好选取质数
    
    	    private BitSet bits = new BitSet(BIT_SIZE);
    	    private Hash[] func = new Hash[seeds.length];//用于存储8个随机哈希值对象
    
    	    public BloomFilter(){ 
    	        for(int i = 0; i < seeds.length; i++){ 
    	            func[i] = new Hash(BIT_SIZE, seeds[i]);
    	        }
    	    }
    
    	    /** * 像过滤器中添加字符串 */
    	    public void addValue(String value)  
    	    {   
    	        //将字符串value哈希为8个或多个整数，然后在这些整数的bit上变为1
    	        if(value != null){ 
    	            for(Hash f : func) 
    	                bits.set(f.hash(value), true); 
    	        }
    
    	    }  
    
    	    /** * 判断字符串是否包含在布隆过滤器中 */
    	    public boolean contains(String value)  
    	    {   
    	        if(value == null) 
    	            return false;  
    
    	        boolean ret = true;  
    
    	        //将要比较的字符串重新以上述方法计算hash值，再与布隆过滤器比对
    	        for(Hash f : func)
    	            ret = ret && bits.get(f.hash(value));  
    	        return ret;  
    	    }  
    
    	    /** * 随机哈希值对象 */
    
    	    public static class Hash implements Serializable{ 
    	        private int size;//二进制向量数组大小
    	        private int seed;//随机数种子
    
    	        public Hash(int cap, int seed){ 
    	            this.size = cap;
    	            this.seed = seed;
    	        }
    
    	        /** * 计算哈希值(也可以选用别的恰当的哈希函数) */
    	        public int hash(String value){ 
    	            int result = 0;
    	            int len = value.length();
    	            for(int i = 0; i < len; i++){ 
    	                result = seed * result + value.charAt(i);
    	            }
    
    	            return (size - 1) & result;
    	        }
    	    }
    }

如果是想对字符串以外的变量值使用，那么只要先将其转化为字符串即可。

[20200812205853150.png_pic_center]: /images/20221124/55f3a07d923d46e794b49595619a7d63.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/e305689c51c542389583700e348c0932.png