浅谈BitMap

BitMap就是用一个bit位来标记某个元素对应的value，而key即是这个元素。由于采用bit为单位来存储数据，因此在可以大大的节省存储空间。

 

1) BitMap的算法思想

32位机器上，一个整形int在内存中占32bit，可以用对应的32个bit位来表示十进制的0-31个数，BitMap算法利用这种思想处理大量数据的排序与查询。

 

2) BitMap的优点

①　效率高，不许进行比较和移位。

②　占用内存少，如N=10000000;只需占用内存为N/8 = 1250000Bytes = 1.2M，如果采用int数组存储，则需要1.2M * 32即38.4M。

 

3) BitMap的缺点

无法对存在重复的数据进行排序和查找。

 

4) map映射表

假设需要排序或查找的总数N，那么需要申请的内存空间为int a[N/32 + 1]。

其中a[0]在内存中占32位，依此类推，BitMap表为：

a[0] --> 0 - 31

a[1] --> 32 - 63

a[2] --> 64 - 95

......

 

5) 将十进制数转换为对应的bit位的位移转换

①　求N对应的在数组a中的下标：N / 32。

②　求N对应的bit位：N % 32。

③　利用移位0-31使得对应的bit位为1。