Java BitMap源码仿写实现
洋圏外の彼女 人气:0bitmap的作用:
用来校验海量数字中某一个数字有没有出现过,海量数据中某一个数据有没有出现过
做一个长的比特数组,比特数组就会出现索引(0n),所有0n之间的数,比如123,就把所有比特数组中索引为123的位置,由0变为1;看这个数有没有出现在比特数组中,看是0还是1;0没有出现过,1出现过;
(getIndex()方法)byte数组中每一个都代表八位;做value>>3只是确定了0,1,2,3,4,5的位置,但是不知道在里边的空里是多少;
getPosition()方法:决定了在后面1~8中的哪个位置
private int getPosition(int value){ // return value%8; return value & 0x07; }
byte[] bits = new byte[2];
比如说:添加13
13/8 = 1;确定了索引为1的一行的内容
13>>3; 13的二进制数是:1101 - - - > 0001
13%8 = 5;确定了是在此行的第五个位置
13 & 0x07
13 = 1101
0x07 = 0111
与操作= 0101
所以说13的位置 bits[13>>3] | 1<<(13&0x07)
1<<(13&0x07) = 1 << 5 = 0001 << = 00100000
假如说原来就是0 :00000000
或操作:00100000
package com.BitMap; import java.util.HashSet; import java.util.Random; import java.util.Set; public class MyBitMap { private byte[] bits; //byte数组中每一个数字都要代表八位 public static final int DEFAULT_CAPACITY = 1<<10;//最大容量是1左移10位 public MyBitMap(){ this.bits = new byte[DEFAULT_CAPACITY]; //System.out.println(bits.length);//输出一下1左移10位的数字是多少 } public static void main(String[] args) { MyBitMap map = new MyBitMap(); Set<Integer> set = new HashSet<Integer>(); Random random = new Random(); for (int i = 0 ;i<800;i++){ int i1 = random.nextInt(DEFAULT_CAPACITY); map.add(i1); set.add(i1); } for (int i = 100; i < 300; i++) { boolean contains = map.contains(i); if (contains){ //用已知的set 来确定这个Map写的没问题 if (set.contains(i)){ System.out.print(i + " is contains by set!!! "); } System.out.println(i + " is contains!!! "); } else { if (!set.contains(i)){ System.out.print((i + " is not contains by set !!!")); } System.out.println(i + " is not contains!"); } } } public void add(int value){ //找到value值在byte数组中的位置是在哪里 int index = getIndex(value); //求余 int position = getPosition(value); bits[index] |=1<<position; } public boolean contains(int value){ int index = getIndex(value); int position = getPosition(value); return (bits[index] & 1<<position) != 0; } private int getPosition(int value){ // return value%8; return value & 0x07; } //找到value值当前所在数组中的位置 private int getIndex(int value){ // return value/8; return value>>3; //byte数组每个数字代表八位,除以8就可以得到数组里边的位置 } }
加载全部内容