c++ - std::hash 可以为不同的字符串返回相同的值吗？

Question

下面的链接提到了碰撞的可能性，但我试图用它来查找重复条目:

http://www.cplusplus.com/reference/functional/hash/

我正在使用 std::hash<std::string>并将返回值存储在 std::unordered_set 中。如果 emplace 失败，我将标记字符串，因为它是重复的字符串。

Answer 1

哈希通常是从大空间值到小值空间的函数，例如从所有字符串的空间到 64 位整数。字符串比 64 位整数多得多，因此显然多个字符串可以具有相同的哈希值。一个好的散列函数是这样的，没有简单的规则将具有相同散列值的字符串关联起来。

所以，当我们想使用哈希来查找重复的字符串(或重复任何东西)时，它总是一个两阶段的过程(至少):

查找具有相同哈希值的字符串(即为您的字符串找到“哈希桶”)

将您的字符串与具有相同哈希值的其他字符串逐个进行比较。

std::unordered_set这样做 - 不要介意细节。请注意，它会为您执行此操作，因此您自己进行哈希处理是多余的，然后将结果存储在 std::unordered_set 中。 .

最后，请注意还有其他功能可以用于初始重复筛选 - 或用于在相同哈希值中进行搜索。例如，字符串长度:在逐个字符比较两个字符串之前，您检查它们的长度(您应该能够在不实际迭代字符串的情况下访问它们)；不同长度 -> 不等字符串。