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)