您当前的位置:首页 > 互联网百科 > 大数据

海量数据如何判重?

时间:2023-09-18 15:01:52  来源:微信公众号  作者: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 库实现布隆过滤器总共分为以下两步:

  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() 方法来判断元素是否存在于布隆过滤器中。

小结

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



Tags:数据   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,不构成投资建议。投资者据此操作,风险自担。如有任何标注错误或版权侵犯请与我们联系,我们将及时更正、删除。
▌相关推荐
为训练AI,OpenAI等科技巨头花式淘数据
[环球时报特约记者 甄翔]《纽约时报》6日披露了科技公司训练人工智能的秘密&mdash;&mdash;利用语音识别工具转录视频网站YouTube上的视频,形成对话文本数据,供其最新的AI学习...【详细内容】
2024-04-08  Search: 数据  点击:(7)  评论:(0)  加入收藏
训出GPT-5短缺20万亿token!OpenAI被曝计划建「数据市场」
全网真的无数据可用了!外媒报道称,OpenAl、Anthropic等公司正在努力寻找足够的信息,来训练下一代人工智能模型。前几天,OpenAI和微软被曝出正在联手打造超算「星际之门」,解决算...【详细内容】
2024-04-08  Search: 数据  点击:(1)  评论:(0)  加入收藏
国家数据局首次召开全国性工作会议 释放哪些信号?
数据工作不仅事关经济社会发展、人们生产生活,也关乎国家发展与安全大局,其重要性不言而喻。我国是数据生产和应用大国,也是世界上首个提出数据要素理论的国家。正因为此,全国数...【详细内容】
2024-04-07  Search: 数据  点击:(4)  评论:(0)  加入收藏
向量数据库落地实践
本文基于京东内部向量数据库vearch进行实践。Vearch 是对大规模深度学习向量进行高性能相似搜索的弹性分布式系统。详见: https://github.com/vearch/zh_docs/blob/v3.3.X/do...【详细内容】
2024-04-03  Search: 数据  点击:(4)  评论:(0)  加入收藏
谷歌为了结集体诉讼,同意删除 Chrome 无痕模式下收集的用户数据
IT之家 4 月 2 日消息,根据华尔街日报报道,谷歌为了结追溯到 2020 年的集体诉讼案,近日同意删除通过 Chrome 浏览器“无痕(Incognito)模式”下收集的用户数据。这起诉讼原告认为,...【详细内容】
2024-04-02  Search: 数据  点击:(7)  评论:(0)  加入收藏
数据可视化在网络安全中的关键作用
在当今数字化时代,网络安全已成为各大企业乃至国家安全的重要组成部分。随着网络攻击的日益复杂和隐蔽,传统的网络安全防护措施已难以满足需求,急需新型的解决方案以增强网络防...【详细内容】
2024-03-29  Search: 数据  点击:(19)  评论:(0)  加入收藏
如何正确选择NoSQL数据库
译者 | 陈峻审校 | 重楼Allied Market Research最近发布的一份报告指出,业界对于NoSQL数据库的需求正在持续上升。2022年,全球NoSQL市场的销售额已达73亿美元,预计到2032年将达...【详细内容】
2024-03-28  Search: 数据  点击:(13)  评论:(0)  加入收藏
京东小程序数据中心架构设计与最佳实践
一、京东小程序是什么京东小程序平台能够提供开放、安全的产品,成为品牌开发者链接京东内部核心产品的桥梁,致力于服务每一个信任我们的外部开发者,为不同开发能力的品牌商家提...【详细内容】
2024-03-27  Search: 数据  点击:(9)  评论:(0)  加入收藏
为什么数据库连接池不采用 IO 多路复用?
这是一个非常好的问题。IO多路复用被视为是非常好的性能助力器。但是一般我们在使用DB时,还是经常性采用c3p0,tomcat connection pool等技术来与DB连接,哪怕整个程序已经变成以...【详细内容】
2024-03-27  Search: 数据  点击:(12)  评论:(0)  加入收藏
Google搜索引擎索引的网页数量有多少?谷歌官方提供数据进行参考
Google搜索引擎索引的网页数量有多少?二十世纪九十年代,网页的索引数量成了一个各大搜索引擎相互对比的指标。小编记得2000年谷歌搜索引擎的首页搜索框上方,还标记着谷歌索引的...【详细内容】
2024-03-27  Search: 数据  点击:(12)  评论:(0)  加入收藏
▌简易百科推荐
大数据杀熟何时告别“人人喊打却无可奈何”?
2月7日郑州飞往珠海的航班,不同手机、不同账号搜索该航班显示出不同价格。图源网络有网友近日分享在某平台的购票经历,引发社会广泛关注&mdash;&mdash;用3个账号买同一航班同...【详细内容】
2024-01-30    中国青年网  Tags:大数据杀熟   点击:(32)  评论:(0)  加入收藏
简易百科:到底什么是大数据?
随着互联网的快速发展,大数据已经成为了当今社会最热门的话题之一。那么,到底什么是大数据呢?首先,我们需要明确大数据的定义。大数据是指数据量极大、类型繁多、处理难度高的数...【详细内容】
2024-01-30    简易百科  Tags:大数据   点击:(40)  评论:(0)  加入收藏
数据采集新篇章:AI与大模型的融合应用
开篇在AIGC(人工智能与通用计算)应用中,大型语言模型(LLM)占据着举足轻重的地位。这些模型,如GPT和BERT系列,通过处理和分析庞大的数据集,已经极大地推动了自然语言理解和生成的边界...【详细内容】
2024-01-17  崔皓  51CTO  Tags:数据采集   点击:(50)  评论:(0)  加入收藏
挑战 Spark 和 Flink?大数据技术栈的突围和战争
十年的轮回,正如大数据的发展一般,它既是一个轮回的结束,也是崭新的起点。大数据在过去的二十年中蓬勃发展,从无到有,崛起为最具爆炸性的技术领域之一,逐渐演变成为每个企业不可或...【详细内容】
2024-01-17  InfoQ    Tags:大数据   点击:(40)  评论:(0)  加入收藏
分布式存储系统在大数据处理中扮演着怎样的角色?
如果存储节点本身可以定制,则通常会让其支持部分计算能力,以利用数据的亲和性,将部分计算下推到相关的存储节点上。如果存储是云上的 S3 等对象存储,无法定制,则通常会将数据在计...【详细内容】
2023-12-19  木鸟杂记  微信公众号  Tags:大数据   点击:(48)  评论:(0)  加入收藏
大数据如何实时拯救生命:车联网的数据分析有助预防交通事故
译者 | 李睿审校 | 重楼车联网(IoV)是汽车行业与物联网相结合的产物。预计车联网数据规模将越来越大,尤其是当电动汽车成为汽车市场新的增长引擎。问题是:用户的数据平台准备...【详细内容】
2023-12-19    51CTO  Tags:大数据   点击:(41)  评论:(0)  加入收藏
利用生成对抗网络进行匿名化数据处理
在互联网时代,数据日益成为人们的生产资料。然而,在某些情况下,我们需要分享数据,但又需要保护个人隐私。这时,匿名化技术就显得尤为重要。本文将介绍利用生成对抗网络进行匿名化...【详细内容】
2023-12-18  技巧达人小影    Tags:数据处理   点击:(56)  评论:(0)  加入收藏
盘点那些常见的数据中心类型,你知道几个?
在数字化潮流的浪潮下,数据中心如同企业的神经系统,关系到业务的稳健运转。而在这个巨大的网络中,各种数据中心类型如雨后春笋般崭露头角。从企业级的个性至云数据中心的虚拟化...【详细内容】
2023-12-07  数据中心之家  微信公众号  Tags:数据中心   点击:(65)  评论:(0)  加入收藏
数据中心的七个关键特征
随着信息技术的不断演进,数据中心的可靠性、可扩展性、高效性、安全性、灵活性、管理性和可持续性成为业界探讨的焦点。下面让我们一同深入剖析这些关键特征,了解它们是如何影...【详细内容】
2023-12-06  数据中心之家  微信公众号  Tags:数据   点击:(63)  评论:(0)  加入收藏
什么是数据解析?将数据转化为更好的决策
什么是数据解析?数据解析是一门专注于从数据中获取洞察力的学科。它包含数据分析(data analysis)和管理的流程、工具和技术,包括数据的收集、组织和存储。数据解析的主要目的是...【详细内容】
2023-12-06  计算机世界    Tags:数据解析   点击:(62)  评论:(0)  加入收藏
站内最新
站内热门
站内头条