这个来自CryEngine的散列函数是如何工作的？

Question

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;
}

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

当涉及到位操作时，我不太熟悉，我知道位移位和掩码是如何工作的，但只在像检查位是否被设置这样的基本场景中。

这到底是做什么的？

Answer 1

阅读here以获得一般概述，并阅读“一次一个散列”(作者: Jenkins)，这与本文不谋而合。

另请参阅this answer中提到的这个Wikipedia entry。

“这到底是一个好的哈希吗？”不完全同意。这些转变有点武断，主要是通过一些启发式和经验测试来证明是合理的。

Answer 2

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

我不太幸运地找到了一个好的在线资源，但当我还在学校的时候，我对this textbook的早期版本非常满意。你也可以在CS课堂上找到一些关于二进制算术的在线讲稿。

一般而言，This site可能会引导您深入了解散列理论。我希望我能在那里推荐一本教科书，但我还没有看到一本真正通俗易懂的数论教科书。

Answer 3

谁说它的散列性很好？

哈希函数将输入(在本例中为字符串)映射到输出(在本例中为unsigned int )。输入的大小是(number of usable characters) ^ number of characters in the string，其中^是“的幂”。

如果输入字符串只能包含字符0和1，则输入的大小将为2^ number of characters in the string

这意味着有一个“字符串中的字符数”，其中输入的大小将大于输出的大小。

如果您希望在hash_map或任何其他数据结构中使用哈希函数，请确保将其调优到您的特定输入。

在您的特定情况下，通用散列函数可能不是最优的。专门为某些输入设计的散列函数(这很可能就是这样的函数)在您的输入上的效果可能会明显变差。