字符串的通用散列函数

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

的wikipedia article on double hashing建议您修改散列函数，以避免它变成零，最简单的方法来做到这一点是简单地添加1：

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

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

编辑：哎呀，我想你还需要通过capacity - 1来绑定它，否则用h2 == capacity，你仍然会碰到一个endle ss循环... 或者甚至更好，有hash_func2()已经返回一个小于capacity - 1的值，那么加入1就足够了。