与std::hash发生意外冲突

Question

我知道将无限数量的字符串散列到32bint必然会产生冲突，但我希望从散列函数中得到一些很好的分布。

这两个字符串具有相同的散列，这不是很奇怪吗？

size_t hash0 = std::hash<std::string>()("generated_id_0");
size_t hash1 = std::hash<std::string>()("generated_id_1");
//hash0 == hash1

我知道我可以使用boost::hash<std::string>或其他工具，但我想知道std::hash出了什么问题。我用错了吗？难道我不应该以某种方式“播种”它吗？

Answer 1

您使用std::hash没有任何问题。问题是，与Visual Studio2010捆绑在一起的标准库实现提供的专门化std::hash<std::string>只使用字符串字符的子集来确定散列值(可能是出于性能原因)。巧合的是，包含14个字符的字符串的最后一个字符不是该集合的一部分，这就是为什么两个字符串产生相同的散列值的原因。

据我所知，此行为符合标准，该标准只要求对具有相同参数的散列函数的多次调用必须始终返回相同的值。但是，哈希冲突的概率应该是最小的。VS2010实现满足了强制部分，但没有考虑到可选部分。

有关详细信息，请参阅头文件xfunctional (从我的副本中的第869行开始)和C++标准(latest public draft)的§17.6.3.4中的实现。

如果你确实需要一个更好的字符串散列函数，你应该自己实现它。实际上是not that hard。

Answer 2

标准中没有指定确切的散列算法，因此结果会有所不同。如果字符串超过10个字符，VC10使用的算法似乎不会考虑所有字符；它以1 + s.size() / 10为增量前进。这是合法的，尽管从QoI的角度来看，这是相当令人失望的；众所周知，对于一些典型的数据集(如URL)，这种哈希码的性能非常差。我强烈建议您将其替换为FNV散列或基于Mersenne素数的散列：

FNV哈希：

struct hash
{
    size_t operator()( std::string const& s ) const
    {
        size_t result = 2166136261U ;
        std::string::const_iterator end = s.end() ;
        for ( std::string::const_iterator iter = s.begin() ;
              iter != end ;
              ++ iter ) {
            result = (16777619 * result)
                    ^ static_cast< unsigned char >( *iter ) ;
        }
        return result ;
    }
};

Mersenne prime散列：

struct hash
{
    size_t operator()( std::string const& s ) const
    {
        size_t result = 2166136261U ;
        std::string::const_iterator end = s.end() ;
        for ( std::string::const_iterator iter = s.begin() ;
              iter != end ;
              ++ iter ) {
            result = 127 * result
                   + static_cast< unsigned char >( *iter ) ;
        }
        return result ;
    }
};

( FNV散列应该更好，但Mersenne prime散列在许多机器上会更快，因为乘以127通常比乘以2166136261快得多。)

Answer 3

您可能会得到不同的哈希值。我得到了不同的哈希值(GCC 4.5)：

hashtest.cpp

#include <string>
#include <iostream>
#include <functional>
int main(int argc, char** argv)
{
size_t hash0 = std::hash<std::string>()("generated_id_0");
size_t hash1 = std::hash<std::string>()("generated_id_1");
std::cout << hash0 << (hash0 == hash1 ? " == " : " != ") << hash1 << "\n";
return 0;
}

输出

# g++ hashtest.cpp -o hashtest -std=gnu++0x
# ./hashtest
16797002355621538189 != 16797001256109909978