找回密码
 立即注册
首页 业界区 安全 场景题:有40亿个QQ号如何去重?仅1GB内存 ...

场景题:有40亿个QQ号如何去重?仅1GB内存

滕佩杉 7 天前
场景题也有一些套路可以考虑,比如去重、判断给定数据是否存在
1.大数据去重

1.1 现在有40亿个QQ号如何去重?仅1GB内存

参考链接:https://juejin.cn/post/7396332696660131849
介绍2种方法:Bitmap和布隆过滤器
方法一:Bitmap

首先介绍下什么是位图Bitmap
位图是使用bit数组表示的,它只存储0或者1,因此我们可以把全部的QQ号放到位图中,当index位置为1时表示该索引位的QQ号已经存在。
1.jpeg

数据规模分析+可行性分析

  • QQ号是32位的无符号整型数据,整型数据范围是[-2^31, 2^31-1],总计数据量有43亿,可以覆盖40亿的QQ号。直接存储40亿QQ号,需要的空间为40亿 * 4字节 = 14.9GB,超过1GB了。
  • 使用Bitmap来存储,每个QQ号仅占1位,比如:QQ号23333,只需要判断Bitmap的索引位23333是否为1,为1表示数据已经存在,就能判断是否重复了。所需要内存空间: 2 ^ 32 * 1bit / 8 = 512MB
实现步骤
直接用java自带的Bitset来实现代码,假设QQ号都在整型范围内
[code]//初始化长度为2 ^ 32位的位数组BitSet bitmap = new BitSet(1L
您需要登录后才可以回帖 登录 | 立即注册