场景题：有 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 号都在整型范围内

//初始化长度为2 ^ 32位的位数组BitSet bitmap = new BitSet(1L << 32); // 需调整JVM参数 -Xmx1g//读取QQ号，如果该位为0，标记为1；否则数据重复while(读取QQ号) {    if (!bitmap.get(qq)) {        //数据不存在才set 1，存在则去重了        bitmap.set(qq);    }}//最后，遍历Bitmap位数组，标记为1的位置就是去重后的结果了

方法二：布隆过滤器

有关布隆过滤器的介绍看下我之前写的文章：布隆过滤器原理和使用场景

• 相比较位图 Bitmap，布隆过滤器使用了多个 hash 函数计算哈希值作为下标，在位图中的多个下标都为 1 时，则表示数据已存在

• 优点：加上哈希算法后，我们还可以对字符串或者对象进行存储去重，比如 URL

• 缺点：存在一定的误判，因为存在哈希冲突的问题

实现方案

使用 redis 的布隆过滤器模块来实现

# 初始化过滤器（容量50亿，误判率0.1%）BF.RESERVE qq_filter 0.001 5000000000# 批量添加QQ号BF.MADD qq_filter 12345678 87654321 ...# 检查是否存在BF.EXISTS qq_filter 11223344

2.数据统计

比如在线人员统计，将在线人员 id 为偏移值，为 1 表示在线；视频统计，将全部视频的 id 为偏移存储到 Bitmap 中

下篇分享在线数据统计的场景题