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

本文介绍: 大家好,今天给大家带来两种数据结构无位图&布隆过滤器 ok,大家多多理解,我们下一篇博客见!

文章 目录

前言

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

一 . 位图

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

1.1 面试题

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

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

或者先排序 $o(nlogn)$ 再进行一次二分查找 $o(logn)$

来总结一下 遍历 $o(n)$ 二分查找 $o(nlogn)$ + $o(logn)$

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

在这里引出位图

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

1.2 位图概念

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

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

1.3 位图的实现

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

首先看插入

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

/*
* 位图
* */
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 &gt; 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 &gt; elem.length){
            return false;
        }
        int arrayIndex = val/8;
        int bitIndex = val%8;
        return (elem[arrayIndex] &amp; (1 << bitIndex)) != 0;
    }

    /**
     * 将对应位置置为零
     * @param val
     * @return
     */
    public void reSet(int val){
        if(val < 0){
            throw new IndexOutOfBoundsException();
        }
        if(val/8+1 &gt; elem.length){
            elem = Arrays.copyOf(elem, val / 8 + 1);
        }
        int arrayIndex = val/8;
        int bitIndex = val%8;

        elem[arrayIndex] &amp;= ~(1<<bitIndex);
    }

    /**
     * 当前比特位有多少个1
     * @return
     */
    public int getUsedSize() {
        return this.usedSize;
    }

}

1.4 位图的应用

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

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

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

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

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

二 . 布隆 过滤器

2.1 布隆 过滤器提出

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

2.2布隆过滤器概念

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

插入

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 &gt;&gt;&gt; 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地址和对应的出现次数。

局部 top K统计：
- 对每个切分后的文件进行局部统计，得到每个文件的top K IP地址及其出现次数。可以使用小顶堆（Min Heap）来维护当前的top K IP地址。
合并 top K：
- 将每个切分后的文件的top K统计结果进行合并，得到整体的top K IP地址及其出现次数。
最终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内存，如何找到两个文件交集？分别给出精确算法和近似算法

精准算法

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

近似算法

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