理解BitMap算法的原理

前言

位图:一种常用的数据结构,代表了有限域中的稠集(dense set),每一个元素至少出现一次,没有其他的数据和元素相关联。在索引,数据压缩,海量数据处理等方面有广泛应用。

BitMap 的思想的和原理是很多算法的基础,比如 Bloom Filter、Counting Bloom Filter。

BitMap的原理

BitMap 的基本原理就是用一个 bit 位来存放某种状态,适用于大规模数据,但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的。

举个例子在Java里面一个int类型占4个字节,也就是4*8=32bit,大多数时候我们一个int类型仅仅表示一个整数,但其实如果映射成位存储的话,一个int类型是可以存储32个bit状态的。

也就是说使用1G的内存,换算成bit=1024 * 1024 * 1024 * 8约等于86亿个bit,注意换算的方式GB=>MB=>KB=>Byte=>Bit。如果存储int类型,能存储多少个?我们算下1024 * 1024 * 1024 / 4 约等于2亿6千万个int类型。

从上面的计算的结果来看,在面对海量数据的时候,如果能够采用bit存储,那么在存储空间方面可以大大节省。

在Java里面,其实已经有对应实现的数据结构类java.util.BitSet了,BitSet的底层使用的是long类型的数组来存储元素。

也就是说,假设我想排序或者查找的总数N=10000,那么,我申请的数组大小如下:

如果是int类型:int temp[]=new int[1+N/32],也就是312+1=313

如果是long类型:long temp[]=new long[1+N/64],也就是156+1=157

这里注意Java里面的整数除法是向下取整的,所以数组长度还需要加上1.

这里以int为例,生成的bitmap表如下:

其实申请一个int一维数组,那么可以当作为列为32位的二维数组。先通过对32进行相除,得到数组下标,然后将十进制转成二进制之后,进行移位计算,用来代表状态。

下面,我们来看一个排序场景,定义一个元素不重复的数组。

输出:

第一行的64,是代表当前的bit数,因为是long类型,而数组里面的最大值没有超过63,所以其实只用一个long类型就能处理上面的排序。

看到这里,如果熟悉排序算法里面计数排序,那么我们就能发现原理非常类似,不同的是使用bitmap排序占用的存储空间更小,但缺点是不支持重复数字。

来看一下关于BitMap算法一些处理大数据问题的场景:

(1)给定40亿个不重复的 int的整数,没排过序的,然后再给一个数,如何快速判断这个数是否在那40亿个数当中。

解法:遍历40亿数字,映射到BitMap中,然后对于给出的数,直接判断指定的位上存在不存在即可。

(2)使用位图法判断整形数组是否存在重复

解法:遍历一遍,存在之后设置成1,每次放之前先判断是否存在,如果存在,就代表该元素重复。

(3)使用位图法进行元素不重复的整形数组排序

解法:遍历一遍,设置状态1,然后再次遍历,对状态等于1的进行输出,参考计数排序的原理。

(4)在2.5亿个整数中找出不重复的整数,注,内存不足以容纳这2.5亿个整数

解法1:采用2-Bitmap(每个数分配2bit,00表示不存在,01表示出现一次,10表示多次,11无意义)。

解法2:采用两个BitMap,即第一个Bitmap存储的是整数是否出现,接着,在之后的遍历先判断第一个BitMap里面是否出现过,如果出现就设置第二个BitMap对应的位置也为1,最后遍历BitMap,仅仅在一个BitMap中出现过的元素,就是不重复的整数。

解法3:分治+Hash取模,拆分成多个小文件,然后一个个文件读取,直到内存装的下,然后采用Hash+Count的方式判断即可。

该类问题的变形问题,如已知某个文件内包含一些电话号码,每个号码为8位数字,统计不同号码的个数。8位最多99 999 999,大概需要99m个bit,大概10几m字节的内存即可。 (可以理解为从0-99 999 999的数字,每个数字对应一个Bit位,所以只需要99M个Bit==12MBytes,这样,就用了小小的12M左右的内存表示了所有的8位数的电话)

BitMap的一些缺点:

(1)数据碰撞。比如将字符串映射到 BitMap 的时候会有碰撞的问题,那就可以考虑用 Bloom Filter 来解决,Bloom Filter 使用多个 Hash 函数来减少冲突的概率。

(2)数据稀疏。又比如要存入(10,8887983,93452134)这三个数据,我们需要建立一个 99999999 长度的 BitMap ,但是实际上只存了3个数据,这时候就有很大的空间浪费,碰到这种问题的话,可以通过引入 Roaring BitMap 来解决。

总结

本文主要介绍了BitMap算法的基本原理和应用案例,其本质上是采用了bit位来表示元素状态,从而在特定场景下能够极大的节省存储空间,非常适合对海量数据的查找,判重,删除等问题的处理。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20181025B1R79600?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券