字符串的通用哈希函数

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

就足够了。

Answer 2

我建议使用 mzhash32 一个非常简单、快速的函数，其碰撞次数非常接近通用哈希函数

public static int mzHash32(final byte[] data, int start, int length, int seed) {
    int hash = 0x95DE1432 ^ seed;
    for(int i = 0; i < length; i++)
        hash = (0xA8657C5B * (i + data[start + i])) ^ (hash << 2) ^ (hash >>> 2);
    return hash;
}

来源：https://github.com/matteo65/mzHash32 64 位版本：https://github.com/matteo65/mzHash64