使用bitmap主要是可以减少存储空间的使用,用一个bit来存储一个元素的状态。当我们需要在一亿个数中判断某个数是否存在时,我们不需要将这一亿个数同时放入内存。
首先有一个bit数组,如果我们排序的所有元素中最大的数是一亿,那么我们就需要这个数组大小初始化为一亿零一(加上0),从0排到一亿,每一位bit就对应这个数,比如第6个bit位对应数字5的状态,如果是1表示待排序中存在5,是0,,则表示待排序数组中没有5。当我们使用待排序数组完成对bitmap的填充之后,只需要按位输出存在的数就可以了。
/**
* created by tianfeng on 2018/11/9
* 使用bitmap进行排序(待排序数组中无重复数字)
*/
public class BitmapSort {
private int maxNumber;
private int[] bitmap;
public void sort(int[] array){
for (int i = 0;i<array.length;i++){
int number = array[i];
int bit = number>>5;
int index = number&((1<<5)-1);
bitmap[bit] |= 1<<index;
}
for (int i=0;i<bitmap.length;i++){
for (int j = 0;j<32;j++){
if ((bitmap[i]&(1<<j))!=0){
System.out.print(i*32+j+" ");
}
}
}
}
public BitmapSort(int maxNumber){
this.maxNumber = maxNumber;
bitmap = new int[(maxNumber>>5)+1];
}
public static void main(String[] args) {
BitmapSort bitmapSort = new BitmapSort(88);
int[] array = {88,86,45,65,78,75,12,35,24,5,1,23};
bitmapSort.sort(array);
}
}
如果待排序中有重复的数字,就会只输出一个,这个问题不知道有没有解决的办法,也许可以用多个位表示一个数,但多少个是个多哇。这个问题谁知道告告我嘿嘿。不过也因为bitmap的这个特点——重复的数字只出现一次,我们可以使用同样的代码对一堆数字进行去重操作。
一个文件里有一亿个数,我们如何判断88是否存在其中?简单就是遍历一遍,但是如果内存不够呢?如果数是int型,占4个byte,一亿个数就是400M,如果十亿个数呢?4个G。把四个G的数都放入内存,才能完成这个遍历。如果内存不够呢?我们就可以采用bitmap,记录十亿个数的状态,我们只需要十亿个bit,也就是125M。
public class IsNumberExist {
private int[] bitmap;
private int size;
private int SHIFT = 5;//2的5次方是32
public boolean isNumberExist(int number){
int bit = number>>SHIFT;
int index = number&((1<<SHIFT)-1);
return ((1<<index)&bitmap[bit])!=0;
}
public IsNumberExist(int size){
this.size = size;
bitmap = new int[(size>>SHIFT)+1];
}
public void insertDate(int number){
int bit = number>>SHIFT;
int index = number&((1<<SHIFT)-1);
bitmap[bit] = bitmap[bit]|(1<<index);
}
public void insertFromTxt(String filename){
try {
BufferedReader br = new BufferedReader(new FileReader(filename));
String str = null;
while ((str = br.readLine())!=null){
insertDate(Integer.valueOf(str));
}
br.close();
} catch (IOException e) {
e.printStackTrace();
}
}
public static void main(String[] args) {
Runtime rt = Runtime.getRuntime();
System.out.println("当前JVM所占内存:"+(rt.totalMemory()-rt.freeMemory())/1024/1024+"M");
IsNumberExist tool = new IsNumberExist(1000000000);
System.out.println("当前JVM所占内存:"+(rt.totalMemory()-rt.freeMemory())/1024/1024+"M");
//Date.makeNumbers(100000000);//生成一亿个数到number.txt
tool.insertFromTxt("numbers.txt");//使用这个一亿个数初始化bitmap的状态
System.out.println(tool.isNumberExist(88888888));//判断88888888是否在这个文件中
System.out.println(tool.isNumberExist(99999999));//判断99999999是否在这个文件中
System.out.println(tool.isNumberExist(91725151));//判断91725151是否在这个文件中
}
}
生成数据的类:
public class Date {
public static boolean makeNumbers(int size){
boolean flag = true;
Random random = new Random();
try {
BufferedWriter bw = new BufferedWriter(new FileWriter("numbers.txt"));
for (int i = 0;i<size;i++){
bw.write(String.valueOf(Math.abs(random.nextInt(size))));
bw.newLine();
}
bw.close();
} catch (IOException e) {
flag = false;
e.printStackTrace();
}
return flag;
}
}