数据结构之布隆过滤器

桃扇骨 2023-02-26 05:19 2阅读 0赞

# 布隆过滤器 #

如果要经常判断某个元素是否存在，你会怎么做？很容易想到使用哈希表（HashSet、HashMap），将元素作为key去查找。时间复杂度为O(1)，但是空间利用率不高，需要占用比较多的内存资源。

如果需要编写一个网络爬虫去爬10亿个网站数据，为了避免爬到重复的网站，如何判断某个网站是否爬过？很显然，HashSet、HashMap并不是非常好的选择。

是否存在时间复杂度低、占用内存较少的方案？就是下面要学习的布隆过滤器。

## 布隆过滤器（Bloom Filter） ##

布隆过滤器（Bloom Filter）在1970年由布隆提出，它是一个空间效率高的概率型数据结构，可以用来告诉你：一个元素一定不存在或者可能存在。

它实质上是由一个很长的二进制向量和一系列随机映射函数（Hash函数）组成。

优点：空间效率和查询时间都远远超过一般的算法。

缺点：有一定的误判率、删除困难。

应用场景：网页黑名单系统、垃圾邮件过滤系统、爬虫的网址判重系统、解决缓存穿透问题。

开源实现：google的guava中com.google.common.hash.BloomFilter。

## 布隆过滤器的原理 ##

假设布隆过滤器由20位二进制、3个哈希函数组成，每个元素经过哈希函数处理都能生成一个索引位置。

*  添加元素（put）：将每一个哈希函数生成的索引位置都设为1
 *  查询元素是否存在（contains）：如果有一个哈希函数生成的索引位置不为1，就代表不存在（100%准确），如果每一个哈希函数生成的索引位置都为1，就代表可能存在（存在一定的误判率）。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70]

添加、查询的时间复杂度都是：O(k)，空间复杂度是：O(m)（其中k是哈希函数的个数，m是二进制位的个数）。

## 布隆过滤器的误判率 ##

误判率p受3个因素影响：二进制位的个数m、哈希函数的个数k、数据规模n。

已知误判率p、数据规模n，求二进制位的个数m、哈希函数的个数k，可以使用下面的公式：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 1]

## 布隆过滤器的实现 ##

### 数据结构 ###

private long[] bits; // 二进制位
    
        private int bitSize; // 二进制位数
    
        private int hashSize; // 哈希函数的个数
    
        /** * @param n 数据规模 * @param p 误判率 */
        public BloomFilter(int n, double p) { 
            if (n <= 0 || p <= 0 || p >= 1) { 
                throw new IllegalArgumentException("wrong n or p");
            }
    
            double ln2 = Math.log(2); // ln2
    
            bitSize = (int) (- (n * Math.log(p)) / ln2 / ln2); // 二进制位的个数
    
            // (bitSize + Long.SIZE - 1) / Long.SIZE = ceil(bitSize / Long.SIZE)
            bits = new long[(bitSize + Long.SIZE - 1) / Long.SIZE]; // 初始化二进制位
    
            hashSize = (int) (bitSize * ln2 / n); // 哈希函数的个数
        }

### put ###

/** * 添加一个value * * @param value * @return */
        public boolean put(T value) { 
            nullCheck(value);
    
            int hash1 = value.hashCode();
            int hash2 = value.hashCode() >> 16;
    
            boolean result = false;
            for (int i = 1; i <= hashSize; i++) { 
                int combinedHash = hash1 + (i * hash2);
                if (combinedHash < 0) { 
                    combinedHash = ~combinedHash;
                }
    
                int index = combinedHash % bitSize;
                if (set(index)) { 
                    result = true;
                }
            }
    
            return result;
        }
    
        public boolean set(int index) { 
    
            int bitsIndex = index / Long.SIZE; // 定位到bits数组中long元素的索引
    
            long value = bits[bitsIndex]; // 定位到long元素
    
            int mask = 1 << (index % Long.SIZE);
    
            long bit = value & mask; // 取出第[index % Long.SIZE]位
    
            bits[bitsIndex] = value | mask; // 将第[index % Long.SIZE]位设置为1
    
            return bit == 0;
        }
    
        private void nullCheck(T value) { 
            if (value == null) { 
                throw new IllegalArgumentException("Value must not be null.");
            }
        }

### contains ###

/** * 判断value是否存在，如果返回false，表示一定不存在，如果返回true，表示可能存在 * * @param value * @return */
        public boolean contains(T value) { 
            nullCheck(value);
    
            int hash1 = value.hashCode();
            int hash2 = value.hashCode() >> 16;
    
            for (int i = 0; i < hashSize; i++) { 
                int combinedHash = hash1 + (i * hash2);
                if (combinedHash < 0) { 
                    combinedHash = ~combinedHash;
                }
    
                int index = combinedHash % bitSize;
                if (!get(index)) { 
                    // 只要有一个为0，则返回false
                    return false;
                }
            }
    
            return true;
        }
    
        private boolean get(int index) { 
            long value = bits[index / Long.SIZE]; // 定位到long元素
            int mask = 1 << (index % Long.SIZE);
            long bit = value & mask; // 取出第[index % Long.SIZE]位
            return bit != 0;
        }

更多精彩内容关注本人公众号：架构师升级之路  
![在这里插入图片描述][20200627175030665.jpg]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70]: /images/20230209/23fb164d3b3547df9050abfa0eacdff3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200714114644750.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMjI4MTI4NDk=,size_16,color_FFFFFF,t_70
[20200627175030665.jpg]: https://img-blog.csdnimg.cn/20200627175030665.jpg