Cuckoo Hashing Collisions 导致溢出

Question

我正在尝试使用散列函数实现布谷鸟散列： hash1: key.hashcode() % 容量 hash2: key.hashcode() /容量%容量

用无限循环检查和rehashing方法使容量翻倍。该程序适用于少量数据，但当数据变大（大约 20k 个元素）时，程序会不断重新散列，直到容量溢出。

我认为无限重新散列主要是由具有完全相同散列码的数据引起的。重新散列后，其他数据可能会得到相同的散列码并导致再次重新散列。

我已经使用 Java 内置哈希码，但当数据很大时，相同哈希码的可能性仍然很高。即使我修改了一点哈希码方法，最终仍然有具有相同哈希码的数据。

那么我应该使用哪种哈希方法来防止这种情况发生？

Answer 1

创建哈希函数的常用方法通常是使用质数。我写了一个函数（下面），我不保证不会碰撞，但应该减少它。

hashFunction1(String s){
    int k = 7;         //take a prime number, can be anything (I just chose 7)
    for(int i = 0; i < s.length(); i++){
        k *= (23 * (int)(s.charAt(i)));
        k %= capacity;
    }
}
//23 is another randomly chosen number.

你可以写一个类似hashFunction2的散列函数，选择两个不同的质数。但这里的主要问题是，对于字符串 "stop" 和 "pots"，这给出了相同的哈希码。

因此，对这个函数的改进可以是：

hashFunction1(String s){
    int k = 7;         //take a prime number, can be anything (I just chose 7)
    for(int i = 0; i < s.length(); i++){
        k *= (23 * (int)(s.charAt(i)));
        k += (int)(s.charAt(i));
        k %= capacity;
    }
}

这将解决这个问题（对于大多数情况，如果不是全部的话）。

如果您仍然觉得这个函数不好，您可以使用映射到每个字符的唯一质数代替 s.charAt(i)，即。 a=3, b=5, c=7, d=11 等等。这应该更能解决冲突。

编辑：

您正在使用 +n，这是一个常量。
2 不是在这种情况下使用的素数。使用奇质数，3个有效。

Cuckoo Hashing Collisions 导致溢出

Cuckoo Hashing Collisions lead to overflow

java

stack-overflow

algorithm

hash

collision