一.BitMap
BitMap算法流程
假设需要排序或者查找的最大数MAX=10000000（lz:这里MAX应该是最大的数而不是int数据的总数！），那么我们需要申请内存空间的大小为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映射到Bit-Map中去，首先要确定把这个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 % 结果就是N/(2^K)
Note: map的范围是[0, 原数组最大的数对应的2的整次方数-1]。
2.求十进制数对应数组元素a[i]在0-31中的位m（取余确定小下标）：
十进制数0-31就对应0-31，而32-63则对应也是0-31，即给定一个数n可以通过模32求得对应0-31中的数。
m = n & ((1 << K) - 1) %结果就是n%(2^K)
3.利用移位0-31使得对应第m个bit位为1（按位置1、0）
如a[i]的第m位置1：a[i] = a[i] | (1<<m)
如：将当前4对应的bit位置1的话，只需要1左移4位与B[0] | 即可。同理将int型变量a的第k位清0，即a=a&~(1<<k)
BitMap算法评价
优点：
1. 运算效率高，不进行比较和移位；
2. 占用内存少，比如最大的数MAX=10000000；只需占用内存为MAX/8=1250000Byte=1.25M。
缺点：
1. 所有的数据不能重复，即不可对重复的数据进行排序。（少量重复数据查找还是可以的，用2-bitmap，这种情况一般不是用来计数，而是用来判断“某个情况”是否出现过，00表示未出现过，01表示出现一次，10表示出现多次，11不合法）。
2. 当数据类似（1，1000，10万）只有3个数据的时候，用bitmap时间复杂度和空间复杂度相当大，只有当数据比较密集时才有优势。
为解决数据稀疏造成的bitmap空间浪费，设计了一种数据结构EWAHCompressedBitMap，参考文章：
应用实例
应用场景：快速排序（初始化过程即排序）；快速去重（初始化过程即去重，前提是1bit代表一个数据）；快速查找（某个数据是否存在、出现过1次or多次）
1. 使用位图法判断整形数组是否存在重复
首先，使用bitMap初始化后的数据是经过了去重处理的，所以用1bit来表示某个数的方式，可以达到去重的效果
如何判断某个数是否重复，可以采用用两个bit位代表一个数的方式，如下2中所示。
2. 在2.5亿个整数中找出不重复的整数，注，内存不足以容纳这2.5亿个整数
将bit-map扩展一下，采用2-Bitmap（每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，11无意义）进行，共需内存2^32 * 2 bit=1 GB内存，还可以接受。然后扫描这2.5亿个整数，查看Bitmap中相对应位，如果是00变01，01变10，10保持不变。所描完事后，查看bitmap，把对应位是01的整数输出即可。
3. 一个序列里除了一个元素，其他元素都会重复出现3次，设计一个时间复杂度与空间复杂度最低的算法，找出这个不重复的元素。
这个看数据量，小的话直接set处理即可，大的话使用bitmap，道理同2
4. 已知某个文件内包含一些电话号码，每个号码为8位数字，统计不同号码的个数。
8位最多99 999 999，大概需要99m个bit，大概10几m字节的内存即可。 （可以理解为从0-99 999 999的数字，每个数字对应一个Bit位，所以只需要99M个Bit==1.2MBytes，这样，就用了小小的1.2M左右的内存表示了所有的8位数的电话）
5. 给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中？
解析:bitmap算法就好办多了。申请512M的内存，一个bit位代表一个unsigned int值，读入40亿个数，设置相应的bit位；读入要查询的数，查看相应bit位是否为1，为1表示存在，为0表示不存在。
Note: unsigned int最大数为2^32 - 1，所以需要2^32 - 1个位，也就是(2^32 - 1) / 8 /2^20G = 0.5G内存。
二.布隆过滤器
网友评论