使用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;
    }
}