40亿QQ号，不超过1G内存，如何去重？

dbaplus社群 10小时前

文章探讨了如何对40亿QQ号码进行去重，同时限制内存使用不超过1GB。由于直接使用HashSet会超出内存限制，文章提出使用BitMap（位图）作为解决方案。BitMap通过使用位来表示数字是否存在，从而大大节省存储空间。文章详细介绍了BitMap的原理、实现方法，以及其优缺点，并提供了简单的代码示例。最后，文章也提到了布隆过滤器作为另一种可能的解决方案，引发读者思考。

💡传统方法，例如使用HashSet，直接存储40亿QQ号码会占用大约30GB内存，远超1GB的内存限制，因此不适用。

💡BitMap是一种高效的数据结构，它使用一个bit位来表示一个数字是否存在，从而大大节省存储空间。对于40亿QQ号码，使用BitMap只需要大约0.466GB的内存，满足内存限制。

💡使用BitMap去重的流程包括：初始化一个40亿位的BitMap；遍历所有QQ号码，将每个号码映射到BitMap的对应位置，并将该位置的bit设置为1；遍历BitMap，收集所有设置为1的位对应的QQ号码，即为去重后的QQ号码。

💡BitMap的优点在于空间效率高，操作高效，去重逻辑简单。缺点是存储空间依赖值域范围，且无法存储额外信息。

捡田螺的小男孩 2025-06-08 08:01 广东

一个非常经典的海量数据去重问题。

分享一道网上很火的面试题：

40亿QQ号，不超过1G的内存，如何去重？

这是一个非常经典的海量数据去重问题，并且做了内存限制，最多只能1GB，本文跟大家探讨一下~~

一、常规思路

我们日常开发中,如果谈到去重,最容易想到的就是放到HashSet,直接放到HashSet就好:

Set<Long> qqSet = new HashSet<>();
qqSet.add(qqNumber); // 自动去重

但是呢,是有个1G的内存限制的! 如果放到HashSet,那40亿的QQ数据,都是在内存中的话,我们来算一下,40亿的QQ,要多大的内存:

如果每个QQ号是64位整数（8字节），那么40亿个QQ号的总存储量为：

40亿 * 8字节 = 320亿字节

转化位KB 32,000,000,000 字节/1024 = 31,250,000 KB

KB转化为MB 31,250,000 KB/ 1024 ≈ 30,517.578125 MB

MB转化为GB 30,517.578125 MB/ 1024 ≈ 29.8023223876953125 GB

那就是30GB左右,如果每个QQ号码是32位整数(4字节),则是15GB左右. 显然,都远超1GB的内存.

因此,直接放到HashSet并不可行.

因此,这道题我们需要换个思路,就是在内存有限的情况下,如何实现去重? 我们可以考虑一种更高效的数据结构来处理这个问题。

我们可以考虑BitMap（位图)来解决这个问题.

二、BitMap

1、BitMap 到底是什么

BitMap（位图）是一种非常高效的数据结构，特别适合处理大规模数据的去重和查询问题。它的基本思想是使用一个bit位来表示一个数字是否存在。

例如，如果我们有一个长度为10的BitMap，那么它可以表示数字0到9是否存在：

如果BitMap的第0位是1，表示数字0存在；

如果BitMap的第1位是1，表示数字1存在；

如果BitMap的第2位是1，表示数字2存在；

以此类推~

数字9表示的BitMap如下:

如果用BitMap,比如我要记录的QQ号码分别是9、5、2、7, 那么BitMap表示为:

显然只需要一个10位就可以表示,如果用传统方法来记录,一个整型4字节,4个QQ号码就是,4*4=16字节,然后一个字节8位,那就是 16*8=128位啦~. 可以发现用BitMap 可以大大节省存储空间.

2、用BitMap给40亿QQ去重

1）使用BitMap,40亿的QQ是否超过1GB内存

既然BitMap 可以大大节省存储空间,我们用BitMap来给40亿QQ去重,看看会不会超1G的内存.

我们来一起估算一下, 因为要40亿的QQ,那我们申请一个足够大的BitMap,假设就是40亿的位,那内存大概就是:

4,000,000,000/8 = 500,000,000

500,000,000/1024/1024/1024 ≈ 0.466GB

可以发现,只需要0.466GB的内存就足够啦~ 在内存这方面,是符合不超过1GB的限制的~

2）使用BitMap,给40亿QQ 去重流程

首先,初始化好40亿位的BitMap

其次,遍历这40亿的QQ,把每个QQ号码映射到BitMap中,给对应位置的bit,设置为1

比如,假设有个QQ号码为326443281,那么就在BitMap的对应位置,设置为1

遍历BitMap，收集所有设置为1的位对应的QQ号码,即为去重后的QQ号码。

3、BitMap去重的简单代码实现

给大家来个简单的代码模拟吧：

import java.util.*;
public class QQDeduplication {
    // 位图的大小为 4,294,967,296 bits，即 0.5 GB
    private static final long BITMAP_SIZE = 1L << 32; // 2^32
    private static final int BYTE_SIZE = 8; // 每个字节有8位
    private static List<Long> deduplicateQQNumbers(long[] qqNumbers) {
        // 创建位图，使用字节数组
        byte[] bitmap = new byte[(int) (BITMAP_SIZE / BYTE_SIZE)];
        // 更新位图
        for (long qqNumber : qqNumbers) {
            if (qqNumber >= 0 && qqNumber < BITMAP_SIZE) {
                // 计算字节索引和位索引
                int index = (int) (qqNumber / BYTE_SIZE);
                int bitPosition = (int) (qqNumber % BYTE_SIZE);
                // 设置对应的位
                bitmap[index] |= (1 << bitPosition);
            }
        }
        // 收集去重后的QQ号码
        List<Long> uniqueQQNumbers = new ArrayList<>();
        for (int i = 0; i < bitmap.length; i++) {
            for (int j = 0; j < BYTE_SIZE; j++) {
                if ((bitmap[i] & (1 << j)) != 0) {
                    long qqNumber = (long) i * BYTE_SIZE + j;
                    uniqueQQNumbers.add(qqNumber);
                }
            }
        }
        return uniqueQQNumbers;
    }
}