✅被百度追着项目问,上亿数据,限制 1G 内存,如何去重?
有许多方法可以用来去重,比如使用列表、集合等等,但这些方法通常只适用于一般情况。然而,当涉及到大量数据去重时,常见的 Java Set、List,甚至是 Java 8 的新特性 Stream 流等方式就显得不太合适了。在处理大量数据的需求场景下,我们不得不提及 BitMap。
什么是 BitMap?有什么用?
高手回答
基本概念
位图(BitMap),基本思想就是用一个 bit 来标记元素,bit 是计算机中最小的单位,也就是我们常说的计算机中的 0 和 1,这种就是用一个位来表示的。
所谓位图,其实就是一个 bit 数组,即每一个位置都是一个 bit,其中的取值可以是 0 或者 1
像上面的这个位图,可以用来表示 1,,4,6:
如果不用位图的话,我们想要记录 1,4,,6 这三个整型的话,就需要用三个 unsigned int,已知每个 unsigned int 占 4 个字节,那么就是 34 = 12 个字节,一个字节有 8 bit,那么就是 128 = 96 个 bit。
所以,位图最大的好处就是节省空间。
位图有很多种用途,特别适合用在去重、排序等场景中,著名的布隆过滤器就是基于位图实现的。
位图的优势
空间效率优势:为徒极大的节省了存储空间,对于大量稀疏数据,特别是当元素数量远大于实际存在的项时,相比较于使用传统的列表、集合等数据结构,位图的空间占用极小。
查询速度:由于内存访问时按字节或字进行的。因此对单个元素的存在性检查时间复杂度为 O(1),即常量时间,非常快速。
批量操作高效:对于批量插入、删除和查询操作,尤其是统计范围内元素的数量,位图表现出优秀的性能。
位图的劣势
但是位图也有着一定的限制,那就是他只能表示 0 和 1,无法存储其他的数字。所以他只适合这种能表示 true or false 的场景。
BitMap 和 Int 的区别
以 Java 中的 int 为例,来对比观察 BitMap 的优势,再 Java 中,int 类型通常需要 32 位,而 BitMap 使用 1 位就可以来标识此元素是否存在,所以可以认为 BitMap 占用的空间大小只有 int 类型的 1/32,所以有大量数据判重时,使用 BitMap 也可以实现。
了解了什么是 BitMap,那么我们就可以使用 BitMap 来解决大量数据去重的问题
40 亿个无符号整数内存只有 1G,如果要去重的话,如何解决
假设 40 亿个无符号整数数据都是 10 位的话,如果直接使用内存来存储,大约需要 14.9GB 的空间。
每个无符号整数通常占用 4 个字节(32 位),因此 40 亿个无符号整数所需要的总字节数位
4*4000000000
字节。总字节数转换为 GB:
4*4000000000 / 1024 / 1024 /1024
= 14.9 GB
考虑到其中有一些重复的数据,即使这样 1G 的空间基本上也是不够的。所以想要实现这个功能可以借助 BitMap。
如果使用位图的话,40 亿数据存储所需要的内存大概也就是 476M
40 亿无符号整数数据的总字节数是 4000000000 字节,在位图中 1 个 10 位的无符号整数可以使用 1 bit 表示,然后 1 字节 = 8 位(bit)。
4000000000 bit * 1/8
求出字节数,再/ 1024
得到占用的 KB 数,最后/ 1024
得到占用的 MB 数4000000000 * 1 /8 /1024/1024 = 476M
这样相比于之前的 14.9G 来说,大大的节省了很多空间。
比如要把数据"714771310"放到 BitMap 中,就需要找到第 714771310 这个位置,然后把他设置成 1 就可以了。
这样,把 40 亿个数字都放到 BitMap 之后,所有位置上是 1 的表示存在,不为 1 的表示不存在,相同的数据只需要设置一次 1 就可以了,那么,最终就把所有是 1 的数字遍历出来就行了。
BitMap 在 Java 中的使用
BitMap 在 Java 中的具体实现时 java.util 中的 BitSet,BitSet 是一个可变大小的位向量,能够动态增长以容纳更多的数据,以下是 BitSet 基本使用示例:
如有问题,欢迎加微信交流:w714771310,备注- 技术交流 。或关注微信公众号【码上遇见你】。
免费的Chat GPT可关注公众号【AI贝塔】进行体现,无限使用。早用早享受
好了,本章节到此告一段落。希望对你有所帮助,祝学习顺利。
版权声明: 本文为 InfoQ 作者【派大星】的原创文章。
原文链接:【http://xie.infoq.cn/article/8de247cda4fa8377731dc4bdd】。
本文遵守【CC BY-NC-SA】协议,转载请保留原文出处及本版权声明。
评论