我们在面试中经常会被文档莫名奇妙的问题： 比如我怎样统计100万用户的上线情况，假设我有亿万文档id 的重复列表，如何去重 等等。 这种问题的关键尤其是涉及到大数据领域都会很常见，问题的核心是这些问题如果用传统的数据结构去做，必然是耗费大量的空间和时间的解决方案，完全不够经济和效率。
对于lucene来说，在最后的文档根据不同的过滤条件做筛选的时候很可能会遇到成千上万的文档的筛选，其最通用的解决方案就是bitset。本文我们初步分析lucene的longebitset 的结构 和java 原生的对其支持。
首先如何转换现实十进制的文档id和bitset 相互转换的关系。
ID 转化为bitset
public LongBitSet(long numBits) {
this.numBits = numBits;
bits = new long[bits2words(numBits)];
numWords = bits.length;
}
numBits 代表的就是十进制中最大的文档id，longbitset 事实上结构是维护一个long型数组，由于long型存储的是64位的bit，也就是说其维护了每个元素为64 bit 的数组。
public void set(long index) {
assert index >= 0 && index < numBits: “index=” + index + “ numBits=” + numBits;
int wordNum = (int) (index » 6); // div 64
long bitmask = 1L « index;
| bits[wordNum] | = bitmask; |
}
index 就是要存储的文档id， 首先找到long数组的索引下标（(in t) (index » 6)） ，第二步找到下标后，再查找文档id在这个64bit的映射。这个事实上相当于ID%64的过程，但是代码中用了带符号循环左移，由于一个long型限定64位，所以大于63的左移，会自动回归最低位重新开始。1L « index 相当于将1从0位循环index/64次，并在index%64位结束。最后一步是用或的方法设置相应的位置。
如何取出bitset中有效的文档号。
/** Returns the index of the last set bit before or on the index specified. *
- -1 is returned if there are no more set bits. * */
public long prevSetBit(long index) {
assert index >= 0 && index < numBits: “index=” + index + “ numBits=” + numBits;
int i = (int) (index » 6);
final int subIndex = (int) (index & 0x3f); // index within the word
long word = (bits[i] « (63-subIndex));
// skip all the bits to the left of index
if (word != 0) {
return (i << 6) + subIndex - Long.numberOfLeadingZeros(word);
// See LUCENE-3197
}
while (–i >= 0) {
word = bits[i];
if (word !=0 ) {
return (i << 6) + 63 - Long.numberOfLeadingZeros(word);
} }
return -1; }
这个方法是返回给定的文档id情况下，前面一个文档ID,如果文档id在bitset存在，直接返回本身。同样先找给定文档id，找到其属于哪个数组，同时求余定位在数组中可能的位置。 index & 0x3f 是相当于index对64 求余数 定位在long型的准确其位置。
下面分两种情况： 如果其前面一位文档id和当前文档id存在于同一个数组下标中，首先将当前long值向左移动63 - 余数位，如果不为0表示当前肯定存在满足条件的文档id。举例来说，假设我们现在寻找的文档id是10000在bitset中当前或者前一个id的值，那么在10000%64 ＝ 16 表示在64bit中是16 (从右往左即为低到高），如果将其左移63-16=17位,由于如果存在另外一个1在其右边(即存在当前位置右边为1的id 同时也表明10000在bitset中不存在，如果存在即返回当前)，那必然左移17位以后，依然在其右边。所以下一个1的位置（从右到左）是(i « 6) + subIndex - Long.numberOfLeadingZeros(word); Long.numberOfLeadingZeros(word) 表示最高位的1前面有几个0，由于在这种情况下当前id 10000 在bitset中必然不存在，那么Long.numberOfLeadingZeros(word) 就是表示下一位id与当前id为10000的间距。(i « 6) + subIndex -Long.numberOfLeadingZeros(word)，定位到下一个文档ID的十进制数。
如果当前long型 不存在前一个有效的文档id，那穷举扫描数组前面的long型数组去寻找非0的long型，由于找跨数组的前一位，肯定是前面数组的低位（也就是最右边为1的） 所以是(i « 6) + 63 - Long.numberOfLeadingZeros(word);
依照道理可推查找下面的一个有效的文档号。