Java BitMap 和 Bloom Filter
Bit Map Bit-map用一个bit位来标记某个元素对应的Value, 而Key即是该元素。由于采用了Bit为单位来存储数据,因此在存储空间方面,可以大大节省。 假设我们要对0-7内的5个元素4,7,2,5,3排序(假设这些元素没有重复)。那么我们就可以采用Bit-map的方法来达到排序的目的。要表示8个数,我们就只需要8个Bit(1Bytes), 首先我们开辟1Byte的空间,将这些空间的所有Bit位都置为0,0 0 0 0 0 0 0 0. 然后遍历这5个元素,首先第一个元素是4,那么就把4对应的位置设为1, p+(i/8)|(0x01<<(i%8)), 这里默认为Big-ending, 0 0 0 0 1 0 0 0. 然后再处理第二个元素7,将第八位置为1,,接着再处理第三个元素,一直到最后处理完所有的元素,将相应的位置为1,这时候的内存的Bit位的状态0 0 1 1 1 1 0 1 遍历一遍Bit区域,把1的索引依次输出(2,3,4,5,7),这样就达到了排序的目的。 算法的关键是如何确定十进制的数映射到二进制bit位的map图。算法占用很少内存,比如N=10000000;只需占用内存为N/8=1250000Byte=1.25M。缺点是不能有重复数据。 Map映射表 假设需要排序或者查找的总数N=10000000,那么我们需要申请内存空间的大小为int a[1 + N/32],其中:a[0]在内存中占32位, 可以对应十进制数0-31,依次类推: bitmap表为: a[0]--------->0-31 a[1]--------->32-63 a[2]--------->64-95 a[3]--------->96-127 .......... 十进制数需要转换为对应的bit位 位移转换 将十进制数转换为对应的bit位, 申请一个int一维数组,作为32列的二维数组, int a[0] |0000000000000000000000000000000000000| int a[1] |0000000000000000000000000000000000000| ……………… int a[N] |0000000000000000000000000000000000000| 例如十进制0,对应在a[0]第一位: 00000000000000000000000000000001 求十进制0-N对应在数组a的索引:十进制0-31,对应a[0],先由十进制数n转换为与32的余可转化为对应在数组a中的索引0。比如n=24,那么 n/32=0,则24对应a[0]。又比如n=60, 那么n/32=1,则60对应a[1]。 求0-N对应0-31中的数:十进制0-31就对应0-31,而32-63则对应也是0-31,即给定一个数n可以通过模32求得对应0-31中的数。 利用移位0-31使得对应32bit位为1. 找到对应0-31的数为M, 左移M位:即2 ^ M, 置1....