BitMap算法

转载： BitMap算法

基本思想

所谓的BitMap就是用一个bit位来标记某个元素所对应的value，而key即是该元素，由于BitMap使用了bit位来存储数据，因此可以大大节省存储空间。

BitMap应用

  1. 可进行数据的快速查找，判断，删除，一般来说数据范围是int的10倍以下。
  2. 去重数据而达到压缩数据
  3. 还可以用于爬虫系统中URL去重，解决全组合问题。

BitMap应用：排序示例

假设我们要对0-7内的5个元素（4，7，2，5，3）排序（这里假设这些元素没有重复）。那么我们就可以采用BitMap的方法来达到排序的目的。要表示8个数，我们就只需要8个bit（1Byte），首先我们开辟1Byte的空间，将这些空间的所有bit位都置为0，如下图：

bitmap_0

然后遍历这5个元素，首先第一个元素是4，那么就把4对应的位置置1（可以这样操作p+(i/8)|(0x01<<(i%8)），当然了这里的操作设计到Big-ending和Little-ending的情况，这里默认为Big-ending。不过计算机一般都是小端存储的，如intel。（小端的话就是讲倒数第5位置1），因为是从零开始的，所以要把第5位置为1，如下图：

bitmap_1

然后再处理第二个元素7，讲第8位置为1，接着再处理第三个元素，一直到最后处理完所有的元素，将相应的位置为1，这时候的内存的bit位的状态如下：

bitmap_2

然后我们现在遍历一遍bit区域，将该位是1的位的编号输出（2，3，4，5，7），这样就达到了排序的目的。

BitMap排序复杂度分析

BitMap排序需要的时间复杂度和空间复杂度依赖于数据中最大的数字。

BitMap排序的时间复杂度不是O(N)的，而是取决于待排序数组中的最大值MAX，在实际应用上关系也不大，比如我开10个线程去读byte数组，那么复杂度为：O(MAX/10)。也就是，要是读取的，可以用多线程的方式去读取。时间复杂度方面也是O(Max/n)，其中Max为byte[]数组的大小，n为线程大小。

空间复杂度应为O(MAX/8)bytes。

BitMap算法流程

假设需要排序或者查找的最大数MAX=10000000，那么我们需要申请内存空间的大小为int a[1 + MAX/32]。

其中：a[0]再内存中占32位可以对应十进制数0-31，以此类推：

bitmap表为：

a[0] ———-> 0-31

a[1] ———-> 32-63

a[2] ———-> 64-95

a[3] ———-> 96-127

……….

我们要把一个整数N映射到BitMap中去，首先要确定把这个N Mapping到哪一个数组元素中，即确定映射元素的index。我们用int类型的数组作为map的元素，这样我们就知道了一个元素能够表示的数字个数（这里是32）。于是N/32就可以知道我们需要映射的key了。所以余下来的那个N%32就是要映射到的位数。

*1. 求十进制数对应在数组a中的下标： *

先由十进制数n转换为与32的余可转化为对应在数组a中的下标。

如十进制数0-31，都应该对应在a[0]中，不如n=24，那么n/32=0，则24对应在数组a中的下标为0。又比如n=60，那么n/32=1，则60对应在数组a中的下标为1，同理可以计算0-N在数组a中的下标。

i = N >> K

2.求十进制数对应数组元素a[i]在0-31中的为m：

十进制数0-31就对应0-31，而32-63则对应也是0-31，即给定一个数n可以通过mod32求得对应0-31中的数。

m = n & ((1 << K) - 1)

3.利用以为0-31使得对应第m个bit位为1

如a[i]的第m位置1：a[i] = a[i] | (1 << m)

BitMap算法评价

优点：

  1. 运算效率高，不进行比较和移位；
  2. 占用内存少，比如最大的数MAX=10000000；只需要占用内存为MAX/(8*1024 * 1024) = 1.25M。

缺点：

  1. 所有的数据不能重复，即不可对重复的数据进行排序。
  2. 当数据类似(1,1000,100000)只有3个数据的时候，用BitMap时间复杂度和空间复杂度相当大，只有当数据比较密集时才有优势。

最后更新： 2019年10月17日 16:56

原始链接： freesdw.github.io/2019/10/17/BitMap算法/

赏
× 请我吃巧克力吧
打赏二维码