首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
AI 模拟面试
简历
求职
学习
基础学习课
实战项目课
求职辅导课
专栏&文章
竞赛
我要招人
发布职位
发布职位、邀约牛人
更多企业解决方案
AI面试、笔试、校招、雇品
HR免费试用AI面试
最新面试提效必备
登录
/
注册
小白White_
门头沟学院 Java
发布于宁夏
关注
已关注
取消关注
@Java大湿兄:
场景题:海量数据如何判重?
在海量数据如何确定一个值是否存在?这是一道非常经典的面试场景题。那怎么回答这个问题呢?接下来咱们就详细的聊一聊。参考答案判断一个值是否存在?通常有以下两种解决方案:使用哈希表:可以将数据进行哈希操作,将数据存储在相应的桶中。查询时,根据哈希值定位到对应的桶,然后在桶内进行查找。这种方法的时间复杂度为 O(1),但需要额外的存储空间来存储哈希表。如果桶中存在数据,则说明此值已存在,否则说明未存在。使用布隆过滤器:布隆过滤器是一种概率型数据结构,用于判断一个元素是否在集合中。它利用多个哈希函数映射数据到一个位数组,并将对应位置置为 1。查询时,只需要对待查询的数据进行哈希,并判断对应的位是否都为 1。如果都为 1,则该数据可能存在;如果有一个位不为 1,则该数据一定不存在。布隆过滤器的查询时间复杂度为 O(k),其中 k 为哈希函数的个数。相同点和不同点它们两的相同点是:它们都存在误判的情况。例如,使用哈希表时,不同元素的哈希值可能相同,所以这样就产生误判了;而布隆过滤器的特征是,当布隆过滤器说,某个数据存在时,这个数据可能不存在;当布隆过滤器说,某个数据不存在时,那么这个数据一定不存在。它们两的区别主要有以下几点:存储机制:哈希表使用一个数组来存储键值对,通过哈希函数将键映射到数组的索引位置,然后将值存储在对应的位置上。而布隆过滤器则使用一个位数组(或位向量),通过多个哈希函数将元素映射到位数组的多个位上。查询操作:哈希表在进行查询时,通过计算哈希值来定位键值对的存储位置,然后直接获取对应的值。查询时间复杂度通常为 O(1)。布隆过滤器在进行查询时,也通过多个哈希函数计算多个位,然后判断对应的位是否都为 1 来确定元素是否存在。查询时间复杂度为 O(k),其中 k 为哈希函数的个数。内存占用:哈希表需要根据数据规模来动态调整数组的大小,以保证存储效率。而布隆过滤器在预先设置位数组的大小后,不会随数据规模的增加而增长。因此布隆过滤器更适用于海量数据。结论哈希表和布隆过滤器都能实现判重,但它们都会存在误判的情况,但布隆过滤器存储占用的空间更小,更适合海量数据的判重。布隆过滤器实现原理布隆过滤器的实现,主要依靠的是它数据结构中的一个位数组,每次存储键值的时候,不是直接把数据存储在数据结构中,因为这样太占空间了,它是利用几个不同的无偏哈希函数,把此元素的 hash 值均匀的存储在位数组中,也就是说,每次添加时会通过几个无偏哈希函数算出它的位置,把这些位置设置成 1 就完成了添加操作。当进行元素判断时,查询此元素的几个哈希位置上的值是否为 1,如果全部为 1,则表示此值存在,如果有一个值为 0,则表示不存在。因为此位置是通过 hash 计算得来的,所以即使这个位置是 1,并不能确定是那个元素把它标识为 1 的,因此布隆过滤器查询此值存在时,此值不一定存在,但查询此值不存在时,此值一定不存在。并且当位数组存储值比较稀疏的时候,查询的准确率越高,而当位数组存储的值越来越多时,误差也会增大。位数组和 key 之间的关系,如下图所示:如何实现布隆过滤器?布隆过滤器的实现通常有以下两种方案:通过程序实现(内存级别方案):使用 Google Guava 库和 Apache Commons 库实现布隆过滤器。通过中间件实现(支持数据持久化):使用 Redis 4.0 之后提供的布隆过滤插件来实现,它的好处是支持持久化,数据不会丢失。Guava 实现布隆过滤器使用 Google Guava 库实现布隆过滤器总共分为以下两步:引入 Guava 依赖使用 Guava API 操作布隆过滤器具体实现如下。① 引入 Guava 依赖<dependency> <groupId>com.google.guava</groupId> <artifactId>guava</artifactId></dependency>② 使用 Guava APIimport 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() 方法来判断元素是否存在于布隆过滤器中。小结在海量数据如何确定一个值是否存在?通常有两种解决方案:哈希表和布隆过滤器,而它们两都存在误判的情况,但布隆过滤器更适合海量数据的判断,因为它占用的数据空间更小。布隆过滤器的特征是:当布隆过滤器说,某个数据存在时,这个数据可能不存在;当布隆过滤器说,某个数据不存在时,那么这个数据一定不存在。
点赞 2
评论 0
全部评论
推荐
最新
楼层
暂无评论,快来抢首评~
相关推荐
07-31 17:30
中南大学 Java
最强本科✌
带带杨巅峰:
清华本也是985本
什么样的背景能拿SSP?
点赞
评论
收藏
分享
不愿透露姓名的神秘牛友
07-30 11:34
这是认真的吗?
真的很糟糕:
黑奴听了都流泪啊
点赞
评论
收藏
分享
07-23 20:28
北京大学 硬件开发
是谁的简历如此不垂直,被吐槽。
没错,正是我的,求助各位uu以后的就业方向,简单说说本人心路历程,因为本硕导师都是工艺材料,不想去fab or 研究所,所以一开始投了ic但是找不到,所以为了保底做了两段硬件的实习,第三段本来拿到了新华三的硬件offer,但是因为同时拿到了Cadence的实习offer(以为是ic验证)就没继续实习硬件,进去了才发现是做EDA工具验证,大概有点像软件测试,写Case和脚本验证Cadence工具的稳定性,和电路基本上接触不到,但是好处是能接触到Linux系统(之前没用过),以及全英工作环境很锻炼人,外加组里氛围特别好,而且不打卡,工作压力小,所以还是打算呆一呆。就好奇后面怎么发展,目前想的是央国企和私企,不考公。央国企有推荐的岗位吗。如果去私企的话,因为EDA验证岗位太小众了,后续是不是只能下一段继续找硬件的实习?然后秋招投个类似于华子单板硬件之类的?这个Cadence实习应该不能作为跳板去找ic的实习吧。
投递新华三等公司10个岗位
点赞
评论
收藏
分享
07-30 17:25
内蒙古大学 模拟IC设计
小米,你是如此的冷酷无情😭
没有测评没有笔试没有感谢信,直接就是一个寄
投递小米集团等公司10个岗位
点赞
评论
收藏
分享
评论
点赞成功,聊一聊 >
点赞
收藏
分享
评论
提到的真题
返回内容
全站热榜
更多
1
...
都是 dirty work,为什么别人的简历上就能言之有物🤔
2.1W
2
...
虾皮秋招一面
4397
3
...
虾皮后端一面(已挂)
4370
4
...
百度提前批,三面被推迟一周,喜提秋招第一凉
3758
5
...
7.30滴滴提前批一面凉经
3478
6
...
百度提前批 三面
3329
7
...
干活最少的实习生因为长得漂亮转正了
3075
8
...
他拿大厂SSP Offer打牌是什么概念啊?25届双非之光
2923
9
...
7.30百度提前批一面
2580
10
...
QQ提前批一面凉经
2573
创作者周榜
更多
正在热议
更多
#
你遇到最难的面试题目是_
#
15392次浏览
194人参与
#
反问环节如何提问
#
95585次浏览
1951人参与
#
中兴秋招
#
203984次浏览
2282人参与
#
简历上的经历如何包装
#
24808次浏览
731人参与
#
如何看待offer收割机的行为
#
815725次浏览
6088人参与
#
你最讨厌面试问你什么?
#
25475次浏览
286人参与
#
秋招最大的收获是什么?
#
38657次浏览
323人参与
#
我的实习收获
#
90952次浏览
1039人参与
#
26届的你,投了哪些公司?
#
37671次浏览
434人参与
#
滴滴求职进展汇总
#
233401次浏览
2116人参与
#
作业帮求职进展汇总
#
57041次浏览
376人参与
#
初创公司值得加入吗?
#
27365次浏览
194人参与
#
我对___祛魅了
#
43846次浏览
410人参与
#
数字马力求职进展汇总
#
184486次浏览
1500人参与
#
你跟室友的关系怎么样?
#
6186次浏览
94人参与
#
什么样的背景能拿SSP?
#
31980次浏览
207人参与
#
工作中哪个瞬间让你想离职
#
60927次浏览
548人参与
#
和同事相处最忌讳的是__
#
21426次浏览
217人参与
#
去年你投递实习了吗?
#
22894次浏览
331人参与
#
如何快速融入团队?
#
15065次浏览
182人参与
#
机械人的金三校招总结
#
36279次浏览
461人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务