布隆过滤器

r囧r小猫 2022-07-14 13:15 258阅读 0赞

> **布隆过滤器\[1\]**（Bloom Filter）是由布隆在1970年提出的。它实际上是由一个很长的二进制向量和一系列随机映射函数组成，布隆过滤器可以用于检索一个元素是否在一个集合中，优点是空间效率和查询时间都远超一般算法，缺点是有一定的误识别率（即布隆过滤器报告某一元素在集合中，实际上该元素不在集合中）和删除困难，但是没有识别错误的情形，如果某个元素确实没有在该集合中，那么Bloom Filter是不会>报告该元素存在于集合中的，所以不会漏报

我们通过下面例子来说明其工作原理：  
假定我们要存储1亿个网址，假设每个网址需要16个字节存储,  
1. 我们先建立16亿二进制常量（Bit Array），并将这16亿位全部置成0;  
2. 对于每个网址，我们用8个哈希函数产生8个信息指纹（其实就是8个整数）;  
3. 然后将这8个信息指纹映射到1~16亿中的8个自然数中记作（g1，g2，….,g8）将这8个位置的二进制数置成1；  
4. 然后每个这样的网址都进行一遍这样的处理。  
最后针对这些网址的布隆过滤器就建成了。

现在我们看看布隆过滤器如何进行查找该网址是否存在与布隆过滤器中，  
(1).首先得到要查找的网址；  
(2).同样用这8个哈希函数产生8个信息指纹；  
(3).然后根据这8个信息指纹得到这1~16亿中的8个位置；  
(4).如果这8个位置上全部为1，则该网址已经存在；  
(5).如果有一个为0，则表明该网址不存在；  
下面我们来看Bloom Filter过滤器的java实现：

package com.xkang.common;
    
    import java.util.BitSet;
    
    public class BloomFilter {
    
        private static int DEFAULT_SIZE = 2<<24;//2G大小
        private static int basicIndex = DEFAULT_SIZE-1;
        private static final int[] seeds = new int[]{
       7,11,13,31,37,61};
        //位集，创建一种特殊类型的数组来保存位值
        private BitSet bits = new BitSet(DEFAULT_SIZE);
    
    
        /** * hash函数的主要功能是返回一个0~basicIndex的数 * @param value * @param seed * @return */
        public int hash(String value,int seed){
            int result = 0;
            int len = value.length();
            for(int i=0;i<len;i++){
                //hash映射
                result = seed*result+value.charAt(i);
            }
            //将hash出来的散列值映射到0~basicIndex中的某一个数上
            return basicIndex&result;
    
        }
        //将url添加到布隆过滤器中
        public void add(String value){
    
            if(exist(value)){
                System.out.println("已经存在布隆过滤器中了");
                return;
            }
            for(int i=0;i<seeds.length;i++){
    
                int index = hash(value,seeds[i]);
                //将对应位置上的数置成true；
                bits.set(index, true);
            }
        }
        //判断是否url存在布隆过滤器中；
        public boolean exist(String value) {
            if(value ==null){
    
                return false;
            }
            boolean flag=true;
            for(int i=0;i<seeds.length;i++){
    
                int index = hash(value,seeds[i]);
                flag = flag&&bits.get(index);
            }
            return flag;
        }
        /* *从布隆过滤器中删除制定url *这是布隆过滤器的一个缺点，因为 你不能保证是否有其他url也是用的这个位置，所以当你 *将当前url所对应的位置置0时，可能会导致其他本应该存在的url也被你删除 */
        public void delete(String value){
    
            if(value == null||!exist(value)){
                return ;
            }
            for(int i=0;i<seeds.length;i++){
                int index = hash(value,seeds[i]);
                bits.set(index, false);
            }
    
        }
    
    }