Lucene 源码系列——BytesRefHash

阅读原文
BytesRefHash 类是专门为 BytesRef 对象作优化的一种类似 hashMap 的数据结构,该类的主要用途就是将所有的 BytesRef 对象存储到一个连续的存储空间中,并且使得能在查询阶段达到 0(1)的时间复杂度。

BytesRefHash 的一些变量

byte[] [] buffers;

二维数组 buffers[][]用来存储 ByteRef 对象,所有的 BytesRef 对象都连续的存储在 buffers[][]数组中

int termID;

termID 是从 0 开始的一个递增的值,每个 BytesRef 根据它存储到 buffers[][]的先后顺序获得一个唯一的 termID

int[] ids;

ids[]数组下标是 BytesRef 对利用 MurmurHash 算法计算出的 hash 值,ids[]数组元素则是 termID

int[] bytesStart;

bytesStart[]数组下标是 termID,数组元素是 termID 对应的 BytesRef 值在 buffers[][]中的起始位置

例子

这里用一个例子来描述上文中介绍的 BytesRefHash 的那些变量之间的关系,存储的内容如下

上图中所有 BytesRef 对象通过 MurmurHash 算法计 算出的 hash 值通过公式 hash & hashMask 散落到 ids[]数组后的情况如下图。其中 hashMask 的值为 15,即当前 ids[]数组大小减 1,另外 ids[]数组中的元素初始值为 -1。



ids[]数组

ids[]数组初始值大小为 16,数组元素(termID)用来作为 bytesStart[]数组的索引

bytesStart[]数组

bytesStart[]数组元素用来作为 buffers[][]二维数组的索引

buffers[] []二维数组

buffers[][]数组中存放了 BytesRef 对象的原始值,每一个 BytesRef 对象按块(block)连续的存放,每一个 block 中包含了 BytesRef 对象的长度跟原始值,存放长度的作用用来在读取阶段描述应该读取数组中多长的数据,注意的是存储长度占用的字节根据 BytesRef 的大小可能占用 1 个或者 2 个字节,下面的例子中,存储所有的 BytesRef 对象的长度只需要 1 个字节
term 值与 BytesRef 对象的关系

Term BytesRef(十六进制) BytesRef(十进制) 长度
mop [6d, 6f, 70] [109, 111, 112] 3
moth [6d, 6f, 74, 68] [109, 111, 116, 104] 4
of [6f, 66] [111, 102] 2
star [73, 74, 61, 72] [115, 116, 97, 114] 4

三个数组的映射关系

三个数组之间的关系如下图

结语

本篇博客通过例子介绍了 BytesRefHash 类如何存储 BytesRef 对象,但并没有以代码的形式给出,要理解 BytesRefHash 这个类中实现逻辑,其类中最重要的一个方法就是 add(BytesRef bytes),这个方法中的源码详细注释大家可以看我的 GitHub:https://github.com/luxugang/Lucene-7.5.0/blob/master/solr-7.5.0/lucene/core/src/java/org/apache/lucene/util/BytesRefHash.java ,对应的 demo 在这里:https://github.com/luxugang/Lucene-7.5.0/blob/master/LuceneDemo/src/main/java/lucene/utils/BytesRefHashTest.java


本文地址:https://www.6aiq.com/article/1586426301404
本文版权归作者和AIQ共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出