unordered_map 的顺序是确定的吗？

Question

我想知道是否可以保证 unordered_map 的顺序在所有 CPU、线程等中始终相同。

我意识到特定顺序本身可能没有明显的模式（因此，“无序”映射），但是如果我在另一台机器上运行我的进程，或者连续多次运行，或者在不同的线程上运行，插入项目的顺序将始终如果哈希函数和插入顺序保持不变，是否会相同？换句话说，如果我的代码不改变，我的进程的每次执行都会导致映射的元素处于相同的顺序吗？

我已经运行了一些测试，插入后的项目顺序似乎每次都是相同的，但这可能只是侥幸，而且我只有这台机器可以测试。我需要知道顺序是否会受到任何其他因素的影响，例如 CPU/内存架构、操作系统（Windows 8 与 Windows 10）等。

Answer 1

TL;DR：可以这样做，但我不推荐这样做。如果可以的话，使用其他数据结构；你自己的哈希表，一个“treap”，一个平面数组，或者其他东西。

中项目的顺序std::unordered_map更依赖于标准库的实现，而不是硬件/CPU等。

因此，如果您在不同的硬件上使用相同的库实现，并提供自己的哈希函数（以确保它在运行中不是随机的 - 以对抗针对您的数据结构的 DoS 攻击）或其他硬件或操作系统相关的，那么你应该没问题。

然而，如果您在标准中寻找保证，您将找不到任何保证。唯一相关的保证是，在对象的同一实例中，相同的键将散列到相同的存储桶。我认为即使对于地图的不同实例也没有保证，而且我从（痛苦的）个人经验知道，应用程序的不同运行之间不存在一致性。

但并非所有希望都破灭了！如果您坚持使用相同的实现unordered_map，并使用您自己的哈希函数，并查看实现以确保没有隐藏的意外（任何对硬件/操作系统/时间/RNG/等的依赖应该相对容易点）你可以管理它。

请注意，由于您似乎在 Windows 上并且可能使用 MSVC，因此unordered_map默认哈希算法的默认值在同一编译二进制文件的运行中根本不是顺序一致的（至少在 2013/2015 IIRC 中不是这样）。

另一件要记住的事情是，如果您认真对待一致性，则必须确保静态链接到 CRT 。如果您链接到 DLL 版本，则将来的某些补丁/更新可能会在您发布应用程序后更改应用程序的行为。