定义

所谓的位图就是用一个bit位来标记某个元素对应的value，而key是该元素。

即将bit数组下标与应用中的一些值关联映射，bit数组中该下标所指定的位置上的元素可以用来标识应用中值的情况（是否存在或者数目或者计数等），位图数组中每个元素在内存中占用1位，所以可以节省存储空间。位图是一种非常简洁快速的数据结构，它能同时使存储空间和速度最优化，在海量数据处理，索引，数据压缩等方面有广泛应用。

数据结构

假如，我们要存储的数据范围为0-15，则我们只需要长度为16的bit数组就可以把数据存进去。如下图：

数据【5，1，7，15，0，4，6，10】存入这个结构中的情况为：

问题实例

位图法搜索和排序

基本原理及要点

使用bit数组来表示某些元素是否存在，比如8位电话号码。

海量数据排序

只需三步

初始化bit数组将所有的位都置为0。
读入每个整数来建立集合，将每个对应的位置都置为1。
检验每一位，如果该为为1，就输出对应的整数，有此产生有序的输出。

show code

    /**
     * 位图法对海量数据排序
     */
    public static void printSoredStr(int[] arr) {
        BitSet bs = new BitSet();
        for (int num : arr) {
            //将对应数据的位置设置true
            bs.set(num, true);
        }
        for (int i = 0; i < bs.length(); i++) {
            if (bs.get(i)) {
                System.out.print(i + ",");
            }
        }
    }

海量数据找重复数字

腾讯面试题：给40亿个不重复的unsinged int的整数，没排过序，然后再给出一个数，如何快速判断这个数是否在那40亿个数当中？

类似题目：
给你一堆电话号码列表，数量大概在千万级，要求从中找出所有重复的电话号码，需要时间复杂度尽可能小。
在2.5亿整数中找出不重复的整数，注，内存不足以容纳这2.5亿个整数？如果对2.5亿个数字排序，怎么办？

算一下40亿整数用bitmap来存储要多大存储空间：40*100000000/8/1024/1024=476.83M

show code

    /**
     * 位图法判断某数字是否存在（去重）
     */
    public static boolean findNumExist(int[] arr, int flag) {
        if (arr == null)
            return false;
        else {
            BitSet bs = new BitSet();
            for (int num : arr) {
                bs.set(num, true);
            }
            if (bs.get(flag)) {
                return true;
            }
            return false;
        }
    }


    /**
     * 利用位图法找出重复的数
     */
    public static void findRepeat(int[] arr) {
        if (arr != null) {
            BitSet bs = new BitSet();
            for (int i = 0; i < arr.length; i++) {
                if (bs.get(arr[i])) {
                    System.out.println("重复的数：" + arr[i]);
                } else {
                    bs.set(arr[i], true);
                }
            }
        } else {
            System.out.println("数组为空");

        }
    }

code验证

    public static void main(String[] args) {
        int[] arr = {1, 35, 65, 78, 34};
        printSoredStr(arr);
        int[] arr2 = {1, 35, 35, 65, 78, 34};
        System.out.println(findNumExist(arr, 35));
        findRepeat(arr2);
    }
//output:
1,34,35,65,78,true
重复的数：35