场景题：海量数据如何判重？

秒速五厘米 2023-10-16 10:13 45阅读 0赞

![3589324c0c6170d5137ed4f200a5b4f9.png][]

作者 | 磊哥

来源 |公众号：Java中文社群

转载请联系授权（微信ID：GG\_Stone）

在海量数据如何确定一个值是否存在？这是一道非常经典的面试场景题。

那怎么回答这个问题呢？接下来咱们就详细的聊一聊。

### 参考答案 ###

判断一个值是否存在？通常有以下两种解决方案：

1.  使用哈希表：可以将数据进行哈希操作，将数据存储在相应的桶中。查询时，根据哈希值定位到对应的桶，然后在桶内进行查找。这种方法的时间复杂度为 O(1)，但需要额外的存储空间来存储哈希表。如果桶中存在数据，则说明此值已存在，否则说明未存在。
2.  使用布隆过滤器：布隆过滤器是一种概率型数据结构，用于判断一个元素是否在集合中。它利用多个哈希函数映射数据到一个位数组，并将对应位置置为 1。查询时，只需要对待查询的数据进行哈希，并判断对应的位是否都为 1。如果都为 1，则该数据可能存在；如果有一个位不为 1，则该数据一定不存在。布隆过滤器的查询时间复杂度为 O(k)，其中 k 为哈希函数的个数。

#### 相同点和不同点 ####

它们两的相同点是：它们都存在误判的情况。例如，使用哈希表时，不同元素的哈希值可能相同，所以这样就产生误判了；而布隆过滤器的特征是，当布隆过滤器说，某个数据存在时，这个数据可能不存在；当布隆过滤器说，某个数据不存在时，那么这个数据一定不存在。

它们两的区别主要有以下几点：

1.  存储机制：哈希表使用一个数组来存储键值对，通过哈希函数将键映射到数组的索引位置，然后将值存储在对应的位置上。而布隆过滤器则使用一个位数组（或位向量），通过多个哈希函数将元素映射到位数组的多个位上。
2.  查询操作：哈希表在进行查询时，通过计算哈希值来定位键值对的存储位置，然后直接获取对应的值。查询时间复杂度通常为 O(1)。布隆过滤器在进行查询时，也通过多个哈希函数计算多个位，然后判断对应的位是否都为 1 来确定元素是否存在。查询时间复杂度为 O(k)，其中 k 为哈希函数的个数。
3.  内存占用：哈希表需要根据数据规模来动态调整数组的大小，以保证存储效率。而布隆过滤器在预先设置位数组的大小后，不会随数据规模的增加而增长。因此布隆过滤器更适用于海量数据。

#### 结论 ####

哈希表和布隆过滤器都能实现判重，但它们都会存在误判的情况，但布隆过滤器存储占用的空间更小，更适合海量数据的判重。

### 布隆过滤器实现原理 ###

布隆过滤器的实现，主要依靠的是它数据结构中的一个位数组，每次存储键值的时候，不是直接把数据存储在数据结构中，因为这样太占空间了，它是利用几个不同的无偏哈希函数，把此元素的 hash 值均匀的存储在位数组中，也就是说，每次添加时会通过几个无偏哈希函数算出它的位置，把这些位置设置成 1 就完成了添加操作。

当进行元素判断时，查询此元素的几个哈希位置上的值是否为 1，如果全部为 1，则表示此值存在，如果有一个值为 0，则表示不存在。因为此位置是通过 hash 计算得来的，所以即使这个位置是 1，并不能确定是那个元素把它标识为 1 的，因此布隆过滤器查询此值存在时，此值不一定存在，但查询此值不存在时，此值一定不存在。

并且当位数组存储值比较稀疏的时候，查询的准确率越高，而当位数组存储的值越来越多时，误差也会增大。

位数组和 key 之间的关系，如下图所示：

![a6c05d00cd46702745c70f88bacdc22f.png][]

### 如何实现布隆过滤器？ ###

布隆过滤器的实现通常有以下两种方案：

1.  通过程序实现（内存级别方案）：使用 Google Guava 库和 Apache Commons 库实现布隆过滤器。
2.  通过中间件实现（支持数据持久化）：使用 Redis 4.0 之后提供的布隆过滤插件来实现，它的好处是支持持久化，数据不会丢失。

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

使用 Google Guava 库实现布隆过滤器总共分为以下两步：

1.  引入 Guava 依赖
2.  使用 Guava API 操作布隆过滤器

具体实现如下。

#### ① 引入 Guava 依赖 ####

<dependency>
        <groupId>com.google.guava</groupId>
        <artifactId>guava</artifactId>
    </dependency>

#### ② 使用 Guava API ####

import com.google.common.hash.BloomFilter;
    import com.google.common.hash.Funnels;
    
    public class BloomFilterExample {
        public static void main(String[] args) {
            // 创建一个布隆过滤器，设置期望插入的数据量为10000，期望的误判率为0.01
            BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.unencodedCharsFunnel(), 10000, 0.01);
    
            // 向布隆过滤器中插入数据
            bloomFilter.put("data1");
            bloomFilter.put("data2");
            bloomFilter.put("data3");
    
            // 查询元素是否存在于布隆过滤器中
            System.out.println(bloomFilter.mightContain("data1")); // true
            System.out.println(bloomFilter.mightContain("data4")); // false
        }
    }

在上述示例中，我们通过 BloomFilter.create() 方法创建一个布隆过滤器，指定了元素序列化方式、期望插入的数据量和期望的误判率。然后，我们可以使用 put() 方法向布隆过滤器中插入数据，使用 mightContain() 方法来判断元素是否存在于布隆过滤器中。

### 小结 ###

在海量数据如何确定一个值是否存在？通常有两种解决方案：哈希表和布隆过滤器，而它们两都存在误判的情况，但布隆过滤器更适合海量数据的判断，因为它占用的数据空间更小。布隆过滤器的特征是：当布隆过滤器说，某个数据存在时，这个数据可能不存在；当布隆过滤器说，某个数据不存在时，那么这个数据一定不存在。

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

### 说件大事 ###

磊哥一直在做的事，为了让大家找到更好的工作，所以有着13 年工作经验的我，开发了一门《Java 面试突击课》。

整个课程以包含 15 万字的图文课件 + 3000 多分钟的视频课（支持永久观看），带领大家一起高效、系统的复习 Java 面试知识。整个课程从 Java 基础到微服务 Spring Cloud 应用尽有，包含以下 16 个大的模块：

![9da373ead936741fef80644a18b2447c.png][]

收费只要 1200 元，带你高效的搞定面试问题，学完之后可以搞定目前市面上的绝大部分面试，锁定高薪 Offer。

报名只需加我微信：GG\_Stone【备注：面试课】

![8837b97d3772a51c316217c277b673ee.png][]

[3589324c0c6170d5137ed4f200a5b4f9.png]: https://img-blog.csdnimg.cn/img_convert/3589324c0c6170d5137ed4f200a5b4f9.png
[a6c05d00cd46702745c70f88bacdc22f.png]: https://img-blog.csdnimg.cn/img_convert/a6c05d00cd46702745c70f88bacdc22f.png
[9da373ead936741fef80644a18b2447c.png]: https://img-blog.csdnimg.cn/img_convert/9da373ead936741fef80644a18b2447c.png
[8837b97d3772a51c316217c277b673ee.png]: https://img-blog.csdnimg.cn/img_convert/8837b97d3772a51c316217c277b673ee.png