减少冲突的散列函数

Question

我正在使用这个散列函数，但是我得到了很多冲突。其目的是将元素的ascii值相加并输出值。有没有办法优化这个函数或其他函数，以减少冲突的数量？

int hash(char* s)
{
    int hash = 0;
    while(*s)
    {
        hash = hash + *s;
        s++;
    }
    return hash;
}

Answer 1

32位int的范围超过40亿。(如果您的int是64位的，则范围要大得多。)但是您的代码只是简单地将字符串中每个字符的值相加，它永远不会接近上限范围。所有的哈希码都将是较小的数字，挤占了可能值的低端，并增加了冲突的机会。

这就是为什么一个好的算法会比这个更复杂。

在谷歌快速搜索中出现的Here's one article。

Answer 2

"foo bar“和"bar foo”散列为相同的值，对吗？实现它的方式是使用ascii值及其在字符串中的位置来计算哈希，我天真地认为这将显着减少冲突。

int hash(char* s)
{
    int hash = 0;
    int pos = 0;
    while(*s)
    {
        pos++;
        hash += (*s * pos);
        s++;
    }
    return hash;
}

试试这个，看看是否有帮助。这个答案背后我没有太多的理论知识。

EDIT*如下所述，您可能希望hash是一个无符号整数。我在codechef.com上进行了测试，以下是源代码和结果：

#include <stdio.h>

unsigned int hash(char* s);
unsigned int hash2(char* s);

int main(void) {
    unsigned int temp1 = hash("foo bar");
    unsigned int temp2 = hash("bar foo");

    printf("temp1 is %d and temp2 is %d\n",temp1, temp2);

    temp1 = hash2("foo bar");
    temp2 = hash2("bar foo");

    printf("temp1 is %d and temp2 is %d\n",temp1, temp2);

    return 0;
}

unsigned int hash(char* s)
{
    unsigned int hash = 0;
    while(*s)
    {
        hash = hash + *s;
        s++;
    }
    return hash;
}

unsigned int hash2(char* s)
{
    unsigned int hash = 0;
    int pos = 0;
    while(*s)
    {
        pos++;
        hash += (*s * pos);
        s++;
    }
    return hash;
}

带输出：

temp1为665，temp2为665

temp1为2655，temp2为2715

Answer 3

是的，您的"hash“函数将对由相同字母组成的字符串产生冲突，例如"rail”和“rail”。这是因为你只使用了可交换的加法。

你可以使用像这样的东西，它包含一个素数作为因子。

unsigned long int hashBetter(const char* s)
{
    unsigned long int hash = 1234567890ul;
    while(*s)
    {
        hash = (*s + hash) * 4294967291ul;
        s++;
    }
    return hash;
}

或者使用CRC，它将输入数据广泛分布在可能的散列值的有效范围内：

unsigned long int hashGood(const char* s)
{
    unsigned long int hash = 1234567890ul;
    while(*s)
    {
        hash = crc(hash, *s);
        s++;
    }
    return hash;
}