对于给定的编译器，无序映射的顺序是否始终相同？

Question

我刚刚在代码中发现了一个错误，该错误取决于元素存储在

unordered_map

中的顺序。好吧，没什么大不了的，我会解决它。我的问题只是出于好奇，想了解不同编译器中的不同实现。

在我的计算机（linux

g++

）上编译时，我的单元测试始终有效，因为

unordered_map

的顺序始终相同，并且顺序不会触发我的错误。

当在另一台计算机和架构（mac M1，

clang++

）上编译时，我的错误总是会被触发，因为元素总是以相同的顺序出现，这与

g++

不同。

当在我的计算机上编译时带有

clang++

：没有错误。

在我的具体情况下，

unordered_map

的键是

int

，哈希值是

int

的默认值，我没有使用自定义哈希函数。

我的问题是：

unorderd_map

的顺序如何取决于编译器的实现？我一直认为它有点随机，但我错了，它对于我测试的每个编译器都是稳定的。标准对此有何规定？订购

unordered_map

的典型实现是什么？

Answer 1

哈希函数确定元素被放置在哪个桶中。

std::unordered_map<Key,T>

使用

std::hash<Key>

作为默认哈希器。来自cppreference：

实际的哈希函数取决于实现，并且不需要满足除上述指定之外的任何其他质量标准。值得注意的是，一些实现使用简单的（身份）哈希函数将整数映射到自身。换句话说，这些哈希函数旨在与无序关联容器一起使用，但不能作为加密哈希等使用。

这意味着您得到的结果顺序取决于实现。

我认为散列 int 在某种程度上是标准的。

定义的实现是“某种标准”；）。哈希函数仍然是研究的主题。选择最佳哈希值并不简单，如果标准能够修复一个目前最先进的特定哈希值，但在一年左右的时间内就会过时，那就糟糕了。

Answer 2

对于给定的编译器，无序映射的顺序是否始终相同？

没有。

这里有一些事情在起作用：

• 元素散列到的存储桶取决于：
  • 使用的哈希函数，虽然

    std::hash<int>

    是实现定义的，但据我所知，过去几十年来所有版本的 GCC、Clang 和 Visual C++ 都使用了身份哈希
  • bucket_count，因为

    size_t

    返回的

    std::hash

    值一般是

    %

    -ed或

    &

    -ed到当前

    bucket_count()

    ； GCC 使用质数进行存储桶计数，而 Visual C++ 使用 2 的幂（更容易发生冲突，但按位与比 mod 运算更快）；虽然标准中指定了重新哈希发生的默认值

    max_load_factor()

    （1.0），但表的初始大小和重新哈希期间增长的量未指定
• 一旦识别了存储桶，就取决于实现是否在与该存储桶关联的元素链的开头、结尾或中间的某个位置插入元素
• 如何编排迭代取决于实现；对于 GCC，实际上有一个所有键/值节点的单链表，并且在不引用存储桶的情况下进行迭代；该列表中具有散列到同一存储桶的键的所有节点都在单链表中分组在一起（以未指定的顺序），存储桶有效地将迭代器保存到单链表中，但可以做出其他选择（尽管实现 O( 1）在大多数元素已被删除的大表中，迭代器前进无法通过检查每个桶来完成，因此需要一些技巧）
• 重新散列/调整表大小后具有相同散列的相对顺序元素具有哪些未指定（即它们如何链接到新的较大表中）

因此，即使哈希值相同，很多因素也可能导致迭代发生变化。使用相同的键完成相同的插入/擦除操作后，没有特别的理由期望迭代顺序会发生变化对于相同的标准库实现（这里比编译器本身更相关），但也不能保证。