0

我有一个很长的字符串，我需要比较它是否相等。由于逐个字符比较它们非常耗时，我喜欢为字符串创建一个哈希。

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

我对上述假设是否正确？

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

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

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

4

5 回答 5

4

为了在这种情况下有用，哈希码必须快速计算。使用大于硬件支持的最大字（通常为 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;
}

然而，使用这样的散列可能不会有好处，除非大多数比较是使用不相等但具有较长公共初始序列的字符串。请记住，如果哈希值相等，您仍然需要比较字符串，并且该比较只需要直到第一个不相等的字符。（事实上​​，我见过的大多数比较函数都是从比较长度开始的，并且仅在字符串长度相等时才比较字符。）

于 2013-08-20T12:04:28.657 回答
1

您可以使用许多散列算法。

如果您想自己实现一个，那么一个简单的方法是获取每个字符的ascii并将其与0对齐（即a = 1，b = 2 ...）并将其与字符串中的字符索引相乘. 继续添加这些值并将其存储为特定字符串的哈希值。

例如， abc 的哈希值将是：

HASH("abc") = 1*1 + 2*2 + 3*3 = 14;

随着字符串长度的增加，碰撞的可能性会降低（考虑到你的字符串会很长）。

于 2013-08-20T11:22:43.367 回答
0

好吧，我将首先比较字符串长度。如果它们匹配，那么我将开始使用一种算法进行比较，该算法使用随机位置来测试字符相等性，并在第一个差异处停止。随机位置将从一个 stringLength 大小的向量中获得，其中填充了从 0 到 stringLength-1 的随机整数。不过，我还没有测量过这种方法，这只是一个想法。但这会为您省去哈希冲突的顾虑，同时减少比较时间。

于 2013-08-21T07:52:33.547 回答
0

这真的取决于你的硬性要求是什么。如果您有硬性要求，例如“搜索可能永远不会花费这么多时间”，那么可能没有适用的解决方案。如果您的目的只是为了加快大量搜索的速度，那么一个简单的短哈希就可以了。

虽然将 1000 个字符的字符串散列为整数（单个 32 位或 64 位数字）通常是正确的，但最终会产生冲突，但这不是值得关注的问题。
10 个字符的散列也会产生冲突。这是 1000 > 10 这一事实的必然结果。对于每个 10 个字符的散列，存在 100 个 1000 个字符的字符串1。

重要的问题是你是否真的会看到碰撞，你会看到它们的频率，以及它是否重要。您是否（或有多大可能）看到冲突不是取决于字符串的长度，而是取决于不同字符串的数量。
如果您使用 32 位哈希对 77,100 个字符串（长度超过 4 个字符）进行哈希处理，那么您有 50% 的机会遇到每个新哈希的冲突。在 25,000 个字符串中，可能性仅为 5-6% 左右。在 1000 个字符串中，可能性约为 0.1%。
请注意，当我说“50% at 77,100 个字符串”时，这并不是意味着您实际遇到碰撞的机会如此之高。这只是有两个具有相同哈希值的字符串的机会。除非大多数琴弦都是这种情况，否则实际击中一根琴弦的机会再次低很多。

这意味着对于大多数用例来说不多也不少，这根本不重要。除非您想散列数十万个字符串，否则现在不要担心，使用 32 位散列。
否则，除非您想对数十亿个字符串进行哈希处理，否则不要在这里担心并使用 64 位哈希。

问题是，您必须准备好在任何情况下处理碰撞，因为只要您有 2 个字符串，碰撞的可能性就永远不会完全为零。即使仅将 2 或 3 个 1000 字符的字符串散列到 500 字节的散列中，原则上也可能会发生冲突（非常不可能但可能）。
这意味着如果哈希在任何一种情况下都匹配，则无论您的哈希有多长（或多好或多坏），您都必须进行字符串比较。

如果碰撞不是每次都发生，那么它们完全无关紧要。如果您的表中有很多冲突并且遇到一个，例如，在 10,000 次查找中有 1 次（这是很多！），它没有实际影响。是的，您必须在 10,000 次查找中进行一次无用的字符串比较，但其他 9,999 次仅通过比较单个整数来工作。除非您有严格的实时要求，否则可衡量的影响完全为零。
即使您在每 5 次搜索时完全搞砸并遇到冲突（非常糟糕的情况，这意味着大约 8 亿个字符串对发生冲突，这只有在至少 16 亿个字符串的情况下才有可能），这仍然意味着5 次搜索中有 4 次没有发生冲突，因此您仍然会丢弃 80% 的不匹配项而不进行比较。

另一方面，生成 10 个字符的散列既麻烦又慢，而且您可能创建的散列函数比现有的 32 位或 64 位散列具有更多的冲突（由于糟糕的设计）。
加密散列函数当然更好，但它们的运行速度也比非加密对应的慢，并且存储 16 或 32 字节散列值所需的存储空间也大得多（对大多数人来说几乎没有任何好处）。这是空间/时间的权衡。

就个人而言，我只会使用 djb2 之类的东西，它可以用 3 行 C 代码实现，效果很好，而且运行速度非常快。当然还有许多其他的哈希函数可以使用，但我喜欢 djb2 的简单性。

有趣的是，在阅读了 James Kanze 的回答后，发布的代码似乎是 djb2 的变体，只是种子和乘数不同（分别为 5381 和 33）。
在同一个答案中，关于首先比较字符串长度的评论也是一个很好的提示。值得注意的是，您也可以将字符串的长度视为“散列函数”的一种形式（尽管它相当弱，但通常是“免费”提供的）。

1但是，字符串不像散列那样是一些“随机二进制垃圾”。它们是结构化的低熵数据。到目前为止，这种比较并不真正成立。

于 2013-08-20T12:20:04.017 回答
0

有许多已知的哈希算法可用。例如 MD5、SHA1 等。您不需要实现自己的算法，而是使用可用的算法之一。使用您选择的搜索引擎来查找类似这样的实现。

于 2013-08-20T11:15:58.127 回答