位图&布隆过滤器(附面试题)

太过爱你忘了你带给我的痛 2024-02-05 11:12 18阅读 0赞

#### 文章目录 ####

**目录**

文章目录

前言

一 . 位图

1.1 面试题

1.2 位图概念

1.3 位图的实现

1.4 位图的应用

二 . 布隆过滤器

2.1 布隆过滤器提出

2.2布隆过滤器概念

2.3 布隆过滤器的查找

2.4 实现

2.5 布隆过滤器删除

2.6 布隆过滤器优点

2.7 布隆过滤器缺陷

2.8 布隆过滤器使用场景

三 . 海量数据面试题

1. 哈希切割

2. 位图应用

3.布隆过滤器

总结

--------------------

## 前言 ##

大家好,今天给大家带来两种数据结构无位图&布隆过滤器

--------------------

## 一 . 位图 ##

学到这里,林林总总也是学了很多的数据结构了,那么位图是一种怎样的数据结构呢?我们由一道面试题来引出

### **1.1 面试题** ###

给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数 中。【腾讯

回顾以往学过的数据结构,最简单想到的或许就是直接遍历 时间复杂度为![o(n)][o_n]

或者先排序![o(nlogn)][o_nlogn]再进行一次二分查找![o(logn)][o_logn]

来总结一下 **遍历 ![o(n)][o_n]** **二分查找![o(nlogn)][o_nlogn]\+![o(logn)][o_logn]**

如果面试被问到类似的这种问题,上面两种回答绝对是挂了的,那么我们该用什么来解决这个问题?

在这里引出位图

数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以**使用一个二进制比 特位来代表数据是否存在的信息**，如果二进制比特位为1，代表存在，为0代表不存在。比如：

![7184453e10ea44709eeb3c816f400c3c.png][]

### 1.2 位图概念 ###

所谓位图，就是用每一位来存放某种状态，适用于海量数据，整数，数据无重复的场景。通常是用来判 断某个数据存不存在的。

如上例子，10个整数本应该存放需要40个字节，此时用位图只需要3个字节。

![9775e7abd20f45f6b02750c2fd532717.png][]

### 1.3 位图的实现 ###

主要就是三个方法的实现1.插入,2.判断数字是否存在,3.将对应的位置置为零

首先看插入

![212aa693bd7442dc9cb8b10e3bcfec5b.png][]

知道了索引就好办了,其它两个直接照抄即可,给出实现

/*
    * 位图
    * */
    public class MyBitSet {
        private byte[] elem;
        private int usedSize;
    
        public MyBitSet(){
            elem = new byte[1];
        }
    
        /**
         * @param n 比特数
         */
        public MyBitSet(int n){
            elem = new byte[n/8+1];
        }
    
        /**
         * 插入数据
         * @param val 以等价于 将数据的对应
         */
        public void set(int val){
            if(val < 0){
                throw new IndexOutOfBoundsException();
            }
            if(val/8+1 > elem.length){
                elem = Arrays.copyOf(elem, val / 8 + 1);
            }
            int arrayIndex = val/8;
            int bitIndex = val%8;
            elem[arrayIndex] |= (1<<bitIndex);
            usedSize++;
        }
    
        /**
         * 测试数字是否存在
         * @param val
         * @return
         */
        public boolean get(int val){
            if(val < 0){
                throw new IndexOutOfBoundsException();
            }
            if(val/8+1 > elem.length){
                return false;
            }
            int arrayIndex = val/8;
            int bitIndex = val%8;
            return (elem[arrayIndex] & (1 << bitIndex)) != 0;
        }
    
        /**
         * 将对应位置置为零
         * @param val
         * @return
         */
        public void reSet(int val){
            if(val < 0){
                throw new IndexOutOfBoundsException();
            }
            if(val/8+1 > elem.length){
                elem = Arrays.copyOf(elem, val / 8 + 1);
            }
            int arrayIndex = val/8;
            int bitIndex = val%8;
    
            elem[arrayIndex] &= ~(1<<bitIndex);
        }
    
        /**
         * 当前比特位有多少个1
         * @return
         */
        public int getUsedSize() {
            return this.usedSize;
        }
    
    }

### 1.4 位图的应用 ###

1. 快速查找某个数据是否在一个集合中(已实现)

2. 排序 + 去重(已实现)

3. 求两个集合的交集、并集等

假设我们有两个位图 A 和 B，分别表示集合 A 和集合 B。要求两个集合的交集，我们可以对位图 A 和位图 B 进行逻辑与操作，得到的结果位图即为两个集合的交集。要求两个集合的并集，我们可以对位图 A 和位图 B 进行逻辑或操作，得到的结果位图即为两个集合的并集。

