提示文章写完后目录可以自动生成如何生成可参考右边的帮助文档文章目录位图定义: 6的含义 6 等于 /64右移6位 等同于 除以64,也就是除以 2^6的意思取模运算 转化为 位运算a%b a(b-1) 且b1kk为整数位运算 比加减乘除,取模效率上高很多位图的实现1. 构造函数:2. add操作将对应的比特位置赋值为1bits[num 6] bits[num 6] | (1L (num 63));bits[num 6] | (1L (num 63));3. delete操作将对用的比特位置0操作4. contains操作判断对应的比特位是0不存在还是1存在总代码测试位图定义:位图就是用每一位来存放某种状态适用于大规模数据但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的。位图就是用每一位来存放某种状态适用于大规模数据但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的 6的含义 6 等于 /64右移6位 等同于 除以64,也就是除以 2^6的意思取模运算 转化为 位运算若满足b为2的整数次幂即b1kk为整数时可用一个特殊的小技巧将取模运算转化为位运算a%b a(b-1) 且b1kk为整数位运算 比加减乘除,取模效率上高很多位图的实现1. 构造函数:max 为需要存储的元素个数和// 这个类的实现是正确的publicstaticclassBitMap{privatelong[]bits;publicBitMap(intmax){bitsnewlong[(max64)6];}}一个long类型的数字,可以存64位数字(max 64) 6 看需要多少个long类型的数字2. add操作publicvoidadd(intnum){bits[num6]|(1L(num63));}num 6 判断是第几个long类型的区间取模64 等于 (num 63) 看 对应区间的 具体哪个位置上将对应的比特位置赋值为1位或运算bits[num 6] bits[num 6] | (1L (num 63));bits[num 6] | (1L (num 63));3. delete操作publicvoiddelete(intnum){bits[num6]~(1L(num63));}将对用的比特位置0操作4. contains操作publicbooleancontains(intnum){return(bits[num6](1L(num63)))!0;}判断对应的比特位是0不存在还是1存在总代码publicstaticclassBitMap{privatelong[]bits;publicBitMap(intmax){bitsnewlong[(max64)6];}publicvoidadd(intnum){bits[num6]|(1L(num63));}publicvoiddelete(intnum){bits[num6]~(1L(num63));}publicbooleancontains(intnum){return(bits[num6](1L(num63)))!0;}}测试publicstaticvoidmain(String[]args){System.out.println(测试开始);intmax10000;BitMapbitMapnewBitMap(max);HashSetIntegersetnewHashSet();inttestTime10000000;for(inti0;itestTime;i){intnum(int)(Math.random()*(max1));doubledecideMath.random();if(decide0.333){bitMap.add(num);set.add(num);}elseif(decide0.666){bitMap.delete(num);set.remove(num);}else{if(bitMap.contains(num)!set.contains(num)){System.out.println(Oops!);break;}}}for(intnum0;nummax;num){if(bitMap.contains(num)!set.contains(num)){System.out.println(Oops!);}}System.out.println(测试结束);}