场景题:有 40 亿个 QQ 号如何去重?仅 1GB 内存
场景题也有一些套路可以考虑,比如去重、判断给定数据是否存在
1.大数据去重
1.1 现在有 40 亿个 QQ 号如何去重?仅 1GB 内存
参考链接:https://juejin.cn/post/7396332696660131849
介绍 2 种方法:Bitmap 和布隆过滤器
方法一:Bitmap
首先介绍下什么是位图 Bitmap
位图是使用 bit 数组表示的,它只存储 0 或者 1,因此我们可以把全部的 QQ 号放到位图中,当 index 位置为 1 时表示该索引位的 QQ 号已经存在。

数据规模分析+可行性分析
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 号都在整型范围内
方法二:布隆过滤器
有关布隆过滤器的介绍看下我之前写的文章:布隆过滤器原理和使用场景
相比较位图 Bitmap,布隆过滤器使用了多个 hash 函数计算哈希值作为下标,在位图中的多个下标都为 1 时,则表示数据已存在
优点:加上哈希算法后,我们还可以对字符串或者对象进行存储去重,比如 URL
缺点:存在一定的误判,因为存在哈希冲突的问题
实现方案
使用 redis 的布隆过滤器模块来实现
2.数据统计
比如在线人员统计,将在线人员 id 为偏移值,为 1 表示在线;视频统计,将全部视频的 id 为偏移存储到 Bitmap 中
下篇分享在线数据统计的场景题
版权声明: 本文为 InfoQ 作者【卷福同学】的原创文章。
原文链接:【http://xie.infoq.cn/article/c6181ae12627b941742239172】。文章转载请联系作者。
评论