FixedBitSet

FixBitSet 类在 Lucene 中属于一个工具类(Util),它的其中一个用途用来存储文档号,用一个 bit 位来描述(存储)一个文档号。该类特别适合存储连续并且没有重复的 int 类型的数值。最好情况可以用 8 个字节来描述 64 个 int 类型的值。下面通过介绍几个 FixBitSet 类的方法来理解这个类的存储原理。本篇文章纯属充数。。。直接看源码的话不会花很多时间,写这篇文章的原因主要是出于总结,因为好几个月前我看过了这个类的源码,今天准备写关于 NumericDocValues 的文章时再次遇到这个类时,发现又忘了,囧。

构造函数

1
2
public FixedBitSet(int numBits) {
  }

构造一个 FixedBitSet 对象,参数 numBits 用来确定需要多少 bit 位来存储我们的 int 数值。如果我们另 numBits 的值为 300,实际会分配一个 64 的整数倍的 bit 位。因为比 300 大的第一个 64 的倍数是 320 (64 * 5),所以实际上我们可以存储 [0 ~319]范围的数值。最终根据 320 的值,我们获得一个 long 类型的 bit[]数组,并且 bit[]数组初始化为大小 5。在这里我们发现 bit[]数组的每一个元素是 long 类型,即 64bit,所以 5 个元素一共有 64 * 5 共 320 个 bit 位。

void set(int index)方法

1
2
3
4
5
6
7
8
public void set(int index) {
        // 将index根据64进行划分,比如 0~63都属于一个wordNum, 64~127属于另一个wordNum
        int wordNum = index >> 6;      // div 64
        // 计算出当前文档号应该放到64个bit位(long类型)的哪一位
        long bitmask = 1L << index;
        // bits[]是个long类型的数据
        bits[wordNum] |= bitmask;
    }

例子:

图 1:

添加 3

1
2
3
4
根据set()方法的逻辑:
1. 计算出wordNum的值:3 >> 6,即wordNum = 0,说明3应该存放在bit[]数组下标为0的元素中。
2. 计算出bitmask的值,即计算出在64个bit位中的偏移,bitmask = 0b1000。
3. 与bit[0]的值执行或操作。

图 2:

添加 67

1
2
3
4
根据set()方法的逻辑:
1. 计算出wordNum的值:67 >> 6,即wordNum = 1,说明67应该存放在bit[]数组下标为1的元素中。
2. 计算出bitmask的值,即计算出在64个bit位中的偏移,bitmask = 0b1000。
3. 与bit[1]的值执行或操作。

图 3:

添加 120

1
2
3
4
根据set()方法的逻辑:
1. 计算出wordNum的值:120 >> 6,即wordNum = 1,说明120应该存放在bit[]数组下标为1的元素中。
2. 计算出bitmask的值,即计算出在64个bit位中的偏移,bitmask = 0b00000001_00000000_00000000_00000000_00000000_00000000_00000000_00000000。
3. 与bit[1]的值执行或操作。

图 4:

添加 179、195、313

不赘述,大家可以自己算下是不是跟下图中一致。

图 5:

通过上面的例子可以看到,如果我们存储的是连续的值,那么压缩率是很高的。当然同时可以看出无法处理有相同值的问题。

boolean get(int index)方法

get()方法可以实现随机访问,来确定 index 的值是否在 bit[]数组中。

1
2
3
4
5
6
public boolean get(int index) {
    int i = index >> 6;               // div 64
    long bitmask = 1L << index;
    // 如果bit为1,说明index在bit[]数组中。
    return (bits[i] & bitmask) != 0;
  }

结语

FixedBitSet 类中还有一些其他的方法,比如说 prevSetBit(int index)方法来找到第一个比 index 小的值和 nextSetBit(int index)