首先介绍作用:
可以解决海量数据的存在性问题,又不占用很多内存的前提下。
位图法的原理主要就是利用int类型数据,一个int类型数据是4个字节,一个字节8位,然后一个int数据利用自身字节位就可以表示0-31的数是否存在,bit位表示数值,位山0,1值表示这个数值是否存在。
所有的int类型数据一共有2^32/8 = 2^29 Byte约等于512MB(2^10=1KB 2^20 =1MB 2^30=1GB)表示所有的int类型数需要512MB,现在的计算机完全可以胜任,这些可以表示多少位数呢就是一个int可以表示32个数,32*2^32=2^37约等于10^11百亿级别;
具体方案
那么接下来我们只需要申请一个int数组长度为 int tmp[N/32+1]即可存储完这些数据,其中N代表要进行查找的总数(这里也就是2^32),tmp中的每个元素在内存在占32位可以对应表示十进制数0~31,所以可得到BitMap表:
tmp[0]:可表示0~31
tmp[1]:可表示32~63
tmp[2]可表示64~95
~~
假设这10亿int数据为:6,3,8,32,36,……,那么具体的BitMap表示为:
使用如何快速查找具体的是否存在:
(1). 如何判断int数字放在哪一个tmp数组中:将数字直接除以32取整数部分(x/32),例如:整数8除以32取整等于0,那么8就在tmp[0]上;
(2). 如何确定数字放在32个位中的哪个位:将数字mod32取模(x%32)。上例中我们如何确定8在tmp[0]中的32个位中的哪个位,这种情况直接mod上32就ok,又如整数8,在tmp[0]中的第8 mod上32等于8,那么整数8就在tmp[0]中的第八个bit位(从右边数起)。
对于多次出现的数据处理方法
然后我们怎么统计只出现一次的数呢?每一个数出现的情况我们可以分为三种:0次、1次、大于1次。也就是说我们需要用2个bit位才能表示每个数的出现情况。此时则三种情况分别对应的bit位表示是:00、01、11
我们顺序扫描这10亿的数,在对应的双bit位上标记该数出现的次数。最后取出所有双bit位为01的int型数就可以了。