C++字符串散列哈希字符串或内存地址吗？

Question

我之前从未研究过散列算法,我很惊讶当使用std :: unordered_map时我发现散列函数(我认为)实际上是散列内存地址,而不是字符串.如果我错了,请纠正我,但我发现这只是通过更改原始字符串并将其添加到我的unordered_map,并且当内存地址(指针)相同时它从未添加任何内容.

在下面的例子中,是否添加新密钥取决于std :: string是否重新分配到另一个内存区域:

std::unordered_map<const char*, char*> myMap;

std::string myString = "Key1";

myMap[myString.c_str()] = "someVal";    // <--- Adds a new key, size is now 1
myString = "Key2";
myMap[myString.c_str()] = "someVal";    // <--- Doesn't add a new key "Key2" didn't need to be reallocated

但是当我在更改字符串时直接在模板中使用std :: string时,它会向我的地图添加另一个键,这样就表明unordered_map模板专门用于std :: string并实际散列字符串本身？如果它必须散列字符串本身,这会慢吗？

我提出这个问题的原因是,我所看到的教程似乎传达了这样的含义,即实际的字符串本身会被哈希化.即使在Stack Overflow上,我也看到人们会说出"由于性能原因,不需要检查整个字符串,只需要检查所需的字符数"(释义).

好吧,我得到的印象显然是字符串文字和指向字符串的指针,但不是std :: string类？

Answer 1

你误以为这const char*是一个字符串.它实际上是一个指针.因此,std::unordered_map<const char*, anything>使用指针(类型const char*)作为键,std::hash指针(哈希地址)的特化作为哈希键.

如果你想使用字符串作为键,你应该使用std::string,例如std::unordered_map<std::string, anything>.

编辑我还应该说使用指针代替字符串至少是危险的,但通常是不可能的.它不会做你的想法.问题是字符串(字符序列)及其地址(指针)不一定与程序的生命周期配对(尽管对于某些const char*对象可能也是如此).想想以下内容

std::unordered_map<const char*,int> map;
char str[11] = "bad";
map[str] = 2;           // hashes str = char*
auto x = map["bad"];    // hashes address of "bad"; x!=2

这表明使用地址作为键不能按预期工作:您无法从字符序列中获取元素("bad")