位图的实战场景及源码分析

前言：

之前碰到过一道面试题，大概内容如下

有40亿个无符号的整型数据，现在给定一个目标数字，判断这个数字是否在这40亿数据中？	

刚开始想的时候，处理思路应该很简单，直接把这40亿个数字存储到一个集合中，但是仔细一算，发现并不现实，一个int类型的数字占4个字节，4byte * 40亿 差不多就是16G的大小，占用内存太大，那么还有没有好的办法给解决呢？

1.解决思路

一个int类型数字占用4字节，32bit位，那我们能不能用一个bit位来表示一个数字呢？

理论上肯定是可以的，如下图所示：

我们用bit0位代表1，一直到31位bit代表数字32，如果当前bit位值为1，则说明存在对应数字。这样的话，一个32bit的int，可以存储32个数字，如果按照这种模型的话，那么上面的40亿个数字使用500多M的空间就可以存放下来。

假如现在需要存放数字1、3、31，那么具体如下

是一个不错的思路，但是上面这种，超过32bit位的数字应该怎么办呢？总不能无限扩bit位吧？

我们可以使用数组来解决这个问题，32bit所组成的数组，如下所示：

我们使用这个数组来存放更多的值，理论上来说，无论多少的值（N个数字），只要内存放的下，我们就可以使用int[]来存放，数组的长度等于N/32+1

2.代码实现

// 假设我们有10亿个数据要处理
private int N = 1000000000;
// 在这里使用int[]数组来存储，按照上面的分析，数组长度为N / 32 + 1
private int[] a = new int[N / 32 + 1];

public void addValue(int n) {
    // n >> 5 等于 n/32，算出n所在int数组的那一列
    int row = n >> 5;
    //相当于 n % 32 求n在数组a[i]中的下标
    // 这句代码可以拆成三句来看
    // 1.n & 0x1F 即n 和 00001111的与操作，获得n在当前32bit位中的下标index
    // 2.1> 6 +1
 
 
3.2 BitSet.set() 添加数据 
public class BitSet implements Cloneable, java.io.Serializable {
	public void set(int bitIndex) {
        if (bitIndex < 0)
            throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

        // 获取当前数据所属行
        int wordIndex = wordIndex(bitIndex);
        // 如果计算出的行超过目前的最大行数，则扩容long[]一倍
        expandTo(wordIndex);

        // 设置对应index值为 1