【位图】面对海量数据，如何压缩空间？定位数据？

红太狼 2023-09-23 22:00 69阅读 0赞

**目录**

一、腾讯面试题

二、解决办法——位图

2.1、那么什么是位图？

三、位图的模拟实现

3.1、位图的构造

3.2、存放数据

3.3、检测数据是否存在

3.4、设置某个数据的对应位为0

四、位图模拟代码（完整）

--------------------

# 一、腾讯面试题 #

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

> 思考：

思路一：没有学习位图之前，我们**一般最快能反应到使用哈希表的办法来解决**，但是是有40亿的整形数据，这是一个什么概念？一个整形占4个字节，**相当于要占用16G的内存空间，但生活中有多少电脑有这么大的内存空间**？就算你是16G内存，难道你打开编译器编写代码不占空间？所以这个想法显然走不通；

思路二： “排序+二分查找” 的办法来解决，时间复杂度上，排序最快也就是O(NlogN)，二分查找logN，但是依然面临一个问题——内存存不下，二分查找依然是在内存中查找，但是16G的数据都存不了，还查个...所以很难受，根本查不了；

# 二、解决办法——位图 #

我们可以这样规划空间，一个字节是32位，**可以把每一位都利用起来，也就是说，一个 bit位表示一个数字，32位用可以来存放32个不同的数字**，怎么存？可以通过映射的方式，1表示这意味数字存在，0表示不存在，具体的如下图：

![7dcdacc164e24a75a5b70aaa5ee7d6db.png][]

## 2.1、那么什么是**位图**？ ##

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

2.2、有什么**好处**？

——大大节省了空间

例如上述栗子，10个整数本来需要40个字节，而用位图表示只需要3个字节，那么40亿个整数就只占512M的大小了~

# 三、位图的模拟实现 #

## 3.1、位图的构造 ##

默认初始化为一个字节，当然要也可以手动指定，而且一般需要多给一个字节，具体原因在注释当中；

> 如下代码：

## 3.2、存放数据 ##

创建一个set方法用来存放数据，首先要先判断数据是否小于0，**若小于0就是不符合要求的，直接抛出异常；**

**怎么存放数据呢？**如下图：

![51462c0d8d7d4c32ada5c4694f1264a5.png][]

**最后还要注意，若数据过大，需要考虑扩容（否则会越界访问）；**

> 代码如下：

/**
         * 设置某一位为1(1为有效)
         * @param val
         */
        public void set(int val) {
            if(val < 0) {//必须是大于等于零的整数
                throw new IndexOutOfBoundsException();
            }
            //先确定val在elem的哪一个下标的哪一个bit位
            int arrayIndex = val / 8;
            //扩容
            if(arrayIndex > elem.length - 1) {
                elem = Arrays.copyOf(elem, arrayIndex + 1);
            }
            int bitIndex = val % 8;
            elem[arrayIndex] |= (1 << bitIndex);//不能是异或，会修改原来的值
            usedSize++;
        }

## 3.3、检测数据是否存在 ##

创建一个get方法，先检验val值是否小于零，小于直接抛异常，然后还是通过除8模8，左移1的方式确定位置，与 存放数据 不同， **这回使用 按位与，若按位与得到的数字为0，则说明原来这一位就是0，数字不存在，返回false，反之则存在，返回true**;

> 如下代码：

/**
         * 判断当前位是不是1
         * @param val
         * @return
         */
        public boolean get(int val) {
            if(val < 0) {//必须是大于等于零的整数
                throw new IndexOutOfBoundsException();
            }
            //先确定val在elem的哪一个下标的哪一个bit位
            int arrayIndex = val / 8;
            int bitIndex = val % 8;
    
            if((elem[arrayIndex] & (1 << bitIndex)) != 0) {
                return true;
            }
            return false;
        }

## 3.4、设置某个数据的对应位为0 ##

创建一个reSet方法，先检验val值是否小于零，小于直接抛异常；怎么设置为某一位为0呢，好像直接按位与、或、异或都不行，实际上我们可以这样做，按原来的方法，除8模8，左移1的方式确定位置，然后给这个数据取反，再 按位与等 这一字节，就可以了，如下图：

![4eed918a8c8f4c6e841b4ec929dee2fd.png][]

> 代码如下：

/**
         * 将对应位置 设置为0
         * @param val
         */
        public void reSet(int val) {
            if(val < 0) {//必须是大于等于零的整数
                throw new IndexOutOfBoundsException();
            }
            //先确定val在elem的哪一个下标的哪一个bit位
            int arrayIndex = val / 8;
            int bitIndex = val % 8;
    
            elem[arrayIndex] &= ~(1 << bitIndex);
            usedSize--;
        }

# 四、位图模拟代码（完整） #

public class MyBitSet {
        public byte[] elem;
        //记录当前位图中，存放了多少个有效数据
        public int usedSize;
    
        /**
         * 默认初始化位为一个字节
         */
        public MyBitSet() {
            this.elem = new byte[1];
        }
    
        /**
         * 指定构造方法中的初始化位数
         * 一般会多给一个字节，因为如果是12，那么12%8=4，不能整除，还多出来4个bit位
         * 所以多给一个也无所谓(不要那么抠)
         */
        public MyBitSet(int n) {
            this.elem = new byte[n / 8 + 1];
        }
    
        /**
         * 获取当前位图存储的数据量
         */
        public int getUsedSize() {
            return this.usedSize;
        }
    
    
        /**
         * 设置某一位为1(1为有效)
         * @param val
         */
        public void set(int val) {
            if(val < 0) {//必须是大于等于零的整数
                throw new IndexOutOfBoundsException();
            }
            //先确定val在elem的哪一个下标的哪一个bit位
            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
         * @return
         */
        public boolean get(int val) {
            if(val < 0) {//必须是大于等于零的整数
                throw new IndexOutOfBoundsException();
            }
            //先确定val在elem的哪一个下标的哪一个bit位
            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();
            }
            //先确定val在elem的哪一个下标的哪一个bit位
            int arrayIndex = val / 8;
            int bitIndex = val % 8;
    
            elem[arrayIndex] &= ~(1 << bitIndex);
            usedSize--;
        }
    
    }

--------------------

![95ab4216d2704bcfb3da2ed6a536b030.gif][]

[7dcdacc164e24a75a5b70aaa5ee7d6db.png]: https://img-blog.csdnimg.cn/7dcdacc164e24a75a5b70aaa5ee7d6db.png
[51462c0d8d7d4c32ada5c4694f1264a5.png]: https://img-blog.csdnimg.cn/51462c0d8d7d4c32ada5c4694f1264a5.png
[4eed918a8c8f4c6e841b4ec929dee2fd.png]: https://img-blog.csdnimg.cn/4eed918a8c8f4c6e841b4ec929dee2fd.png
[95ab4216d2704bcfb3da2ed6a536b030.gif]: https://img-blog.csdnimg.cn/95ab4216d2704bcfb3da2ed6a536b030.gif