在java中一个int类型占4个字节也就是32bit我们用一个int数组来表示时 new int[32],总计占用内存大概32*32bit,如果说我们存放的海量数据亿万级非常大那么这些基本数据类型都不够用的则可以用int字节码的每一位表示一个数字比如int类型32位可以存放0-31共32个数值那么32个数字只需要一个int类型所占内存空间大小就够了这样在大数据量的情况下会节省很多内存。

 一、位图作用

存放海量数据节省存储空间有明显优势

二、位图实现

一、思路分析

位图的定义我们大概了解就是通过定义一个整形数值后将原本只表示1个数值的情况下扩大了可以存放几十个数及以上的结构比如我们要存放0-63的数共64个数那么我们就定义一个long型变量有8个字节64位二进制就是64位那么每一位从左到右就可以表示012..,63如果有数则可以赋值1 没有则表示0 比如保存1那么就是第二位赋值1 以此类推

下面我们演示下传递一个数值保存到一个long[] arr数组中简单了解下:

arr[0]存放的值 0 - 63          

arr[1]存放的值 64 - 127

arr[2]存放的值 128 - 191

.....

num =4  存放的位置就是 arr[0] 第一个元素 因为 num /64 = 0 元素二进制 00..10000 第五位赋值1

 二、代码演示

package class05;

import java.util.HashSet;

public class Code02_BitMap2 {

	// 这个类的实现是正确的
	public static class BitMap {
		//定义long数组一个元素可以存放64个数因为long类型是8字节 64位
		private long[] bits;
		//定义数组长度需要先给需要存储的数集的最大值 (max+64/64) 表示需要多少个如 max是63 那个得 1 只需一个元素就可以
		//如果是64 得 2就需要2个元素 因为一个Long64位 存放0-63的数值 接着是64-127
		public BitMap(int max) { bits = new long[(max + 64) >> 6];}
		/*
		保存数值
		1.num>>6 表示先将目标数值除以64 得到该数值是位于bits数组的第几个比如63 / 64 = 0 在bit[0] 64/64=1 bit[1]..
		2.num & 63 表示num % 64 , 即看在该元素的第几位 2的6次方=64 第7位1000000 所以可以知道求模后肯定余数是1-6位的数
	      那么与运算 111111 即 63 就能表示1-6的值也就是余数也就得到是位于该元素中的第几位了 比如余数0 那么就是第一位 
	      1 就是第二位...  确定了这个余数 即第几位那么我们就用 1l << 余数(1必须要为long型 1L 取值长度才不会越界int是32位
	      所以右移63肯定位数不够)  将1右移余数位比如余数1 那么就1L右移一位表示在这个位置标1了。
	      3.前面得到了对应在第几个元素中的第几位最后就是需要在这个元素的这个位置赋值1. 那么就是可以将元素位置bits[num >>6] =
	       bits[num >>6] | (1L << (num & 64)  即或运算 前面得到的具体位置有1 则表示1 所以就给元素的对于位置赋值1了
		 */
		public void add(int num) {
			bits[num >> 6] |= (1L << (num & 63));
		}

		/*
		删除数值 就是将对应的元素中的第几位 将其1改成0
		1.bits[num >> 6] 元素所在数组的元素 1L << (num & 63) 64位元素中的第几位 表示存放着num
		2.对1L << (num & 63) 取反 就得到一个 1111...01111 即将存放位赋值0 其他为1
		3.将取反后的数 与bits[num >> 6] 所在元素就行 与运算 此时其他位都位1 与完元素不变而num所在位是0 与完则为0则
		表示将数组删除
		 */
		public void delete(int num) {
			bits[num >> 6] &= ~(1L << (num & 63));
		}

		/*
		判断数值是否包含那么就是判断 bits[num >> 6] 所在元素的(1L << (num & 63)) 所在位 进行与运算(1L << (num & 63))
		所在位为1 其他位都为0 所以与运算后 如果为一 表示bits[num >> 6] 的所在位也是1 那么就返回true
		 */
		public boolean contains(int num) {
			return (bits[num >> 6] & (1L << (num & 63))) != 0;
		}

	}

	public static void main(String[] args) {
		System.out.println("测试开始");
		int max = 10000;
		BitMap bitMap = new BitMap(max);
		HashSet<Integer> set = new HashSet<>();
		int testTime = 10000000;
		for (int i = 0; i < testTime; i++) {
			int num = (int) (Math.random() * (max + 1));
			double decide = Math.random();
			if (decide < 0.333) {
				bitMap.add(num);
				set.add(num);
			} else if (decide < 0.666) {
				bitMap.delete(num);
				set.remove(num);
			} else {
				if (bitMap.contains(num) != set.contains(num)) {
					System.out.println("Oops!");
					break;
				}
			}
		}
		for (int num = 0; num <= max; num++) {
			if (bitMap.contains(num) != set.contains(num)) {
				System.out.println("Oops!");
			}
		}
		System.out.println("测试结束");
	}

}

三、核心总结 

1. 定义数组长度需要先给需要存储的数集的最大值 (max+64/64) 表示需要多少个如 max是63 那个得 1 只需一个元素如果是64 得 2就需要2个元素 因为一个Long64位 存放0-63的数值 接着是64-127

2. num>>6 表示先将目标数值除以64 得到该数值是位于bits数组的第几个比如63 / 64 = 0 在bit[0]  64/64=1 bit[1]

3. num & 63 表示num % 64 , 即看在该元素的第几位 2的6次方=64 第7位1000000 所以可以知道求模后肯定余数是1-6位的数那么与运算 111111 即 63 就能表示1-6的值也就是余数也就得到是位于该元素中的第几位了 比如余数0 那么就是第一位 1 就是第二位... 

4. 确定了这个余数 即第几位那么我们就用 1l << 余数(1必须要为long型 1L 取值长度才不会越界int是32位所以右移63肯定位数不够)  将1右移余数位比如余数1 那么就1L右移一位表示在这个位置标1了。

5. 保存数值将对应位赋值1前面得到了对应在第几个元素中的第几位最后就是需要在这个元素的这个位置赋值1. 那么就是可以将元素位置bits[num >>6] =
    bits[num >>6] | (1L << (num & 64)  即或运算 前面得到的具体位置有1 则表示1 所以就给元素的对于位置赋值1了

6. 删除数值就是将对应的元素中的第几位 将其1改成0
   1.bits[num >> 6] 元素所在数组的元素 1L << (num & 63) 64位元素中的第几位 表示存放着num
   2.对1L << (num & 63) 取反 就得到一个 1111...01111 即将存放位赋值0 其他为1
   3.将取反后的数 与bits[num >> 6] 所在元素就行 与运算 此时其他位都位1 与完元素不变而num所在位是0 与完则为0则表示将数组删除

7. 判断数值是否包含那么就是判断 bits[num >> 6] 所在元素的(1L << (num & 63)) 所在位 进行与运算(1L << (num & 63))
   所在位为1 其他位都为0 所以与运算后 如果为一 表示bits[num >> 6] 的所在位也是1 那么就返回true