java - Cuckoo Hashing Collisions 导致溢出

Question

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

用无限循环检查和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 等等。这应该更能解决冲突。

编辑:

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