Lucene 源码系列——工具类 FixedBitSet
FixedBitSet
FixBitSet 类在 Lucene 中属于一个工具类（Util），它的其中一个用途用来存储文档号，用一个 bit 位来描述（存储）一个文档号。该类特别适合存储连续并且没有重复的 int 类型的数值。最好情况可以用 8 个字节来描述 64 个 int 类型的值。下面通过介绍几个 FixBitSet 类的方法来理解这个类的存储原理。本篇文章纯属充数。。。直接看源码的话不会花很多时间，写这篇文章的原因主要是出于总结，因为好几个月前我看过了这个类的源码，今天准备写关于 NumericDocValues 的文章时再次遇到这个类时，发现又忘了，囧。
构造函数
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)方法
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
根据set()方法的逻辑：
1. 计算出wordNum的值：3 >> 6,即wordNum = 0，说明3应该存放在bit[]数组下标为0的元素中。
2. 计算出bitmask的值，即计算出在64个bit位中的偏移，bitmask = 0b1000。
3. 与bit[0]的值执行或操作。
图 2：
添加 67
根据set()方法的逻辑：
1. 计算出wordNum的值：67 >> 6,即wordNum = 1，说明67应该存放在bit[]数组下标为1的元素中。
2. 计算出bitmask的值，即计算出在64个bit位中的偏移，bitmask = 0b1000。
3. 与bit[1]的值执行或操作。
图 3：
添加 120
根据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[]数组中。
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)方法来找到第一个比 index 大的数，在 Lucene 中，常用 FixedBitSet 类来存储文档号，并且在通过 prevSetBit(int index)或者 nextSetBit(int index)来遍历文档号。
