【算法&数据结构初阶篇】：位图bitMap

偏执的太偏执、 2024-03-29 16:07 77阅读 0赞

> 在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位，那么每一位从左到右就可以表示0，1，2..,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