百度360必应搜狗淘宝本站头条
当前位置:网站首页 > 技术文章 > 正文

40亿QQ号,不超过1G内存,如何去重?

myzbx 2025-07-10 19:27 4 浏览

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


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;
    }
}


4、BitMap的优缺点



我们使用一种数据结构去解决问题,那肯定要知道它的优缺点对吧.


1)Bitmap的优点


  • 空间效率高


相比哈希表存储原始数据,Bitmap仅用1位/元素。对于密集数据(如连续QQ号),空间利用率极高。


  • 操作非常高效


插入和查询均为O(1)复杂度,位运算速度快,适合海量数据实时处理。


  • 去重逻辑简单


只需遍历数据,置位存在标记,无需复杂结构。


2)Bitmap的缺点


  • 存储空间依赖值域范围


若值域范围大但稀疏(如QQ号上限远大于实际数量),空间浪费严重。例如,若QQ号上限为1万亿,需125GB内存,难以承受。


  • 无法存储额外信息,只能记录有还是没有


仅记录是否存在,无法保存出现次数等元数据。


三、最后


有些伙伴认为,使用布隆过滤器也可以实现,40亿的QQ号,不超过1G的内存,进行去重。大家觉得呢? 欢迎评论区留言讨论哈~


作者丨捡田螺的小男孩

来源丨公众号:捡田螺的小男孩(ID:gh_3d11c9893ca0)

dbaplus社群欢迎广大技术人员投稿,投稿邮箱:editor@dbaplus.cn

相关推荐

砌体植筋拉拔试验检验值到底是6.0KN,还是10.2KN,如何计算确定

砌体拉结筋植筋养护完成后,需对所植钢筋进行拉拔试验,以检验植筋的锚固强度是否满足设计要求。检测时,按照一定的抽样比例进行拉拔试验。根据《混凝土结构后锚固技术规程》JGJ145-2013,以同品种、同...

柴油机功率如何计算?计算柴油机功率需要哪些参数?

在汽车领域,对于柴油机功率的计算是一项重要的工作,它有助于我们更好地了解柴油机的性能和适用场景。下面我们就来详细探讨一下柴油机功率的计算方法以及所需的参数。首先,我们要了解计算柴油机功率常用的公式。在...

变压器短路阻抗的作用和计算方法(变压器短路阻抗的作用和计算方法是什么)

变压器短路阻抗的作用和计算方法短路阻抗是在负载试验中测量的一项数据,它是二次侧短接并流过额定电流时,一次侧施加的电压与额定电压的的百分数。那么测量变压器的短路阻抗有什么意义呢?其实变压器的阻抗电压乃是...

9.35m层高高支模支撑架计算书(支模架多高属于高支模)

某工厂新扩建的建筑面积为1989.2m^2,建筑物总体分为2层,但局部为4层。建筑物檐高19.4m,建筑物总高23m。建筑物呈长方形设置,长度为48.20m,宽度为23.88m,结构形式为框架结构...

吊篮(悬挂装置前梁加长)安全复核计算书

吊篮(悬挂装置前梁加长)安全复核计算书一种超常规搭设的高处作业吊篮,因使用要求将吊篮悬挂装置前梁加长设置,本计算书针对这种工况的校核,以作参考。计算依据:1、《高处作业吊篮》GB/T19155-...

电功率计算公式精编汇总(电功率计算视频讲解)

一、电功率计算公式:1在纯直流电路中:P=UIP=I2RP=U2/R式中:P---电功率(W),U---电压(V),I----电流(A),R---电阻(Ω)。2在单相交流电路中:P=UIcosφ...

灌注桩承载力检测方法及步骤(灌注桩承载力不够怎么办)

检测灌注桩的承载力是确保基础工程安全可靠的关键环节,检测结果的精细能准确为我们提供可靠的数据,让我们能准确判断桩基础的承载力,方便后续施工安排,同样也能让我们根据数据分辨出有问题桩基,采取可靠有效的措...

很哇塞的体积计算方法:向量叉乘 很哇塞的体积计算方法

高中数学必看:向量叉乘,体积的神。大家都知道a、b的向量是什么意思,但是a、b的向量又是什么?很多同学都不知道,向量的向量在高中阶段非常有用,虽然它是大学的知识,在高中阶段可以干两件事。·第一件事,表...

施工升降机基础(设置在地库顶板回顶)计算书

施工升降机基础(设置在地库顶板回顶)计算书计算依据:1、《施工现场设施安全设计计算手册》谢建民编著2、《建筑地基基础设计规范》GB50007-20113、《混凝土结构设计标准》GB/T50010-2...

剪力墙水平钢筋根数如何计算?(剪力墙水平钢筋绑扎搭接规范)

剪力墙水平钢筋根数的计算需综合考虑墙高、起步距离、间距及构造要求等因素,具体步骤如下及依据:1.基本计算公式水平钢筋根数计算公式为:根数=(墙高-起步距离)/间距(墙高-起步距离)/间距...

直流电路常用计算公式(直流电路常用计算公式有哪些)

1、电阻导体阻碍电流通过的能力叫做电阻,用字母R表示,单位欧(Ω)。R=ρl/s式中R-导体的电阻,欧(Ω);ρ-导体的电阻率,欧·米(Ω·m);l-导体的长度,米(m);s-导体的截面积,平方米(m...

电气主电路图的绘制特点(电气原理图主电路)

1、电气主电路图中的电气设备、元件,如电源进线、变压器、隔离开关、断路器、熔断器、避雷器等都垂直绘制,而母线则水平绘制。电气主电路图除特殊情况外,几乎无一例外地画成单线图,并以母线为核心将各个项目(如...

中考总复习:物理专题 功和机械能 (功的计算、功率、动能、势能)

中考物理专题:功与机械能解析一、力学中的功——能量转化的桥梁功是力对物体能量变化的量度,需满足两要素:作用在物体上的力、物体沿力方向移动距离。例如推箱子时,若箱子未移动,推力不做功;若箱子滑动,推力做...

40亿QQ号,不超过1G内存,如何去重?

分享一道网上很火的面试题:40亿QQ号,不超过1G的内存,如何去重?这是一个非常经典的海量数据去重问题,并且做了内存限制,最多只能1GB,本文跟大家探讨一下~~一、常规思路我们日常开发中,如果谈到去重...

填充墙体拉结筋植筋深度、孔径、拉拔试验承载力计算!

今天分享下植筋间距及保护层要求:根据JGJ145-2013混凝土后锚固技术规程要求植筋与混凝土结构边缘不应小于5mm,植筋为两根及以上时水平间距为不应小于5d(d为钢筋直径)。根据混凝土结构后锚固技...