BitMap的原理和实现

在java中: 

byte  ->   8 bits  -->1字节
char  ->   16 bit  -->2字节
short ->   16 bits -->2字节
int   ->   32 bits -->4字节
float ->   32 bits -->4字节
long  ->   64 bits -->8字节

BitMap实现原理  

  在java中,一个int类型占32个比特,我们用一个int数组来表示new int[32],总计占用内存32*32bit,现假如我们用int字节码的每一位表示一个数字的话,那么32个数字只需要一个int类型所占内存空间大小就够了,这样在大数据量的情况下会节省很多内存。

 具体思路:

  1个int占4字节即4*8=32位,那么我们只需要申请一个int数组长度为 int tmp[1+N/32]即可存储完这些数据,其中N代表要进行查找的总数,tmp中的每个元素在内存在占32位可以对应表示十进制数0~31,所以可得到BitMap表:

    tmp[0]:可表示0~31

    tmp[1]:可表示32~63

    tmp[2]可表示64~95

    .......

  那么接下来就看看十进制数如何转换为对应的bit位:假设这40亿int数据为:6,3,8,32,35,......,那么具体的BitMap表示为:

BitMap的原理和实现

 如何判断int数字在tmp数组的哪个下标,这个其实可以通过直接除以32取整数部分,例如:整数8除以32取整等于0,那么8就在tmp[0]上。另外,我们如何知道了8在tmp[0]中的32个位中的哪个位,这种情况直接mod上32就ok,又如整数8,在tmp[0]中的第8 mod上32等于8,那么整数8就在tmp[0]中的第八个bit位(从右边数起)。

/**
 * @author sowhat
 * @create 2020-08-20 19:30
 */
public class BitMap
{
	private long length;
	private static int[] bitsMap;
	private static final int[] BIT_VALUE = {0x00000001, 0x00000002, 0x00000004, 0x00000008, 0x00000010, 0x00000020,
			0x00000040, 0x00000080, 0x00000100, 0x00000200, 0x00000400, 0x00000800, 0x00001000, 0x00002000, 0x00004000,
			0x00008000, 0x00010000, 0x00020000, 0x00040000, 0x00080000, 0x00100000, 0x00200000, 0x00400000, 0x00800000,
			0x01000000, 0x02000000, 0x04000000, 0x08000000, 0x10000000, 0x20000000, 0x40000000, 0x80000000};

	public BitMap(long length)
	{
		this.length = length;
		/**
		 * 根据长度算出,所需数组大小
		 * 当 length%32=0 时大小等于 = length/32
		 * 当 length%32>0 时大小等于 = length/32+l
		 */
		bitsMap = new int[(int) (length >> 5) + ((length & 31) > 0 ? 1 : 0)];
	}

	/**
	 * @param n 要被设置的值为n
	 */
	public void setN(long n)
	{
		if (n < 0 || n > length)
		{
			throw new IllegalArgumentException("length value " + n + " is  illegal!");
		}
		// 求出该n所在bitMap的下标,等价于"n/5"
		int index = (int) n >> 5;
		// 求出该值的偏移量(求余),等价于"n%31"
		int offset = (int) n & 31;
		/**
		 * 等价于
		 * int bits = bitsMap[index];
		 * bitsMap[index]=bits| BIT_VALUE[offset];
		 * 例如,n=3时,设置byte第4个位置为1 (从0开始计数,bitsMap[0]可代表的数为:0~31,从左到右每一个bit位表示一位数)
		 * bitsMap[0]=00000000 00000000 00000000 00000000  |  00000000 00000000 00000000 00001000=00000000 00000000 00000000 00000000 00001000
		 * 即: bitsMap[0]= 0 | 0x00000008 = 3
		 *
		 * 例如,n=4时,设置byte第5个位置为1
		 * bitsMap[0]=00000000 00000000 00000000 00001000  |  00000000 00000000 00000000 00010000=00000000 00000000 00000000 00000000 00011000
		 * 即: bitsMap[0]=3 | 0x00000010 = 12
		 */
		bitsMap[index] |= BIT_VALUE[offset];

	}

