在海量数据如何确定一个值是否存在？这是一道非常经典的面试场景题。
那怎么回答这个问题呢？接下来咱们就详细的聊一聊。
判断一个值是否存在？通常有以下两种解决方案：
它们两的相同点是：它们都存在误判的情况。例如，使用哈希表时，不同元素的哈希值可能相同，所以这样就产生误判了；而布隆过滤器的特征是，当布隆过滤器说，某个数据存在时，这个数据可能不存在；当布隆过滤器说，某个数据不存在时，那么这个数据一定不存在。
它们两的区别主要有以下几点：
哈希表和布隆过滤器都能实现判重，但它们都会存在误判的情况，但布隆过滤器存储占用的空间更小，更适合海量数据的判重。
布隆过滤器的实现，主要依靠的是它数据结构中的一个位数组，每次存储键值的时候，不是直接把数据存储在数据结构中，因为这样太占空间了，它是利用几个不同的无偏哈希函数，把此元素的 hash 值均匀的存储在位数组中，也就是说，每次添加时会通过几个无偏哈希函数算出它的位置，把这些位置设置成 1 就完成了添加操作。
当进行元素判断时，查询此元素的几个哈希位置上的值是否为 1，如果全部为 1，则表示此值存在，如果有一个值为 0，则表示不存在。因为此位置是通过 hash 计算得来的，所以即使这个位置是 1，并不能确定是那个元素把它标识为 1 的，因此布隆过滤器查询此值存在时，此值不一定存在，但查询此值不存在时，此值一定不存在。
并且当位数组存储值比较稀疏的时候，查询的准确率越高，而当位数组存储的值越来越多时，误差也会增大。
位数组和 key 之间的关系，如下图所示：
布隆过滤器的实现通常有以下两种方案：
使用 Google Guava 库实现布隆过滤器总共分为以下两步：
具体实现如下。
<dependency> <groupId>com.google.guava</groupId> <artifactId>guava</artifactId></dependency>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() 方法来判断元素是否存在于布隆过滤器中。
在海量数据如何确定一个值是否存在？通常有两种解决方案：哈希表和布隆过滤器，而它们两都存在误判的情况，但布隆过滤器更适合海量数据的判断，因为它占用的数据空间更小。布隆过滤器的特征是：当布隆过滤器说，某个数据存在时，这个数据可能不存在；当布隆过滤器说，某个数据不存在时，那么这个数据一定不存在。
本文链接：http://www.28at.com/showinfo-26-10404-0.html场景题：海量数据如何判重？
声明：本网页内容旨在传播知识，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。邮件：2376512515@qq.com
上一篇： IDC下调中国政务云整体市场5年复合增长率至16.14%
下一篇： 性能测试的需求分析
Copyright © 2016-2023 天津谷骐科技有限公司 版权所有 sitemap.xml
违法及侵权请联系：2376512515@qq.com 津ICP备18001702号
津公网安备 12010102000574号