如何使用哈希函数的结果来获取数组索引？

Question

我正在学习布隆过滤器，我正在查看 JavaScript 中的各种哈希函数。

例如，我在另一个 Stack Overflow 答案中找到了这个：

在此处找到 )

String.prototype.hashCode = function() {
  var hash = 0, i, chr, len;
  if (this.length == 0) return hash;
  for (i = 0, len = this.length; i < len; i++) {
    chr   = this.charCodeAt(i);
    hash  = ((hash << 5) - hash) + chr;
    hash |= 0; // Convert to 32bit integer
  }
  return hash;
};

如果我运行:

String.prototype.call(null, "hello")

我得到的数值是：99162322 （另外两个哈希函数得到了我：1335831723 和 120092131）。

现在，如果我创建一个假设的布隆过滤器，其中包含 3 个哈希函数和 18 个索引（k=3，m=18），这些大值如何在索引为 0-17 的数组中进行索引？

Answer 1

使用 the remainder/modulo operator % 将随机生成的值包装在特定范围内。

如果你有 18 个元素（索引 0 到 17），你可以得到一个带有 99162322 % 18 (16) 的索引。

如果哈希值个数不是索引个数的倍数，结果会有偏差。例如，如果你的散列值是从 0 到 4 的五个值之一，但你将它映射到从 0 到 2 的三个索引上，它将偏向于 0 (0 % 3, 3 % 3 ) 和 1（1 % 3 或 4 % 3）超过 2（仅 2 % 3）。根据您的需要，如果哈希值的数量远大于索引的数量，则偏差可能是可以接受的。如果你想避免它，你需要一个方案来生成一个新的哈希输入，如果哈希结果来自偏差诱导范围。像这样：

function hashIndex(string, length, hashValueCount) {
  var minBiasedIndex = hashValueCount - (hashValueCount % length);
  for (var i = 0; ; i++) {
    var hashInput = string + ":" + String(i);
    var hashResult = hash(hashInput);
    if (hashResult < minBiasedIndex) {
      return hashResult % length;
    }
  }
}

如何使用哈希函数的结果来获取数组索引？

How to use result from a hash function to get an array index?

javascript

data-structures

hash

hashtable

bloom-filter