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++人员而无法与内部人员交谈,但我可以提出一些可以减轻您担忧的更高级问题:

1)"无序"地图的保证是什么？假设您有一个有序的地图,并且您想创建一个不保证订购的地图.初始实现可以简单地使用有序映射.提供比您做广告更有力的保证几乎不是问题.

2)哈希函数是哈希X - > int的东西.如果您已经有一个整数,则可以使用标识函数.虽然在所有情况下它可能不是最有效的,但它可以解释您所看到的行为.

基本上,看到这样的行为不一定是个问题.

Answer 2

这可能是因为你的哈希是小整数.散列表通常计算放置项目的桶数,如下所示:bucket_index = hash%p其中p是素数,即散列表桶的数量,足以提供低频率的冲突.

对于整数,hash等于整数的值.你有很多数据,所以哈希表选择了一个大的p.对于任何大于i的p , bucket_index = i%p = i.

迭代时,哈希表按其索引的顺序返回其桶中的项目,对于您来说,这是键的顺序.:)

如果你想看到一些随机性,请尝试使用更大的数字.