与std :: hash发生意外冲突

Question

我知道散列无限数量的字符串到32b int必须生成碰撞,但我期望从散列函数中得到一些不错的分布.

这两个字符串具有相同的哈希值是不是很奇怪？

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.问题是,std::hash<std::string>与Visual Studio 2010捆绑在一起的标准库实现提供的专业化只需要字符串字符的一个子集来确定哈希值(可能是出于性能原因).巧合的是,具有14个字符的字符串的最后一个字符不是此集合的一部分,这就是两个字符串产生相同散列值的原因.

据我知道这种行为是符合标准的,这符合要求只能使用相同的参数必须始终返回相同的值的散列函数多次调用.但是,哈希冲突的概率应该是最小的.VS2010实现满足强制部分,但未考虑可选部分.

有关详细信息,请参阅头文件中的实现xfunctional(从我的副本中的第869行开始)和C++标准的§17.6.3.4(最新的公共草案).

如果你绝对需要一个更好的字符串哈希函数,你应该自己实现它.实际上并不那么难.

Answer 2

标准未指定确切的哈希算法,因此结果会有所不同.如果字符串超过10个字符,VC10使用的算法似乎不会考虑所有字符; 它以增量为前进1 + s.size() / 10.这是合法的,尽管从QoI的角度来看,这是令人失望的; 已知这样的哈希码对于一些典型的数据集(例如URL)执行得非常差.我强烈建议你用FNV哈希或基于梅森素数的哈希替换它:

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 hash:

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主散列在很多机器上会更快,因为乘以127通常比乘以2166136261快得多.)