c++ - 有序和无序映射

Question

我正在尝试理解有序和无序 map

据我所知，有序 map 会对您的列表进行排序，而无序 map 不会对其进行排序。以此为基础site

但是为什么这段代码还是被排序了

std::unordered_map<std::string, int> map;

map.insert(std::make_pair("hello", 1));
map.insert(std::make_pair("world", 2));
map.insert(std::make_pair("call", 3));
map.insert(std::make_pair("ZZ", 4));

for(auto it = map.begin(); it != map.end();it++)
{
    std::cout << it->first << std::endl;
}

结果:

world
hello
call
ZZ

我不明白。应该先说 hello，然后是 world，然后再打电话，然后是 ZZ。如果世界的无序容器不应该对它进行排序，那么世界是如何首先出现的呢？

Answer 1

std::hash<std::string>为您的输入键生成哈希值。然后，对这些哈希值进行转换，以获得映射中存储桶的有效索引(人们能想到的最基本的索引是简单的模数)。这些操作需要恒定的时间并为您提供元素的位置。为了从转换后的哈希中获取好的项目，您需要将其放置在正确的位置。这就是为什么您会观察到输入的明显随机顺序。

现在您可以对计算索引的顺序做出没有假设。假设您要在 map 中添加更多字符串。也许某些字符串需要重新哈希，并且您的输入字符串可能会以另一种顺序出现。

这与插入顺序无关，没有理由保留，数据结构的目的是将项目放置在适当的位置，以便可以在摊销常数时间内检索它们(此处为将它们放置在转换后的哈希值给出的索引处)。