![a3101a23279244c5821a1289f866163f.png][]

4. 操作系统中磁盘块标记

## 二 . 布隆过滤器 ##

### 2.1 布隆过滤器提出 ###

布隆过滤器（Bloom Filter）是一种空间效率高、**误判率低的概率型数据结构**，它可以用于判断一个元素是否在一个集合中。**布隆过滤器由一个位数组和多个哈希函数组成**。当一个元素被加入集合时，它会被哈希函数映射到位数组中的多个位置，将这些位置的值都设为1。查询一个元素是否在集合中时，将该元素经过哈希函数映射到位数组中的多个位置，如果这些位置的值都为1，则说明该元素**可能**在集合中，**否则一定不在**。由于哈希函数的随机性，布隆过滤器可能会出现误判，即一个不在集合中的元素被判定为在集合中。但误判率可以通过调整位数组大小和哈希函数个数来控制。

### 2.2布隆过滤器概念 ###

**布隆过滤器是**由布隆（Burton Howard Bloom）在1970年提出的 一种紧凑型的、比较巧妙的**概率型数据结构**，特点是高效地插入和查询，可以用来告诉你 “**某样东西一定不存在或者可能存在**”，它是用多个哈希函 数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。

![8b45ed19b8424be598f356343123e435.png][]

插入

![6c3fddf44b7948018a20ccf943cabf78.png][]

### 2.3 布隆过滤器的查找 ###

布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中，因此被映射到的位置的比特位一定为1。 所以可以按照以下方式进行查找：**分别计算每个哈希值对应的比特位置存储的是否为零，只要有一个为零， 代表该元素一定不在哈希表中，否则可能在哈希表中。**

**注意：布隆过滤器如果说某个元素不存在时，该元素一定不存在，如果该元素存在时，该元素可能存在，因 为有些哈希函数存在一定的误判。**

比如：在布隆过滤器中查找"alibaba"时，假设3个哈希函数计算的哈希值为：1、3、7，刚好和其他元素的比 特位重叠，此时布隆过滤器告诉该元素存在，但实该元素是不存在的。

### 2.4 实现 ###

/**
     * 简单hash函数
     */
    class simpleHash {
        private final int cap;
        private final int seed;
        public simpleHash(int cap,int seed){
            this.cap = cap;
            this.seed = seed;
        }
    
        public int hash(Object key) {
            int h;
            return (key == null) ? 0 : ((cap-1)*seed)*((h = key.hashCode()) ^ (h >>> 16));
        }
    }
    
    /**
     * 布隆过滤器
     */
    public class BloomFilter {
        private static final int DEFAULT_SIZE = 1 << 24 ;//方便哈希函数的计算
        private static final int [] seeds = new int []{5,7, 11 , 13 , 31 , 37 , 61};
        private final BitSet bitSet;
        private final simpleHash[] simpleHashes;
        private int size = 0;
    
        public BloomFilter(){
            // 位图
            bitSet = new BitSet(DEFAULT_SIZE);
            simpleHashes = new simpleHash[seeds.length];
            for(int i = 0; i<seeds.length; i++){
                simpleHashes[i] = new simpleHash(DEFAULT_SIZE,seeds[i]);
            }
        }
    
        public void set(String str){
            if(str == null) return;
            for (simpleHash simpleHash : simpleHashes) {
                int hash = simpleHash.hash(str);
                bitSet.set(hash);
            }
            size++;
        }
    
        public boolean contains(String str){
            if(str == null) return false;
            for (simpleHash simpleHash : simpleHashes) {
                int hash = simpleHash.hash(str);
                boolean flag = bitSet.get(hash);
                if(!flag) return false;
            }
            return true;
        }
    }

### 2.5 布隆过滤器删除 ###

布隆过滤器不能直接支持删除工作，因为在删除一个元素时，可能会影响其他元素。

比如：删除上图中"tencent"元素，如果直接将该元素所对应的二进制比特位置0，“baidu”元素也被删除了， 因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠。

一种支持删除的方法：将布隆过滤器中的每个比特位扩展成一个小的计数器，插入元素时给k个计数器(k个哈 希函数计算出的哈希地址)加一，删除元素时，给k个计数器减一，通过多占用几倍存储空间的代价来增加删除操作。

缺陷：

1. 无法确认元素是否真正在布隆过滤器中【会有误判】

2. 存在计数回绕【回绕意思为：溢出】

--------------------

### 2.6 布隆过滤器优点 ###

1. 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无关 2. 哈希函数相互之间没有关系，方便硬件并行运算

3. 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势

4. 在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势

5. 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能

6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算

### 2.7 布隆过滤器缺陷 ###

1. 有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再建立一个白 名单，存储可能会误判的数据)

2. 不能获取元素本身

