为什么我的unordered_map会自动排序？

Question

我最近在玩 C++ 标准库中新加入的 unordered_map 。 我写了如下代码，创建一个 unordered_map ，填充它，再将其打印出来:

    unordered_map<int,string> m1;

    m1[5]="lamb";
    m1[2]="had";
    m1[3]="a";
    m1[1]="mary";
    m1[4]="little";
    m1[7]="fleece";
    m1[6]="whose";
    m1[10]="fleecey";
    m1[8]="was";
    m1[9]="all";

for(unordered_map<int,string>::const_iterator i = m1.begin(); i != m1.end(); ++i)
cout<<i->first<<" "<<i->second<<endl;

然而，我得到的输出结果是这样排序的：

1 mary
2 had
3 a
4 little
5 lamb
6 whose
7 fleece
8 was
9 all
10 fleecey

但我不想为了让我的映射有序而付出代价！这就是我使用unordered_map的原因...这是怎么回事？

另外注意：我正在使用gcc版本4.3.4 20090804（发布）1（GCC），并且像这样编译

- Jimmy

---

很可能，对于大小<= sizeof(std :: size_t)的整数类型的哈希函数仅是恒等函数。 - ildjarn

试试把 m1[10]="fleecey"; 改成类似于 m1[154297]="fleecey"; 的东西，感受一下乐趣 :) - JohannesD

Answer 1

“无序”并不意味着它会随机存储项目或保持您在地图中放置它们的顺序。它只是意味着您不能依赖任何特定的排序方式。您不需要为排序付出代价，相反 - 实现并没有明确地对项目进行排序，它是一个哈希映射，并以任何它喜欢的方式存储其元素，通常是一种非常高效的方式。恰好使用这些键和地图上的这个数字和操作顺序时，哈希算法和地图的其他内部工作方式最终以看起来有序的方式存储项目。例如，字符串可能导致表面上随机化的布局。

另外一方面，这可能是由于地图使用将（至少一些）整数映射到自身的哈希，并使用哈希的低位（与地图大小要求一样多）来确定底层数组的索引（例如，CPython 这样做 - 并且通过一些非常聪明的添加来相对简单而有效地处理冲突；因此，CPython 字符串和元组的哈希非常可预测）。

- user395760

---

是的，它被全部散列了。谢谢。 - Jimmy

Answer 2

为了您的娱乐，这里是libc++的输出结果，它还为std::hash<int>提供了一个身份函数。

9 all
8 was
10 fleecey
6 whose
7 fleece
4 little
1 mary
3 a
2 had
5 lamb

有几种实现哈希容器的方法，每种方法都有其自身的权衡。

- Howard Hinnant