c++ - boost::unordered_map 是……有序的？

Question

我有一个 boost::unordered_map，但它看起来是有序的，给我一种“你做错了”的强烈感觉。为什么这个输出是有序的？我本以为底层的哈希算法会随机化这个顺序:

#include <iostream>
#include <boost/unordered_map.hpp>

int main()
{
    boost::unordered_map<int, int> im;

    for(int i = 0; i < 50; ++i)
    {
        im.insert(std::make_pair(i, i));
    }

    boost::unordered_map<int, int>::const_iterator i;

    for(i = im.begin(); i != im.end(); ++i)
    {
        std::cout << i->first << ", " << i->second << std::endl;
    }

    return 0;
}

...给我...

0, 0
1, 1
2, 2
...
47, 47
48, 48
49, 49

---

在检查 boost 的源代码时:

inline std::size_t hash_value(int v)
{
    return static_cast<std::size_t>(v);
}

...这可以解释一下。下面的答案也包含更高层次的思考，我发现这很有用。

Answer 1

虽然我不是 C++ 专家，所以不能谈论 boost 的内部结构，但我可以提出一些更高层次的问题，这些问题可能会减轻您的顾虑:

1) “无序” map 的保证是什么？假设您有一个有序 map ，并且您想要创建一个不保证有序的 map 。初始实现可以简单地使用有序映射。提供比您宣传的更强的保证几乎从来都不是问题。

2) 哈希函数是对 X -> int 进行哈希处理的函数。如果您已经有一个整数，则可以使用恒等函数。虽然它可能不是在所有情况下都是最有效的，但它可以解释您所看到的行为。

基本上，看到这样的行为不一定是问题。