-3

它通常用于java.util.HashMap

/**
 * Returns index for hash code h.
 */
static int indexFor(int h, int length) {
    return h & (length-1);
}

其中长度以 2 为底。

或者 Lucene 布隆过滤器代码 (org.apache.lucene.codecs.bloom.FuzzySet)

// Bloom sizes are always base 2 and so can be ANDed for a fast modulo
int pos = positiveHash & bloomSize;

这对我来说没有意义，因为例如 8 和之间的差异i % 8不i & 8为零！

    scala> (0 to 20).map(i => (i & 8) - (i % 8))
res33: scala.collection.immutable.IndexedSeq[Int] = Vector(0, -1, -2, -3, -4, -5, -6, -7, 8, 7, 6, 5, 4, 3, 2, 1, 0, -1, -2, -3, -4)
4

1 回答 1

1

HashMap 和 FuzzySet 都不是精确的 2 次幂 - 它们使用的是整数形式2^n - 1。不幸的是，您从 FuzzySet 引用的评论在这方面具有误导性，但是如果您稍微挖掘一下，您可以找到以下代码块：

//The sizes of BitSet used are all numbers that, when expressed in binary form,
//are all ones. This is to enable fast downsizing from one bitset to another
//by simply ANDing each set index in one bitset with the size of the target bitset
// - this provides a fast modulo of the number. Values previously accumulated in
// a large bitset and then mapped to a smaller set can be looked up using a single
// AND operation of the query term's hash rather than needing to perform a 2-step
// translation of the query term that mirrors the stored content's reprojections.
static final int usableBitSetSizes[];
static
{
  usableBitSetSizes=new int[30];
  int mask=1;
  int size=mask;
  for (int i = 0; i < usableBitSetSizes.length; i++) {
      size=(size<<1)|mask;
      usableBitSetSizes[i]=size;
  }    
}

FuzzySet 中的 bitsize 变量总是最终从这个数组中赋值的。这里的评论也准确地描述了正在发生的事情。

计算X % 8 (1000)就是计算X & 7 (0111)。这适用于 2 的所有幂。

于 2013-04-15T23:21:07.817 回答