【数据结构进阶】位图【有些资料叫做 bitMap】

位图【有些资料叫做 bitMap】

给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数
中。【腾讯】

10亿个字节 大约是1个G
10亿个整数 大约是4个G
40亿个整数 大约是16个G

解法一：
遍历，时间复杂度O(N)
解法二：
排序(O(NlogN))，利用二分查找: logN  面临问题就是 内存存不下。
解法三：
位图解决
数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比
特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在。

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jii4hfoL-1672123044376)(C:\Users\17512\AppData\Roaming\Typora\typora-user-images\1672119258004.png)]$

位图概念

所谓位图，就是用每一位来存放某种状态，适用于海量数据，整数，数据无重复的场景。通常是用来判
断某个数据存不存在的。

例如：

10个整数本应该存放需要40个字节，此时用位图只需要3个字节。

10亿个字节大概是0.9G，可看做是1G，10亿个比特位大概是119兆，看做128兆

位图的使用

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-LJKxz8LV-1672123044377)(C:\Users\17512\AppData\Roaming\Typora\typora-user-images\1672120946830.png)]$

public class Test {
    public static void main(String[] args) {
        int[] array = {1,2,3,10,4,18,13};
        BitSet bitSet = new BitSet();
        for (int i = 0; i < array.length; i++) {
            bitSet.set(array[i]);
        }
        //是否存在10
        System.out.println(bitSet.get(10));
    }
}

位图的实现

package bitsetdemo;

import java.util.Arrays;

/**
 * @author SunYuHang
 * @date 2022-12-27 14:03
 * @ClassName : MyBitSet  //类名
 */

public class MyBitSet {

    public byte[] elem;
    //记录当前位图当中 存在了多少个有效的数据
    public int usedSize;

    public MyBitSet() {
        this.elem = new byte[1];
    }

    /**
     *
     * @param n 多少位
     *          n = 12
     * 有可能会多给一个字节，但是无所谓。
     */
    public MyBitSet(int n) {
        this.elem = new byte[n/8+1];
    }

    /**
     * 设置某一位为 1
     * @param val
     */
    public void set(int val) {
        if(val < 0) {
            throw new IndexOutOfBoundsException();
        }
        int arrayIndex = val / 8 ;
        //扩容
        if(arrayIndex > elem.length-1) {
            elem = Arrays.copyOf(elem,arrayIndex+1);
        }
        int bitIndex = val % 8;

        elem[arrayIndex] |=  (1 << bitIndex); //不能进行异或

        usedSize++;
    }

    /**
     * 判断当前位  是不是1
     * @param val
     */
    public boolean get(int val) {
        if(val < 0) {
            throw new IndexOutOfBoundsException();
        }
        int arrayIndex = val / 8 ;
        int bitIndex = val % 8;

        if((elem[arrayIndex] & (1 << bitIndex)) != 0) {
            return true;
        }
        return false;
    }

    /**
     * 将对应位置 置为 0
     * @param val
     */
    public void reSet(int val) {
        if(val < 0) {
            throw new IndexOutOfBoundsException();
        }
        int arrayIndex = val / 8 ;
        int bitIndex = val % 8;
        elem[arrayIndex] &= ~(1 << bitIndex);
        usedSize--;
    }

    //当前位图中记录的元素的个数
    public int getUsedSize() {
        return usedSize;
    }

}

public class Test {
    public static void main(String[] args) {
        int[] array = {1,2,3,10,4,18,13};
        MyBitSet myBitSet = new MyBitSet();
        for (int i = 0; i < array.length; i++) {
            myBitSet.set(array[i]);
        }
        //是否存在10
        System.out.println(myBitSet.get(10));
    }
}