位图及其应用场景

in 算法 with 0 comment

定义

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

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

数据结构

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

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

问题实例

位图法搜索和排序

基本原理及要点

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

海量数据排序

只需三步

  1. 初始化bit数组将所有的位都置为0。
  2. 读入每个整数来建立集合,将每个对应的位置都置为1。
  3. 检验每一位,如果该为为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