bitmap详解

什么是bitmap

bitmap即位图，一种用bit存储数据的数据结构，主要用于数据的快速排序、去重和查询等操作，其优势在于可以在一个非常高的空间利用率下保存大量0-1状态。

比如Java中1个int类型数据就需要占用4Byte，但是4Byte（32bit）大小的位图可以存储32个数据。

bitmap怎么使用

存储原理

每个bit中数字为1则代表该bit对应的index存在，为0则不存在。下图中的bitmap表示1,3,5,7这四个数字存在，0,2,4,6这四个数字不存在。

存查数据

• 建：创建合适大小的bitmap，比如在JAVA中，需要查找的总数为$N=10000$，那么需要申请的内存空间大小为int a[1+N/32]​（1个int数据大小为4Byte，32bit），其中a[0]对应0-31，a[1]对应32-63，以此类推。
• 存：比如向bitmap中存数据x=35，计算x//31=1和x%31=4，将a[1]中第4个bit设为1。
• 查：和存类似，通过计算x//31和x%31的值找到目标bit，然后检查该bit处值为0还是1。

bitmap应用场景

1. 海量数据下验证目标数据是否存在。

2. 快速去重

   （1）判断正整形数组是否存在重复。

   （2）海量数据中查找不重复的正整数。

   ​ 解法1：采用2-bitmap，即每个数分配2个bit，00表示不存在，01表示出现1次，10表示多次，11无意义。

   ​ 解法2：使用2个bitmap，对于目标数据，先判断是否存在于第一个bitmap，若存在就设置第二个bitmap对应位置为1。

3. 快速排序，正整形数组的排序。

当然bitmap也存在一些缺点：

1. 数据碰撞，比如将字符串映射到bitmap中（不同字符串hash成同一个整数）。
2. 数据稀疏，比如存入（3,1232324,923122311）这三个数字，需要建立999999999长度的bitmap，造成了很大空间浪费。

扩展

java中的bitmap

JDK中BitSet类实现了位图这一数据结构，其内部数据使用long数组来存储。

• 构造方法

  • 有参构造：传入位图长度参数
  • 无参构造：默认长度为64bit。

• set方法

  • 单点set：set(int bitIndex)和set(int bitIndex, boolean value)分别表示设置指定bit为true和指定值value。
  • 范围set：set(int fromIndex, int toIndex)和set(int fromIndex, int toIndex, boolean value)，区别同上

• get方法：和set方法类似，分为单点get和范围get两种，范围get返回一个子集BitSet

• 与，或，异或，与非方法

  and(BitSet set) ， or(BitSet set)， xor(BitSet set)， andNot(BitSet set);

压缩BitMap

前面提到bitmap的一个缺点就是在数据稀疏是十分浪费空间，google开发的javaEWAH包中CompressedBitmap很好的解决了这个问题。 在EWAHCompressedBitmap中，也是采用long数组来保存数据，不过数组中的long数据分两类：

• Literal Word：存储真正的bit位
• Running Length Word：存储跨度信息

比如存储数据1和1亿时，EWAHCompressedBitmap中可能是这样的：

其中，中间那个long数据就属于Running Length Word，表示是前后两个long数据之间有1千万个0。同样地，如果有多个连续1出现，也可以将它们压缩到一起用一个long数据表示。

Bloom Filter

布隆过滤器（Bloom Filter）可以看做一个由bitmap和一系列hash函数两部分组成的数据结构。

• 存取原理

  
  如上图所示，如果将一个字符串存入过滤器中，首先使用一些列hash函数将其映射成整数，然后将bit数组中对应位置值设为1。如果要判断字符串是否存在，只需使用同样的hash函数，然后判断bit数组对应位置是否为1。

• 优点：占用空间少，效率高。

• 缺点：

  • 存在误判（因为hash函数不能保证一对一映射），可以通过增加hash函数个数，扩充bitmap大小缓解。
  • 删除困难（不同数据可能被映射成相同整数）。

• 用途：和bitmap用途类似

  • 判定数据是否存在：防止缓存穿透、垃圾邮件过滤、黑名单等功能；
  • 去重：比如爬给定网址的时候，对爬取过的URL去重

Redis中的bitmap

• 常用命令：setbit，getbit，bitcount，bittop
  • set/get：setbit key offset value，getbit key offset ，时间复杂度为O(1)
  • bitcount：bitcount key start end，统计某范围内值为1的bit数，时间复杂度O(n)
  • bittop：bittop operation destkey key，对不同bitmap进行位运算（and，or，not，xor），时间复杂度O(n)
• 应用场景： 适合需要保存状态信息（比如是否签到、是否登录…）并需要进一步对这些信息进行分析的场景。比如用户签到情况、活跃用户情况、用户行为统计（比如是否点赞过某个视频）。

参考资料

1. https://www.cnblogs.com/dragonsuc/p/10993938.html
2. https://www.jianshu.com/p/c4c5a00b40db
3. https://juejin.cn/post/6844903879201718280
4. https://javaguide.cn/cs-basics/data-structure/bloom-filter.html
5. https://javaguide.cn/database/redis/redis-questions-01/#bitmap