2 
unsigned int HashString( const char *string ) {
    const char* p;
    unsigned hash = 40503;

    for ( p = string; *p != '\0'; ++p ) {
        hash += *p;
        hash += ( hash << 10 );
        hash ^= ( hash >> 6 );
    }
    hash += ( hash << 3 );
    hash ^= ( hash >> 11 );
    hash += ( hash << 15 );

    return hash;
}

只是在他们的代码上徘徊。不过，我以前从未见过这样的散列函数。

在按位操作方面，我不是太老练，我知道位移和掩码是如何工作的，但仅在基本场景中，例如检查位是否已设置。

这究竟是做什么的？

4

3 回答 3

6

阅读此处以获得一般概述，并继续阅读“一次一次的哈希”（詹金斯），这与这个一致。

另请参阅此答案中提到的此Wikipedia 条目。

“这到底是个怎样的好哈希？” 不完全是。这些转变有点武断，主要来自一些启发式和经验测试。

于 2013-05-22T21:45:55.610 回答
1

当您对二进制算术有更广泛的了解时，这类事情会更容易理解。从数学到代码比反过来要容易得多。

我没有多少运气能找到好的在线资源，但是当我在学校时，我对这本教科书的早期版本感到非常满意。你也可以从一个好的 CS 课程中找到一些关于二进制算术的在线讲义。

这个网站可能会给你一个一般的散列理论的引导。我希望我可以在那里推荐一本教科书，但我还没有遇到一本真正清晰的数论教科书。

于 2013-05-22T21:40:37.290 回答
1

谁说它的哈希值很好？

哈希函数将输入（在本例中为字符串）映射到输出（在本例中为unsigned int. 输入的大小是“提高到”的(number of usable characters) ^ number of characters in the string地方。^

如果您的输入字符串只能包含字符 0，1那么输入的大小将是2^ number of characters in the string

输出的大小是固定的，是 中可表示的最大数字unsigned int。

这意味着存在“字符串中的字符数”，其中输入的大小将大于输出的大小。根据鸽子洞原理，您肯定会开始发生碰撞。实际上，您可能在达到此阈值之前发生了碰撞。

如果您想在您的hash_map或任何其他数据结构中使用散列函数，请确保将其调整到您的特定输入。不要去拿起你在互联网上找到的第一个。一个好的散列函数可以为您的特定输入提供尽可能少的冲突。

在您的特定情况下，通用哈希函数可能不是最佳的。专门为某些输入设计的散列函数（这很可能就是这样一个函数）在您的输入上可能工作得更糟。

于 2013-05-22T21:55:00.123 回答