c++ - 在 C++ 中创建一个哈希码形成一个字符串

Question

我有一个很长的字符串，我需要比较它是否相等。因为一个字符一个字符地比较它们非常耗时，我喜欢为字符串创建一个散列。

我喜欢生成的哈希码是唯一的(或者生成两个具有相同哈希值的字符串的机会非常小)。我认为从字符串创建一个 int 是因为散列不足以消除具有相同散列码的两个不同字符串，所以我正在寻找一个字符串散列码。

我上面的假设对吗？

为了澄清，假设我有一个长度为 1K 的字符串，并且我创建了一个 10 个字符的哈希码，然后比较哈希码的速度提高了 100 倍。

我的问题是如何在 C++ 中创建这样的哈希码？

我正在使用 Visual Studio 2012 在 Windows 上进行开发。

Answer 1

要在这种情况下有用，散列码必须能够快速计算。使用比最大单词更大的任何东西硬件支持(通常是 64 位)可能是计数器富有成效的。不过，您可以尝试一下。我找到了以下工作相当不错:

unsigned long long
hash( std::string const& s )
{
    unsigned long long results = 12345; //  anything but 0 is probably OK.
    for ( auto current = s.begin(); current != s.end(); ++ current ) {
        results = 127 * results + static_cast<unsigned char>( *current );
    }
    return results;
}

使用像这样的散列可能没有什么好处，然而，除非大多数比较是与字符串不相等，但有很长的公共(public)初始序列。记住如果哈希值相等，你仍然需要比较字符串，并且该比较只需要进行到第一个不相等的字符。 (其实大部分比较我见过的功能从比较长度开始，并且只比较字符，如果字符串长度相等。)