（转）zoie中DocIDMapperImpl类的分析
原文：http://www.kafka0102.com/2010/07/238.html （这是个牛人）
?
还是说下DocIDMapperImpl的作用吧。在zoie中，uid和lucene的docid有一一对应关系。从docid到uid的映射很简单，就是分配个maxdoc大小的数组，索引位置是docid，值是uid。这样做也是因为docid是从小到大自增的，大小总有限。但uid是long型的，使用数组反映射是不行了，一个直接的选择是使用hashmap。不过zoie为了节约空间，使用了更有效的算法，也就是下面的类，这个算法有些像是bloom filter算法的变种应用。
package proj.zoie.api.impl; import java.util.Arrays;import java.util.HashMap; import proj.zoie.api.DocIDMapper;import proj.zoie.api.ZoieIndexReader; /** * @author ymatsuda * */ public class DocIDMapperImpl implements DocIDMapper { private final int[] _docArray;private final long[] _uidArray;private final int[] _start;private final long[] _filter;private final int _mask;private final int MIXER = 2147482951; // a prime number /** * * @param uidArray uidArray的大小是索引的maxdoc，所以数组的每个索引位置 * 表示docid，值表示uid，如果docid被删除， * 其索引位置的值为ZoieIndexReader.DELETED_UID */public DocIDMapperImpl(long[] uidArray) {int len = uidArray.length;int mask = len / 4;mask |= (mask >> 1);mask |= (mask >> 2);mask |= (mask >> 4);mask |= (mask >> 8);mask |= (mask >> 16);_mask = mask;//上面的操作，首先是取mask为len的1/4,之后做了联合的右移及或操作，//使得mask最高有效位右边的位值都变为1,也就是说，假如mask开始等于0x10110000，//操作后变成0x11111111，这才能mask可以和下面的h做与操作定位到_filter数组中//的某个索引位置。也可以看到，mask的大小介于len的1/4到1/2。_filter = new long[mask + 1]; for (long uid : uidArray) {if (uid != ZoieIndexReader.DELETED_UID) {int h = (int) ((uid >>> 32) ^ uid) * MIXER;//这个hash值算法目的是将uid能散到int的整个数值范围内，并降低h之间的冲突，//所以计算后得到的h会比较大。long bits = _filter[h & _mask];bits |= ((1L << (h >>> 26)));bits |= ((1L << ((h >> 20) & 0x3F)));_filter[h & _mask] = bits;//(h >>> 26)得到的是h高位的前5位，再经过1L << 后，其取值范围就是0-31;//(1L << ((h >> 20) & 0x3F))取值范围是0-63。//这两个或操作正好取了bits的位数范围中的两位。//bits的两个或操作，相当于bloom filter中两次hash取位。//对于bloom filter算法，判定key是否存在是有误判的可能性，这里也不意外。//因为bits有64位，而每个uid取两位，mask最坏是len的1/2，在hash散均的情况下，//这个_filter每个桶(索引位置）冲突率不会很大。}} _start = new int[_mask + 1 + 1];len = 0;for (long uid : uidArray) {if (uid != ZoieIndexReader.DELETED_UID) {_start[((int) ((uid >>> 32) ^ uid) * MIXER) & _mask]++;len++;}}int val = 0;for (int i = 0; i < _start.length; i++) {val += _start[i];_start[i] = val;}_start[_mask] = len;//_start经过了两个循环处理，第一个循环计算出_start每个桶中保存了多少个uid，//并计算出有效的uid个数len。第二个循环是为下面的操作做准备，它使得_start中每个桶//保存的是从第0个桶到当前桶有多少有效的uid。 long[] partitionedUidArray = new long[len];int[] docArray = new int[len]; for (long uid : uidArray) {if (uid != ZoieIndexReader.DELETED_UID) {int i = --(_start[((int) ((uid >>> 32) ^ uid) * MIXER) & _mask]);partitionedUidArray[i] = uid;}}int s = _start[0];for (int i = 1; i < _start.length; i++) {int e = _start[i];if (s < e) {Arrays.sort(partitionedUidArray, s, e);}s = e;}//这两个循环来填充partitionedUidArray数组，并调整_start保存的计数，//这个计数就是partitionedUidArray数组的索引位置的偏小临近值。//注意对_start的--操作和s < e的判断，这是处理一个桶里存在多个uid的情况，//以保证partitionedUidArray中uid的顺序，也使得_start相邻两个桶的计数会有差值。//所以当可以利用二分查找来搜索_uidArray和_docArray。for (int docid = 0; docid < uidArray.length; docid++) {long uid = uidArray[docid];if (uid != ZoieIndexReader.DELETED_UID) {final int p = ((int) ((uid >>> 32) ^ uid) * MIXER) & _mask;int idx = findIndex(partitionedUidArray, uid, _start[p],_start[p + 1]);if (idx >= 0) {docArray[idx] = docid;}}}//填充docArray_uidArray = partitionedUidArray;_docArray = docArray;} /** * @see 分析出构造函数后，这个函数就比较好理解了。这里就不细说了。 */public int getDocID(final long uid) {final int h = (int) ((uid >>> 32) ^ uid) * MIXER;final int p = h & _mask; // check the filterfinal long bits = _filter[p];if ((bits & (1L << (h >>> 26))) == 0|| (bits & (1L << ((h >> 20) & 0x3F))) == 0)return -1; // do binary search in the partitionint begin = _start[p];int end = _start[p + 1] - 1;// we have some uids in this partition, so we assume (begin <= end)while (true) {int mid = (begin + end) >>> 1;long midval = _uidArray[mid]; if (midval == uid)return _docArray[mid];if (mid == end)return -1; if (midval < uid)begin = mid + 1;elseend = mid;}} /** * @see 在arr的一个区间内二分查找uid所在的索引位置。 * @param arr * @param uid * @param begin * @param end * @return */private static final int findIndex(final long[] arr, final long uid,int begin, int end) {if (begin >= end)return -1;end--; while (true) {int mid = (begin + end) >>> 1;long midval = arr[mid];if (midval == uid)return mid;if (mid == end)return -1; if (midval < uid)begin = mid + 1;elseend = mid;}}}??
就时间复杂度来说，DocIDMapperImpl和hashmap相当（在hash均匀情况下，那个二分查找次数通常不会很多）。就空间复杂度来说，DocIDMapperImpl中的_uidArray和_docArray相当于hashmap中项的kye和value集合。DocIDMapperImpl中还有的是_start和_filter，而hashmap中每个项还有hash值和项冲突时的next引用以及需要大于负载因子的额外空间。在mask等于1/2 len的最坏情况下，DocIDMapperImpl也是要优于hashmap的。
