字符串的通用散列函數

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就足夠了。