[数据结构与算法]位图的实战场景及源码分析

前言：

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

有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<<index 即获取对应下标的值，当对应index 的bit位值为1时，对应的数字即1<<index
    // 3.a[row] |= x 即 a[row] = a[row] | x，针对已存在的a[row]值，或上新的x值，即可获得新值
    a[row] |= 1 << (n & 0x1F);
}

// 判断所在的bit为是否为1
public boolean exists(int n) {
    int row = n >> 5;
    return (a[row] & (1 << (n & 0x1F))) == 1;
}

public static void main(String[] args) {

    BitSetTest bitSetTest = new BitSetTest();
    bitSetTest.addValue(31);
}

获取的话，主要分为两步，第一步：获取数字n在int[]中的row（具体某行）；第二步：获取数字n在int[row]中具体的index

3.java中的BitSet实现

在java.util包下，有一个叫做BitSet的类，它本质上就是上述位图的实现，我们先来看下其是如何使用的

// 创建一个位图对象
BitSet bitSet = new BitSet();
// 向里添加10W个数字
for (int i = 0; i < 100000; i++) {
    bitSet.set(i);
}
// 判断9999是否在位图中
boolean b = bitSet.get(9999);// 返回true	

使用起来非常简单，就我们在前言中提到的问题，就可以用同样的方式来解决，我们可以将这40亿个数字都调用bitSet.set()方法添加进来（如果觉得太多，可以分批次添加），最终调用get方法来进行指定数字查询即可。

3.1 BitSet的构造方法

public class BitSet implements Cloneable, java.io.Serializable {
    
    // 当计算给定数字属于long[]的哪一行时，需要ADDRESS_BITS_PER_WORD，类似于上面使用int[]时，值为5
    private final static int ADDRESS_BITS_PER_WORD = 6;
    // BITS_PER_WORD=64，代表Long类型有64个bit位
    private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;
    private final static int BIT_INDEX_MASK = BITS_PER_WORD - 1;
    
    // 以long[]数组来存储数字
    private long[] words;
    
    // 当前long[]已经用到哪一行
    private transient int wordsInUse = 0;
    
    // 提供两个构造方法，默认数据为64，也就是一个long的bit位数
    public BitSet() {
        initWords(BITS_PER_WORD);
        sizeIsSticky = false;
    }
    
    public BitSet(int nbits) {
        // nbits can't be negative; size 0 is OK
        if (nbits < 0)
            throw new NegativeArraySizeException("nbits < 0: " + nbits);

        initWords(nbits);
        sizeIsSticky = true;
    }
    // 初始化long[]数组大小
    private void initWords(int nbits) {
        words = new long[wordIndex(nbits-1) + 1];
    }
    
    private static int wordIndex(int bitIndex) {
        return bitIndex >> ADDRESS_BITS_PER_WORD;
    }
}

看了BitSet的构造方法，与上面我们的解决方案有所不同的是，这里采用long[]数组来存放数据，其他没有不同。

默认的话，最大为64，所以对应的long[]数组大小为64 >> 6 = 1。当然，也可以在创建BitSet的时候指定数据大小，这时候数组大小即为(n-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<< bitIndex
        words[wordIndex] |= (1L << bitIndex); // Restores invariants

        checkInvariants();
    }
    
    private void expandTo(int wordIndex) {
        int wordsRequired = wordIndex+1;
        if (wordsInUse < wordsRequired) {
            // 扩容到合适的行数
            ensureCapacity(wordsRequired);
            wordsInUse = wordsRequired;
        }
    }
    
    private void ensureCapacity(int wordsRequired) {
        if (words.length < wordsRequired) {
            // 扩容到最大
            int request = Math.max(2 * words.length, wordsRequired);
            words = Arrays.copyOf(words, request);
            sizeIsSticky = false;
        }
    }
}

使用BitSet添加数据时候，代码并不复杂，基本与上2中的操作是一致的，只不过这里多一个自动扩容的操作，防止数据过大，当前long[]存储不下

3.3 BitSet.get() 查询数据是否在BitSet中

public class BitSet implements Cloneable, java.io.Serializable {
	public boolean get(int bitIndex) {
        if (bitIndex < 0)
            throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);

        checkInvariants();

        // 先获取数字所在long[]的行
        int wordIndex = wordIndex(bitIndex);
        // 比较对应index的值（0或1），是否匹配，若能匹配上，则说明该值在BitSet中
        return (wordIndex < wordsInUse)
            && ((words[wordIndex] & (1L << bitIndex)) != 0);
    }
}

查询数据是否存在的过程，就是按照set的过程进行一遍查询而已，不算复杂，主要就是寻找对应行的对应位所对应的值是否为1，为1说明数据存在，否则，数据不存在

BitSet还提供了很多其他的方法，大家可以自行阅读测试，笔者不再赘述。

参考：

? ??位图的原理和简单实现 - 小小小小的我 - 博客园??