面试被问，一千万个整数里面快速查找某个整数，你会怎么去做？

最近小林在求职面试中被询问了这么一个有趣的面试题：

假设当我们需要在一千万个整数（整数的范围在1-1亿之间）里面快速查找某个整数是否存在于其中的话，如何快速查找进行判断会比较方便呢？

ps: int 类型的数据存储的时候是会占用四个字节空间，假设存储的数据范围在1-1亿之间，那么数据存储的时候大概占用空间为：100 * 100 * 1000 * 4 byte 大概存储空间大小消耗为 ：40000 kb 40mb左右。

1.散列表结构方案

通过散列表来实现该功能当然是可以的，但是散列表里面除了需要存储对应的数字以外，还需要存储对应的链表指针，每个数字都采用int类型来进行存储的话，光是数字占用的内存大小大概是40mb左右，如果是加上了指针的存储空间的话，那么存储的内存大小大概是80mb左右了。

2.布尔数组结构方案

通过使用布尔类型的数组来进行存储。首先创建一个一千万长度的布尔类型数组，然后根据整数，定位到相应的下标赋值true，那么以后在遍历的时候，根据相应的下标查找到指定的变量，如果该变量的值是true的话，那么就证明该数字存在。

布尔类型变量在存储的时候只有true和false存在，但是在数组中存储的时候实际上是占用了1个字节，该类型的变量在被编译之后实际上是以int类型的数据0000 0000和0000 0001存储的，因此还是占用了较多的内存空间。

3.使用bitmap来进行存储

例如说一个长度是10的bitmap，每一个bit位都存储着对应的0到9的十个整形数字，此时每个bitmap所对应的位都是0。当我们存入的数字是3的时候，位于3的位置会变为1。

当我们存储了多个数字的时候，例如说存储了4,3,2,1的时候，那么位图结构就会如下所示：

那么这个时候你可能就会疑惑了，到底在代码上边该如何通过计算来获取一个数字的索引定位呢？

首先我们将核心思路的代码先贴上来：

 public void set(int number) {
        //相当于对一个数字进行右移动3位，相当于除以8
        int index = number >> 3;
 
        //相当于 number % 8 获取到byte[index]的位置
        int position = number & 0x07;
 
        //进行|或运算  参加运算的两个对象只要有一个为1，其值为1。
        bytes[index] |= 1 << position;
    }

为了方便理解核心思想，所以还是通过图例来理解会比较好：

例如说往bitmap里面存储一个数字11，那么首先需要通过向右移位（因为一个byte相当于8个bit），计算出所存储的byte[]数组的索引定位，这里计算出index是1。由于一个byte里面存储了八个bit位，所以通过求余的运算来计算postion，算出来为3。

这里假设原有的bitmap里面存储了4和12这2个数字，那么它的结构如下所示：

这个时候，我们需要存储11进来，那么就需要进行或运算了：

同理，当我们判断数字是否存在的时候，也需要进行相应的判断，代码如下：

  public boolean contain(int number) {
        int index = number >> 3;
        int position = number & 0x07; 
        return (bytes[index] & (1<<position)) !=0;
    }

整合一下，简单版的一个bitmap代码如下：

public class MyBitMap {
 
    private byte[] bytes;