浅谈布隆过滤器

矫情吗；* 2023-07-14 12:58 132阅读 0赞

一、布隆过滤器是什么  
布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。

二、布隆过滤器的基本思想  
通过一种叫作散列表（又叫哈希表，Hash table）的数据结构。它可以通过一个Hash函数将一个元素映射成一个位阵列（Bit array）中的一个点。这样一来，我们只要看看这个点是不是1就可以知道集合中有没有它了

三、布隆过滤器如何解决哈希冲突的  
解决方法就是使用多个Hash函数，如果它们有一个说元素不在集合中，那肯定就不在。如果它们都说在，虽然也有一定可能性它们在说谎，不过直觉上判断这种事情的概率是比较低的。

四、布隆过滤器的优缺点  
优点：  
1.布隆过滤器的存储空间和插入/查询时间都是常数  
2.Hash函数相互之间没有关系，方便由硬件并行实现  
3.布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势  
4.布隆过滤器可以表示全集，其它任何数据结构都不能  
缺点:  
1.存在一定的误算率，随着存入的元素数量增加，误算率随之增加  
（常见的补救办法是建立一个小的白名单，存储那些可能被误判的元素。但是如果元素数量太少，则使用散列表足矣）  
2.一般情况下不能从布隆过滤器中删除元素  
首先我们必须保证删除的元素的确在布隆过滤器里面. 这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。这就导致删除元素需要很高的成本。

五、布隆过滤器的应用场景  
1.网页URL的去重  
2.垃圾邮件的判别  
3.集合重复元素的判别  
4.查询加速（比如基于key-value的存储系统）等

/** * 描述：TODO(用一句话描述该文件做什么) */
    package com.zbq.utils;
    
    import java.io.BufferedReader;
    import java.io.File;
    import java.io.FileInputStream;
    import java.io.IOException;
    import java.io.InputStream;
    import java.io.InputStreamReader;
    import java.util.BitSet;
    
    /** * 类名： BloomFilterTest * 包名： com.utilTest * 描述： 布隆过滤器，传统的布隆过滤器不支持从集合中删除成员 */
    public class BloomFilterTest { 
        //DEFAULT_SIZE为2的29次方，即此处的左移28位
        private static final int DEFAULT_SIZE = 2<<28;
        /* * 不同哈希函数的种子，一般取质数 * seeds数组共有8个值，则代表采用8种不同的哈希函数 */
        private int[] seeds = new int[]{ 3, 5, 7, 11, 13, 31, 37, 61};
        /* * 初始化一个给定大小的位集 * BitSet实际是由“二进制位”构成的一个Vector。 * 假如希望高效率地保存大量“开－关”信息，就应使用BitSet. */
        private BitSet bitSets = new BitSet(DEFAULT_SIZE);
        //构建hash函数对象
        private SimpleHash[] hashFuns = new SimpleHash[seeds.length];
        //布隆过滤器配置文件存放路径
        private String path = "";
    
        public BloomFilterTest(String path){ 
            /** * 给出所有的hash值，共计seeds.length个hash值。共8位。 * 通过调用SimpleHash.hash(),可以得到根据8种hash函数计算得出hash值。 * 传入DEFAULT_SIZE(最终字符串的长度），seeds[i](一个指定的质数)即可得到需要的那个hash值的位置。 */
            for(int i=0; i<seeds.length; i++){ 
                hashFuns[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]);
            }
            //配置文件路径地址
            this.path = path;
        }
        /** * * 方法名：add * 描述：将给定的字符串标记到bitSets中，即设置字符串的8个函数值的位置为1 * @param value */
        public synchronized void add(String value){ 
            for(SimpleHash hashFun : hashFuns){ 
                bitSets.set(hashFun.hash(value), true);
            }
        }
        /** * * 方法名：isExit * 描述：判断给定的字符串是否已经存在在bloofilter中，如果存在返回true，不存在返回false * @param value * @return */
        public synchronized boolean isExit(String value){ 
            //判断传入的值是否为null
            if(null == value){ 
                return false;
            }
    
            for(SimpleHash hashFun : hashFuns){ 
                if(!bitSets.get(hashFun.hash(value))){ 
                    //如果判断8个hash函数值中有一个位置不存在即可判断为不存在Bloofilter中
                    return false;
                }
            }
            return true;
        }
    
        /** * * 方法名：init * 描述：读取配置文件 */
        public void init(){ 
            File file = new File(path);
            FileInputStream in = null;
            try { 
                in = new FileInputStream(file);
                long lt = System.currentTimeMillis();
                read(in);
                System.out.println(System.currentTimeMillis()-lt);
                System.out.println(Runtime.getRuntime().totalMemory());
            }catch(Exception e){ 
                e.printStackTrace();
            }finally{ 
                try { 
                    if(in!=null){ 
                        in.close();
                        in = null;
                    }
                } catch (IOException e) { 
                    // TODO Auto-generated catch block
                    e.printStackTrace();
                }
            }
        }
    
        /** * * 方法名：read * 描述：根据传入的流，初始化bloomfilter * @param in */
        private void read(InputStream in){ 
            if(null == in){     //如果in为null，则返回
                return;
            }
    
            int i = 0;
            InputStreamReader reader = null;
    
            try { 
                //创建输入流
                reader = new InputStreamReader(in, "UTF-8");
                BufferedReader buffReader = new BufferedReader(reader, 512);
                String theWord = null;
                do { 
                    i++;
                    theWord = buffReader.readLine();
                    //如果theWord不为null和空，则加入Bloomfilter中
                    if(theWord!=null && !theWord.trim().equals("")){ 
                        add(theWord);
                    }
                    if(i%10000 == 0){ 
                        System.out.println(i);
                    }
    
                } while (theWord != null);
    
            } catch (IOException e){ 
                e.printStackTrace();
            } finally{ 
                //关闭流
                try { 
                    if(reader != null){ 
                        reader.close();
                        reader = null;
                    }
                    if(in != null){ 
                        in.close();
                        in = null;
                    }
                } catch (IOException e) { 
                    // TODO: handle exception
                    e.printStackTrace();
                }
            }
        }
    
        /** * 方法名：main * 描述：TODO(这里用一句话描述这个方法的作用) * @param args */
        public static void main(String[] args) { 
            // TODO Auto-generated method stub
            BloomFilterTest bloomFilterTest = new BloomFilterTest("f:/fetchedurls.txt");
            bloomFilterTest.init();
    
            System.out.println(bloomFilterTest.isExit("http://www.plating.org/news_info.asp?pid=28&id=2857"));
        }
    
        public static class SimpleHash { 
            /* * cap为DEFAULT_SIZE，即用于结果的最大字符串的值 * seed为计算hash值的一个key值，具体对应上文中的seeds数组 */
            private int cap;
            private int seed;
            /** * * 构造函数 * @param cap * @param seed */
            public SimpleHash(int cap, int seed){ 
                this.cap = cap;
                this.seed = seed;
            }
            /** * * 方法名：hash * 描述：计算hash的函数，用户可以选择其他更好的hash函数 * @param value * @return */
            public int hash(String value){ 
                int result = 0;
                int length = value.length();
                for(int i=0; i<length; i++){ 
                    result = seed*result + value.charAt(i);
                }
                return (cap-1) & result;
            }
        }
    }