Bitmap实现原理&应用场景

Bitmap是什么？

用内存中连续的二进制位（bit），用0或1标识数据是否存在。

长度为10的bitmap，1，2，3，4 在bitmap中存在。

Bitmap实现

1、字符串

    数值对应字符串的下标、二进制位0，1表示是否存在。（01组成的字符串）

    问题：

        非单调递增字符串长度过大。

2、数组

java中 int类型4byte=32 bit，new int[32] 占32*32bit。

用int的每一位标识一个数字，1个int类型可以表示32的数字。

思路：

个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表示为：

如何判断int数字8在tmp数组的哪个下标index？

    通过直接除以32取整数部分-》  8/32=0 -》 tmp[0]

我们如何知道了8在tmp[0]中的32个位中的哪个位？

在tmp[0]中的第 8mod32=8。数字8就在tmp[0]中的第8个bit位（从右边数起）

Bitmap应用场景

1、在3亿个整数中找出不重复的整数，限制内存不足以容纳3亿个整数。

BitMap小小变种:2-BitMap。

为每个整数分配2bit，用不同的0、1组合来标识特殊意思，

00表示此整数没有出现过、01表示出现一次、11表示出现过多次，就可以找出重复的整数了，

需要的内存空间是正常BitMap的2倍，为：3亿*2/8/1024/1024=71.5MB。

具体的过程如下：

扫描着3亿个整数，组BitMap。

查看BitMap中的对应位置，如果00则变成01，是01则变成11，是11则保持不变，

将3亿个整数扫描完之后也就是说整个BitMap已经组装完毕。最后查看BitMap将对应位为11的整数输出即可。

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

8位最多99 999 999，（可以理解为从0-99 999 999的数字，每个数字对应一个Bit位，所以只需要99M个Bit==1.2MBytes，这样，就用了小小的1.2M左右的内存表示了所有的8位数的电话）

3、用户标签存储

思路：每个标签（eg：程序员） --》bitMap（存的是用户对应的uid）

业务逻辑的处理思路：

and 关系用&运算 、or的关系用 | 运算 、bitMap不支持非运算（如果要求非的情况，通过遍历全量用户然后进行异或操作）

    

4、布隆过滤器 (Bloom Filter) ，它就是专门用来解决这种去重问题的。

描述：Bloom Filter 反馈不存在的值一定不存在、反馈存在值可能不存在。存在一定概率的误判

原理：

（1）通过一系列的hash算法，得到key的hash值。在位数组中标识为1。

（2）判断key是否存在如果所有hash运算反馈的位数组结论都是 1 那么存在。如果有一个反馈是0 说明这个值不存在。

这也说明了为什么布隆过滤器可以精确的知道反馈不存在的值