关于java:场景题海量数据如何判重

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

那怎么答复这个问题呢？接下来咱们就具体的聊一聊。

参考答案

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

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 之间的关系，如下图所示：

如何实现布隆过滤器？

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

1. 通过程序实现（内存级别计划）：应用 Google Guava 库和 Apache Commons 库实现布隆过滤器。

2. 通过中间件实现（反对数据长久化）：应用 Redis 4.0 之后提供的布隆过滤插件来实现，它的益处是反对长久化，数据不会失落。

   Guava 实现布隆过滤器

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

3. 引入 Guava 依赖
4. 应用 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() 办法来判断元素是否存在于布隆过滤器中。

小结

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

本文已收录到我的面试小站 www.javacn.site，其中蕴含的内容有：Redis、JVM、并发、并发、MySQL、Spring、Spring MVC、Spring Boot、Spring Cloud、MyBatis、设计模式、音讯队列等模块。