algorithm - hashmap中的简单hashcode误解？

我正在实现我自己的专用hashmap，它具有泛型值类型，但键的类型总是long在这里和那里，我看到有人建议我用一个素数乘以一个键，然后用桶的数量得到模：

int bucket = (key * prime) % numOfBuckets;

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

int bucket = key % numOfBuckets;

例如，如果numOfBuckets是8，使用第二个“算法”，我们得到的buckets类似于{0，1，2，3，4，5，6，7}重复键=0到无穷大在第一个针对相同密钥的算法中，我们得到bucket{0、3、6、1、4、7、2、5}（或类似的）也在重复基本上我们有相同的问题，比如当使用标识散列时。
基本上，在这两种情况下，我们都会得到键的碰撞：

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

因为当我们用numOfBuckets得到模的时候，我们总是得到x。那么，第一个算法是什么，有人能告诉我吗？

最佳答案

如果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);
}

另一个有效的方法是乘以某个大常数，然后使用结果的高位（它包含它们下面的位的混合，所以键的所有位都可以这样使用）。