3. 一般情况下不能从布隆过滤器中删除元素

4. 如果采用计数方式删除，可能会存在计数回绕问题

### 2.8 布隆过滤器使用场景 ###

1. google的guava包中有对Bloom Filter的实现

2. 网页爬虫对URL的去重，避免爬去相同的URL地址。

3. 垃圾邮件过滤，从数十亿个垃圾邮件列表中判断某邮箱是否是垃圾邮箱。

4. 解决数据库缓存击穿，黑客攻击服务器时，会构建大量不存在于缓存中的key向服务器发起请求，在数据量足够大的时候，频繁的数据库查询会导致挂机。

5. 秒杀系统，查看用户是否重复购买。

## 三 . 海量数据面试题 ##

### 1. 哈希切割 ###

问 : 给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？， 如何找到top K的IP？

**哈希切割**：

*  将超过100G的日志文件切分成多个较小的文件，每个文件的大小适合于内存处理。
 *  对每个切分后的文件进行遍历，统计每个IP地址出现的次数。可以使用哈希表（Hash Table）来存储IP地址和对应的出现次数。

1.  **局部top K统计**：
    
     *  对每个切分后的文件进行局部统计，得到每个文件的top K IP地址及其出现次数。可以使用小顶堆（Min Heap）来维护当前的top K IP地址。
2.  **合并top K**：
    
     *  将每个切分后的文件的top K统计结果进行合并，得到整体的top K IP地址及其出现次数。
3.  **最终top K**：
    
     *  对整体的top K统计结果进行合并，得到最终的top K IP地址及其出现次数。

### 2. 位图应用 ###

1. 给定100亿个整数，设计算法找到只出现一次的整数？

*  可以使用两个位图来做,在插入某个元素的时候,如果位图1的该位为1,那么就将位图二中该位置修改为一,最后位图1 ^ 位图2,最后得到的结果统计二进制1的个数即可
 *  也可以使用一个位图来解决问题,在插入是给一个元素两个空间的容量,如果全为1,表示出现的次数大于等于两次

2. 给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？

*  用两个位图存储,再把两个位图&,统计结果中二进制位为1的数量

3. 位图应用变形：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数

可以使用三个位图来解决

*  如果整数在`bitmap1`中对应的位为0，则将其置为1，表示整数已经出现过一次；
 *  如果整数在`bitmap1`中对应的位为1，但在`bitmap2`中对应的位为0，则将其置为1，表示整数已经出现过两次；
 *  如果整数在`bitmap1`和`bitmap2`中对应的位都为1，则将其置为1，并将对应的`bitmap1`和`bitmap2`中的位清零，然后将对应的位在`bitmap3`中置为1，表示整数已经出现过三次或更多次。

### 3.布隆过滤器 ###

1. 给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和 近似算法

精准算法

*  哈希切割进行分块
 *  使用位图进行统计

近似算法

*  将每个文件分成许多块，每个块包含一定数量的查询。这样每个块的大小可以适应内存的限制。
 *  对于第一个文件，遍历每个块，使用布隆过滤器对查询进行哈希，并将结果保存到磁盘上。对于第二个文件，同样遍历每个块，使用相同的布隆过滤器对查询进行哈希，并将结果保存到磁盘上
 *  遍历第二个文件中的每个查询，使用布隆过滤器检查该查询是否在第一个文件中出现过。

2. 如何扩展BloomFilter使得它支持删除元素的操作

**引入计数器**：

*  在传统的 Bloom Filter 中，每个哈希函数对应一个位数组的位置，表示元素的存在与否。现在我们可以将每个位置的 0/1 改为一个计数器，用来记录元素的插入次数。

存储计数器的位可由实际情况进行调整

--------------------

## 总结 ##

ok,大家多多理解,我们下一篇博客见!

[o_n]: https://latex.csdn.net/eq?o%28n%29
[o_nlogn]: https://latex.csdn.net/eq?o%28nlogn%29
[o_logn]: https://latex.csdn.net/eq?o%28logn%29
[7184453e10ea44709eeb3c816f400c3c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/88c50f90fd774c89bbfd22f43c7d1d70.png
[9775e7abd20f45f6b02750c2fd532717.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/43a4d6fdf05c46249dfca8bd7260d7d0.png
[212aa693bd7442dc9cb8b10e3bcfec5b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/f480c2b6e4e5459390a431938016e5b8.png
[a3101a23279244c5821a1289f866163f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/52240c1ee1d047e8856d72d68d68e639.png
[8b45ed19b8424be598f356343123e435.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/92a342feae824593adfb4e6753a5a33b.png
[6c3fddf44b7948018a20ccf943cabf78.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/4ea29054d02948bab0a552bb8797b639.png