的hash_map是节省每个键/值对即使当密钥是相同

嗨，我使用的hash_map为涉及字符串彼此，与此代码：的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 . . .

这是怎么发生的？我曾尝试每次都打印哈希，但哈希是相同的。

来源

2010-11-17 James Feder

从你的一些例子的细节，它看起来像你使用MSVC。微软的hash_map使用了一个比较函数，它与散列函数一起工作，为散列到相同值的键提供排序。这与SGI的hash_map规格不同。具体地（从http://msdn.microsoft.com/en-us/library/1s1byw77.aspx）：

对于任何值Key类型序列中先_Key2并具有相同的散列值（由散列函数返回值）的_Key1，hash_comp(_Key2, _Key1)是假的。该函数必须对Key类型的值进行总排序。由hash_compare提供的函数返回comp(_Key2, _Key1)，其中comp是Traits类型的存储对象，您可以在构造对象时指定该对象。对于默认的Traits参数类型less<Key>，排序键不会减少值。

因此，虽然更改比较函数返回str1 != str2似乎适用于您的测试，但它不是真的正确。它会混淆hash_map两种不同的字符串碰巧具有相同的哈希码的情况。

来源

2010-11-17 04:31:38

那我该怎么做呢？我无法从你粘贴的信息中收集到什么。 – 2010-11-17 04:43:52

@James：我想你只需要'返回（str1 2010-11-17 18:46:54

其中一个原因hash_map没有把它变成C++ 0x的原因是有很多冲突的实现，而且没有实体规范。

我会切换到C++ 0x接受的内容。 std::unordered_map可能有一个长而笨拙的名字，但是语义是明确的;它会而不是存储重复密钥（为此，您将使用std::unordered_multimap来代替）。

来源

2010-11-17 04:10:03

哦，显然我使用

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; 
}

来源

2010-11-17 04:12:00

的hash_map是节省每个键/值对即使当密钥是相同

回答

相关问题