hash_map 会保存每个键/值对，即使键相等

Question

嘿伙计们，我正在使用 hash_map 将字符串相互关联，代码如下：

#include <string>
#include <iostream>
#include <hash_map>

using namespace std;
using namespace stdext;

struct StrCompare : public stdext::hash_compare<string> {
 unsigned int operator()(const string str) const {
  unsigned int hash = 0;
  unsigned int len = str.length();

  for (unsigned int i = 0; i < len; i++)
   hash = 31 * hash + str[i];

  return hash;
 }

 bool operator()(const string str1, const string str2) const {
  return str1 == str2;
 }
};

int main() {
 hash_map<string, string, StrCompare> m;

 m["asdf"] = "fe";
 m["asdf"] = "asdf";

 for (hash_map<string, string, StrCompare>::iterator i = m.begin(); i != m.end(); ++i)
  cout << i->first << " " << i->second << endl;

 system("PAUSE");
}

问题是输出是：

asdf asdf
asdf fe
Press any key to continue . . .

为什么会发生这种情况？我每次都尝试打印哈希值，但哈希值是相同的。

Answer 1

hash_map 没有进入 C++0x 的原因之一是存在许多相互冲突的实现，而且缺乏可靠的规范。

我会改用 C++0x 所接受的内容。 std::unordered_map 可能有一个又长又笨拙的名字，但语义是明确定义的；它不会存储重复的键（为此您可以使用 std::unordered_multimap 来代替）。

Answer 2

从示例的一些细节来看，您似乎正在使用 MSVC。 Microsoft 的 hash_map 使用比较函数与哈希函数结合使用，为哈希为相同值的键提供排序。这与 SGI 的 hash_map 规范不同。具体来说（来自 http://msdn.microsoft.com/en-us/library/ 1s1byw77.aspx):

对于序列中位于 _Key2 之前且具有相同哈希值（哈希函数返回的值）的 Key 类型的任何值 _Key1 ），hash_comp(_Key2, _Key1) 为 false。该函数必须对 Key 类型的值进行全排序。 hash_compare 提供的函数返回 comp(_Key2, _Key1)，其中 comp 是一个 Traits 类型的存储对象，您可以在构造时指定对象hash_comp。对于默认的 Traits 参数类型 less，排序键的值永远不会减少。

因此，虽然将比较函数更改为 return str1 != str2 似乎适用于您的测试，但实际上并不正确。在两个不同的字符串碰巧具有相同的哈希码的情况下，它会混淆 hash_map。

Answer 3

哦，显然我使用了

bool operator()(const string str1, const string str2) const

错误的功能。而不是

bool operator()(const string str1, const string str2) const {
    return str1 == str2;
}

应该是

bool operator()(const string str1, const string str2) const {
    return str1 != str2;
}