	/**
	 * 获取值N是否存在
	 * @return 1:存在,0:不存在
	 */
	public int isExist(long n)
	{
		if (n < 0 || n > length)
		{
			throw new IllegalArgumentException("length value illegal!");
		}
		int index = (int) n >> 5;
		int offset = (int) n & 31;
		int bits = (int) bitsMap[index];
		return ((bits & BIT_VALUE[offset])) >>> offset;
	}

	public static void main(String[] args)
	{
		BitMap map = new BitMap(64);
		map.setN(6);
		map.setN(3);
		map.setN(8);
		map.setN(32);
		map.setN(35);
		System.out.println(map.isExist(34));

	}
}

BitMap应用

  1:看个小场景 > 在3亿个整数中找出重复>=2次的整数,限制内存不足以容纳3亿个整数。

  对于这种场景我可以采用2-BitMap来解决,即为每个整数分配2bit,用不同的0、1组合来标识特殊意思,如00表示此整数没有出现过,01表示出现一次,11表示出现过多次,就可以找出重复的整数了,其需要的内存空间是正常BitMap的2倍,为:3亿*2/8/1024/1024=71.5MB。

  具体的过程如下:

  扫描着3亿个整数,组BitMap,先查看BitMap中的对应位置,如果00则变成01,是01则变成11,是11则保持不变,当将3亿个整数扫描完之后也就是说整个BitMap已经组装完毕。最后查看BitMap将对应位为11的整数输出即可。

  2:已知某个文件内包含一些电话号码,每个电话号码为8位数字,统计不同号码的个数。

  8位最多99 999 999,大概需要99百万个bit,大小= 99 999 999/8/1024/1024 =12M。 (可以理解为从0-99 999 999的数字,每个数字对应一个Bit位,所以只需要99百万个Bit==1.2MBytes,这样,就用了小小的12M左右的内存表示了所有的8位数的电话)。

 另一种方式分析BitMap

 一、问题引入  

  bitMap是位图,其实准确的来说,翻译成基于位的映射,举一个例子,有一个无序有界int数组{1,2,5,7},初步估计占用内存4*4=16字节,这倒是没什么奇怪的,但是假如有10亿个这样的数呢,10亿*4字节/(1024*1024*1024)=3.72G左右(1GB=1024MB 、1MB=1024KB 、1KB=1024B 、1B=8b)。如果这样的一个大的数据做查找和排序,那估计内存也崩溃了,有人说,这些数据可以不用一次性加载,那就是要存盘了,存盘必然消耗IO。我们提倡的是高性能,这个方案直接不考虑。

 二、问题分析

  如果用BitMap思想来解决的话,就好很多,解决方案如下:
  一个byte是占8个bit,如果每一个bit的值就是有或者没有,也就是二进制的0或者1,如果用bit的位置代表数组值有还是没有, 那么0代表该数值没有出现过,1代表该数组值出现过。不也能描述数据了吗?具体如下图:

BitMap的原理和实现

  是不是很神奇,那么现在假如10亿的数据所需的空间就是3.72G/32了吧,一个占用32bit的数据现在只占用了1bit,节省了不少的空间,排序就更不用说了,一切显得那么顺利。这样的数据之间没有关联性,要是读取的,你可以用多线程的方式去读取。时间复杂度方面也是O(Max/n),其中Max为byte[]数组的大小,n为线程大小。

 三、应用与代码
  如果BitMap仅仅是这个特点,还不是它的优雅的地方,接下来继续欣赏它的魅力所在。下面的计算思想其实就是针对bit的逻辑运算得到,类似这种逻辑运算的应用场景可以用于权限计算之中。

  再看代码之前,我们先搞清楚一个问题,一个数怎么快速定位它的索引号,也就是说搞清楚byte[index]的index是多少,position是哪一位。举个例子吧,例如add(14)。14已经超出byte[0]的映射范围,在byte[1]范围之类。那么怎么快速定位它的索引呢。如果找到它的索引号,又怎么定位它的位置呢。Index(N)代表N的索引号,Position(N)代表N的所在的位置号。

  Index(N) = N/8 = N >> 3;
  Position(N) = N%8 = N & 0x07;

 (1) add(int num)
  你要向bitmap里add数据该怎么办呢,不用担心,很简单,也很神奇。
  上面已经分析了,add的目的是为了将所在的位置从0变成1.其他位置不变.

