29｜位图：如何用更少空间对大量数据进行去重和排序？
黄清昊
该思维导图由 AI 生成，仅供参考
你好，我是微扰君。
今天我们从一道非常经典的面试题开始说起，看看你能否用之前学过的知识回答出来，题目是这样的：QQ，相信你肯定用过，假设 QQ 号（也就是用户的 ID）是一个 10 位以内的数字，用一个长整型是可以存储得下的。
现在，有一个文件里存储了很多个 QQ 号，但可能会有一定的重复，如果让你遍历一边文件，把其中重复的 QQ 号都过滤掉，然后把结果输出到一个新的文件中。你会怎么做？如果 QQ 号多达 40 亿个，但是你的内存又比较有限（比如 1GB），又会怎么做呢？
你可以先暂停，思考一下这个问题，如果有了初步思路，我们一起进入今天的学习。
直接基于内存进行去重
先来说说常规的思路。假设我们的数据可以被内存装下，这个问题其实就有很多种方式可以解决。
比如，对于去重，直接采用基于散列思想的 hashset，或者基于树状结构的 set 就可以了，前者可以在 O(1) 的时间复杂度内，判断某个元素是否存在于集合中，后者虽然需要 O(logN) 的时间复杂度，但是在十亿的数量级下，其实也就是比较 30 次左右，代价也并不高；然后我们遍历一遍整个文件，存入 set 中，再输出到另一个文件。总的时间复杂度，前者是 O(N)，后者是 O(N*logN)。
当然还有一种思路，我们先用数组把所有 QQ 号存储下来，进行排序；然后顺次遍历，跳过所有和前个 QQ 号相同的 QQ 号，就能实现去重，采用快排同样可以达到 O(N*logN) 的时间复杂度。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
位图技术是一种高效的数据去重和排序方法，通过使用二进制位来标记元素的存在与否，大大压缩了内存的使用空间。本文介绍了如何利用外排和Bitmap技术解决40亿个QQ号的去重任务，以及具体的代码实现和数据库中的Bitmap索引应用。文章还提到了Bitmap在计算机领域的广泛应用，包括文件系统、数据库和Redis等领域。总结指出，Bitmap在大量数据去重和排序的场景下非常有用，同时在数据库中建立位图索引可以大大提高多条件过滤查询的效率。最后，鼓励读者尝试自己动手实现，并提出课后练习建议。整体而言，本文深入浅出地介绍了Bitmap技术的原理和应用，对读者快速了解该技术具有很高的参考价值。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《业务开发算法 50 讲》，新⼈⾸单¥59
《业务开发算法 50 讲》，新⼈⾸单¥59
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(5)
- 最新
- 精选
- Geek_37dde4题目很真实 腾讯3面遇到过 原题是设计存储结构存储10位qq号的在线状态
作者回复: 可能也是qq号这个场景特别适合😂
2022-03-17 
陈永强老师，是不是有一行代码写错啦？？ BitMap(int size){ // 声明bitmap数组 flags = NULL; flags = new char[size]; memset(flags, 0x0, size * sizeof(char)); this->size = size; } 中的 flags = new char[size]; 是不是size要除以8呢？2022-04-0911
blentle布隆过滤器2022-03-011
拓山【整个过程完成后，其实我们不止做到了去重，也做到了排序】 bitMap这个排序说的不对吧，bitMap只能标记 hash之后的数字被压缩在某一个bit位上。没有什么排序的能力2023-08-10归属地：浙江1
奕bitmap 一般用于计数，是否存在的场景2022-07-24
收起评论
