本文共 1756 字，大约阅读时间需要 5 分钟。

1.什么是bitmap

我们知道很多常见的存储结构，数组、链表、散列表等容器。那么BitMap是什么呢？我们先一起看看，再分析为什么需要bitmap。

我们知道一个int占据4个字节，32个bit，比如我存储一个int数据，值为8，那么存储结构如下：

00000000 00000000 00000000 00100000

一共32位。如果我们申请一个int类型的数组，比如 new int[32],总计占用内存32*32bit，需要大量的内存空间，有没有可以优化的方法呢？

现假如我们用int字节码的每一位表示一个数字的话，那么32个数字只需要一个int类型所占内存空间大小就够了，这样在大数据量的情况下会节省很多内存。

具体思路：

　　1个int占4字节即4*8=32位，那么我们只需要申请一个int数组长度为 int tmp[1+N/32]即可存储完这些数据，其中N代表要进行查找的总数，tmp中的每个元素在内存在占32位可以对应表示十进制数0~31,所以可得到BitMap表:

　　　　tmp[0]:可表示0~31

　　　　tmp[1]:可表示32~63

　　　　tmp[2]可表示64~95

　　　　.......

　　那么接下来就看看十进制数如何转换为对应的bit位：

　　假设这40亿int数据为：6,3,8,32,36,......，那么具体的BitMap表示为：

思路：我们用bit位标示数字，如何确定一个数字在那个tmp元素呢？求商。如何判断在tmp的某个位置呢？求模。

比如我们判断36，首先36/32，商为1，则36在tmp[1]中，具体那个位置呢？求余36%32结果为4，则在第四个位置。我们通过上图确认一下，结果是正确的。

核心思想：用bit位表示数据，节省存储空间

2. 应用场景

2.1 10亿int整型数，以及一台可用内存为1GB的机器，时间复杂度要求O(n)，统计只出现一次的数？

我们首先分析一下，10亿个数，不可能全部加载内存，然后进行比较，10亿个数，需要40亿个字节，也就是4G空间，目前只有1G内存，所以不可行。

考虑如何节省内存空间表示int类型呢？当然是上面的位图了。也就是bitmap。

那么把所有int整型数字表示出来需要2^32 bit位的空间，为了方便，我们可以把这些信息每8bit分割保存为byte数组，换算成字节单位也就是2^32 bit/8 = 2^29 Byte，大约等于512MB。

出现的次数分为未出现、出现一次、大于一次三种情况，我们需两个bit位表示，分别为00、01、11表示未出现、出现一次、出现大于一次。

所以我们这个题目用2bitmap处理，循环读取10亿个数字，如果这个数字出现，更新2bit的标志位，最后2bitmap中是01的就是出现一次的。此处的存储空间要求大，

共需内存2^32 * 2 bit=1 GB内存

2.2 对没有重复元素的整数进行排序

对于非重复的整数排序BitMap有着天然的优势，它只需要将给出的无重复整数扫描完毕，组装成为BitMap之后，那么直接遍历一遍Bit区域就可以达到排序效果了。

举个例子：对整数4、3、1、7、6进行排序：

直接按Bit位输出就可以得到排序结果了。

2.3 已知某个文件内包含一些电话号码，每个号码为8位数字，统计不同号码的个数

8位的电话号码为0-99 999 999，需要99 999 999个bit位就可以，99 999 999/8/1000/1024M=12.2M

3 优点

• 节省空间，提高存储效率，适合处理大数据量
• 利用位运算，计算机位运算效率高

4.不足

• 数据尽量不重复，如果重复，利用2bitmap
• 数据碰撞。比如将字符串映射到 BitMap 的时候会有碰撞的问题，那就可以考虑用 Bloom Filter 来解决，Bloom Filter 使用多个 Hash 函数来减少冲突的概率。
• 数据不够密集，稀疏的情况。又比如要存入(10,8887983,93452134)这三个数据，我们需要建立一个 99999999 长度的 BitMap ，但是实际上只存了3个数据，这时候就有很大的空间浪费，碰到这种问题的话，可以通过引入 Roaring BitMap 来解决。

转载地址：https://kerry.blog.csdn.net/article/details/110119182 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！