BitMap的原理和实现

public void add(int num){
        // num/8得到byte[]的index
        int arrayIndex = num >> 3; 
        
        // num%8得到在byte[index]的位置
        int position = num & 0x07; 
        
        //将1左移position后,那个位置自然就是1,然后和以前的数据做|,这样,那个位置就替换成1了。
        bits[arrayIndex] |= 1 << position; 
}

(2) clear(int num)

  对1进行左移,然后取反,最后与byte[index]作与操作。

BitMap的原理和实现

public void clear(int num){
        // num/8得到byte[]的index
        int arrayIndex = num >> 3; 
        
        // num%8得到在byte[index]的位置
        int position = num & 0x07; 
        
        //将1左移position后,那个位置自然就是1,然后对取反,再与当前值做&,即可清除当前的位置了.
        bits[arrayIndex] &= ~(1 << position); 

}

(3) contain(int num)

public boolean contain(int num){ // num/8得到byte[]的index
        int arrayIndex = num >> 3; // num%8得到在byte[index]的位置
        int position = num & 0x07; //将1左移position后,那个位置自然就是1,然后和以前的数据做&,判断是否为0即可
        return (bits[arrayIndex] & (1 << position)) !=0; 
}

全部代码:

public class BitMap {
    //保存数据的
    private byte[] bits;
    
    //能够存储多少数据
    private int capacity;
    
    
    public BitMap(int capacity){
        this.capacity = capacity;
        
        //1bit能存储8个数据,那么capacity数据需要多少个bit呢,capacity/8+1,右移3位相当于除以8
        bits = new byte[(capacity >>3 )+1];
    }
    
    public void add(int num){
        // num/8得到byte[]的index
        int arrayIndex = num >> 3; 
        
        // num%8得到在byte[index]的位置
        int position = num & 0x07; 
        
        //将1左移position后,那个位置自然就是1,然后和以前的数据做|,这样,那个位置就替换成1了。
        bits[arrayIndex] |= 1 << position; 
    }
    
    public boolean contain(int num){
        // num/8得到byte[]的index
        int arrayIndex = num >> 3; 
        
        // num%8得到在byte[index]的位置
        int position = num & 0x07; 
        
        //将1左移position后,那个位置自然就是1,然后和以前的数据做&,判断是否为0即可
        return (bits[arrayIndex] & (1 << position)) !=0; 
    }
    
    public void clear(int num){
        // num/8得到byte[]的index
        int arrayIndex = num >> 3; 
        
        // num%8得到在byte[index]的位置
        int position = num & 0x07; 
        
        //将1左移position后,那个位置自然就是1,然后对取反,再与当前值做&,即可清除当前的位置了.
        bits[arrayIndex] &= ~(1 << position); 

    }
    
    public static void main(String[] args) {
        BitMap bitmap = new BitMap(100);
        bitmap.add(7);
        System.out.println("插入7成功");
        
        boolean isexsit = bitmap.contain(7);
        System.out.println("7是否存在:"+isexsit);
        
        bitmap.clear(7);
        isexsit = bitmap.contain(7);
        System.out.println("7是否存在:"+isexsit);
    }
}

参考:

小灰说BitMap

 

上一篇:【jvm】06-new一个对象到底占了多少内存?


下一篇:python运维开发(十六)----Dom&&jQuery