17

我知道将无限数量的字符串散列到 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>or 其他人，但我想知道std::hash. 我用错了吗？我不应该以某种方式“播种”它吗？

4

5 回答 5

28

你的使用没有问题std::hash。问题是std::hash<std::string>与 Visual Studio 2010 捆绑的标准库实现提供的专业化只需要字符串字符的子集来确定哈希值（可能是出于性能原因）。巧合的是，具有 14 个字符的字符串的最后一个字符不属于该集合，这就是两个字符串产生相同哈希值的原因。

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

有关详细信息，请参阅头文件中的实现xfunctional（从我的副本中的第 869 行开始）和 C++ 标准的第 17.6.3.4 节（最新公开草案）。

如果你绝对需要一个更好的字符串散列函数，你应该自己实现它。其实没那么难。

于 2011-11-01T16:24:03.240 回答
11

标准未指定确切的哈希算法，因此结果会有所不同。如果字符串长度超过 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 ;
    }
};

梅森素数哈希：

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 散列更好，但梅森素数散列在很多机器上会更快，因为乘以 127 通常比乘以 16777619 快得多。）

于 2011-11-01T16:44:03.050 回答
3

您应该可能会得到不同的哈希值。我得到不同的哈希值（GCC 4.5）：

哈希测试.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
于 2011-11-01T15:37:49.313 回答
2

你没有种子散列函数，你最多只能加盐“他们”。

该功能以正确的方式使用，这种碰撞可能只是偶然的。

除非您使用随机键执行大规模测试，否则您无法判断散列函数是否分布不均。

于 2011-11-01T15:26:25.340 回答
0

TR1 哈希函数和最新标准为字符串等内容定义了适当的重载。当我使用 std::tr1::hash (g++ 4.1.2) 运行此代码时，我得到这两个字符串的不同哈希值。

于 2011-11-01T15:26:39.777 回答