1

我正在实现我自己的具有通用值类型的专用哈希图，但键总是长类型。在这里和那里，我看到人们建议我应该将键乘以素数，然后按桶数取模：

int bucket = (key * prime) % numOfBuckets;

我不明白为什么？在我看来，它的分布与 simple 完全相同：

int bucket = key % numOfBuckets;

例如，如果 numOfBuckets 为 8，则使用第二个“算法”我们会得到像 {0, 1, 2, 3, 4, 5, 6, 7} 这样的桶重复 key = 0 到无穷大。在相同键的第一个算法中，我们得到桶 {0, 3, 6, 1, 4, 7, 2, 5}（或类似的）也重复。基本上我们有同样的问题，就像使用身份哈希时一样。

基本上，在这两种情况下，我们都会遇到键冲突：

key = x + k*numOfBuckets (for k = 1 to infinity; and x = key % numOfBuckets)

因为当我们对 numOfBuckets 取模时，我们总是得到 x。那么，第一个算法是怎么回事，有人可以启发我吗？

4

1 回答 1

2

如果numOfBuckets是 2 的幂并且prime是奇数（这似乎是预期的用例），那么我们有gcd(numOfBuckets, prime) == 1. 这反过来意味着有一个数字inverse，inverse * numOfBuckets = 1 (mod numOfBuckets)所以乘法是一个双射运算，它只是将桶打乱一点。那当然没用，所以你的结论是正确的。

或者更直观地说：在乘法中，信息只从最低位流向最高位，从不反向。因此，如果没有乘法，存储桶索引不会依赖的任何位，仍然会随着乘法而被丢弃。

其他一些技术确实有帮助，例如 Java 的 HashMap 使用这个：

/**
 * Applies a supplemental hash function to a given hashCode, which
 * defends against poor quality hash functions.  This is critical
 * because HashMap uses power-of-two length hash tables, that
 * otherwise encounter collisions for hashCodes that do not differ
 * in lower bits. Note: Null keys always map to hash 0, thus index 0.
 */
static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

另一件有效的事情是乘以一些大常数，然后使用结果的高位（其中包含它们下面的位的混合，因此密钥的所有位都可以这样使用）。

于 2017-06-27T20:05:03.757 回答