BitMap

对无重复的数据进行排序

给定数据(2,4,1,12,9,7,6)如何对它排序?

方法1:基本的排序方法包括冒泡,快排等。
方法2:使用BitMap算法

方法1就不介绍了,
方法2中所谓的BitMap是一个位数组,跟平时使用的数组的唯一差别在于操作的是位。首先是开辟2个字节大小的位数组,
长度为12(该长度由上述数据中最大的数字12决定的),然后,读取数据,2存放在位数组中下标为1的地方,值从0改为1,4存放在下标为3的地方,值从0改为1….最后,读取该位数组,得到排好序的数据是:(1,2,4,6,7,9,12)。

比较方法1和方法2的差别:方法2中,排序需要的时间复杂度和空间复杂度很依赖与数据中最大的数字比如12,因此空间上讲需要开2个字节大小的内存,时间上需要遍历完整个数组。当数据类似(1,1000,10万)只有3个数据的时候,显然用方法2,时间复杂度和空间复杂度相当大,但是当数据比较密集时该方法就会显示出来优势。

对有重复的数据进行判重

数据(2,4,1,12,2,9,7,6,1,4)如何找出重复出现的数字?

首先是开辟2个字节大小的位数组,长度为12(该长度由上述数据中最大的数字12决定的,当读取完12后,当读取2的时候,发现数组中的值是1,则判断出2是重复出现的。

概述

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

思想

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

优点:
效率高,不许进行比较和移位
占用内存少,比如N=10000000;只需占用内存为N/8 = 1250000Bytes = 1.2M,如果采用int数组存储,则需要38M多

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

示例:

申请一个int型的内存空间,则有4Byte,32bit。输入 4, 2, 1, 3时:

在32位地址上加入4
URL

再加入2
URL

再加入1
URL

再加入3
URL

思想比较简单,关键是十进制和二进制bit位需要一个map映射表,把10进制映射到bit位上

假设需要排序或者查找的总数N=10000000,那么我们需要申请的内存空间为 int a[N/32 + 1].其中a[0]在内存中占32位,依此类推:

bitmap表为:

a[0] ——> 0 - 31

a[1] ——> 32 - 63

a[2] ——> 64 - 95

a[3] ——> 96 - 127

……

下面介绍用位移将十进制数转换为对应的bit位

位移转换
(1) 求十进制数0-N对应的在数组a中的下标

index_loc = N / 32即可,index_loc即为n对应的数组下标。例如n = 76, 则loc = 76 / 32 = 2,因此76在a[2]中。

(2)求十进制数0-N对应的bit位

bit_loc = N % 32即可,例如 n = 76, bit_loc = 76 % 32 = 12

(3)利用移位0-31使得对应的32bit位为1

References

[1] http://www.cnblogs.com/hxsyl/p/4176280.html
[2] https://mp.weixin.qq.com/s/_sXXWeb66G6iYEikVE1Kng