如何快速判断几十亿个数中是否存在某个数

【腾讯面试题】

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

对于这个问题，在前面学习到的知识中，我们有两种方案进行解决：

​

1 遍历，时间复杂度O(N)

2 排序 + 二分查找，时间复杂度O(NlogN) + O(logN)

而对于40亿的无符号整数来说，我们计算一下将这些数组放在内存中需要多大的空间：

​

10亿个字节换算后需要0.93GB的内存(近似看作1GB) -->

​

10亿个整型则需要4GB的内存 -->

​

40亿个整型就需要16GB的内存！！！

​

我们16GB的电脑内存刚开机就已经占用了20%以上的内存，因此对于这种场景，上述两种方案明显不可取。此时就需要用到位图解决。

位图的概念

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

数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比 特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在。比如：

​

int arry[] = {0,3,4,6,11,17,21,23,10,,20}

原本int需要4个字节。10*4就是40个字节。换成位图存储则只需要3个字节即可。

如上例子，10个整数本应该存放需要40个字节，此时用位图只需要3个字节。而此时处理40亿个整型数据的问题也就迎刃而解了。

​

**预计：10亿数据int类型ID = 10亿 4字节 = 3.7G内存*

换成bitmap = 3.7G /32 =117mb内存

​

二、位图的实现

注意：模拟实现的位图只处理0和正整数数据

​

思路：一个字节有8个比特位，每个比特位只表示0和1。位图的关键就在于，对于每个字节，将其所有比特位用来表示对应的某些数存不存在。

例如：一个byte类型占一个字节，也就是8个比特位，则第一个byte用来表示0-7，第二个表示8-15，以此类推。

​

下面，我用byte数组的方式模拟实现了一个位图（Java中BitSet集合类中用的是long数组，为什么？）

import java.util.Arrays;
 
public class MyBitSet {
 
    byte[] elem;
    int usedSize;
 
    public MyBitSet() {
        elem = new byte[4];
    }
 
    //bits：elem数组需要存入的最大位数
    public MyBitSet(int bits) {
        elem = new byte[bits / 8 + 1];
    }
 
    //存入集合 -> 等价于将数据的对应位置为1
    public void set(int val) {
        if (val < 0) {
            throw new IndexOutOfBoundsException();
        }
        //判断是否需要扩容
        if (val >= elem.length * 8) {
            elem = Arrays.copyOf(elem, val / 8 + 1);
        }
        int arrayIndex = val / 8; //该数字在数组中应存入的位置
        int bitIndex = val % 8; //该数字在数组位置中应存入的比特位位置
        elem[arrayIndex] |= (byte) (1 << bitIndex);
        usedSize++;
    }
 
    //判断数字是否存在 -> 等价于检查数据的对应位置是否为1
    public boolean get(int val) {
        if (val < 0) {
            throw new IndexOutOfBoundsException();
        }
        int arrayIndex = val / 8;
        //如果下标超过数组元素个数，一定不存在
        if (arrayIndex >= elem.length) {
            return false;
        }
        int bitIndex = val % 8;
        //逻辑& 如果结果不为0，说明当前bitIndex位置为1，否则为0
        return (elem[arrayIndex] & (1 << bitIndex)) != 0;
    }
 
    //将数据的对应位置置为0
    public void reSet(int val) {
        if (val < 0) {
            throw new IndexOutOfBoundsException();
        }
        int arrayIndex = val / 8;
        if (arrayIndex >= elem.length) {
            return;
        }
        int bitIndex = val % 8;
        // 1 << bitIndex位置为1，对整个字节取反，再逻辑&运算
        // 这样bitIndex位置无论是0或者1都会被置0，其余位都为1，因此会保留原有的1
        elem[arrayIndex] &= (byte) ~(1 << bitIndex);
        usedSize--;
    }
 
    public int getUsedSize() {
        return usedSize;
    }
}

MyBitSet 中有三个主要方法，其解决方式基本一致，只在最后的位运算中有所差别，代码中已有详细的注释。