java - 字符串的通用哈希函数

Question

我正在尝试为字符串实现两个不同的通用散列函数。但我有一个问题，有时哈希值为 0。有了这个我不能使用哈希函数，因为我想实现双重哈希并且必须实现这个函数： hash_func1(string s) + i * hash_func2(string s)遍历哈希表。但是，如果一个哈希函数为 0，则没有任何变化，我会得到一个无限循环。这是用于哈希表中的冲突检测。我需要两个不同的通用哈希函数来做到这一点。

我尝试了不同的哈希函数，但找不到任何有效的方法。

谁能帮我解决这个问题？

这是我尝试过的一些功能。

int h = 0 , r1 = 31415 , r2 = 27183;
 for (int i =0; i < key.length (); i ++) {
 h = ( r1 * h + key.charAt ( i )) % capacity ;
 r1 = r1 * r2 % (capacity -1);
}
return h ;

或者这个

int seed = 131; 
long hash = 0;
for(int i = 0; i < key.length(); i++)
{
hash = (hash * seed) + key.charAt(i);
}
return (int) (hash % capacity);

Answer 1

关于双散列的维基百科文章建议您修改散列函数以避免它变为零，最简单的方法是简单地添加1：

int h1 = hash_func1(s);
int h2 = (hash_func2(s) % (capacity - 1)) + 1;

// loop over (h1 + i * h2) % capacity

编辑：哎呀，我猜你还需要用 来绑定它capacity - 1，否则h2 == capacity，你仍然会遇到一个无限循环......或者，更好的是，hash_func2()已经返回一个小于 的值capacity - 1，那么添加1就足够了。