提高:: unordered_map是...订购？ [英] boost::unordered_map is... ordered?

问题描述

我有一个boost :: unordered_map，但它似乎是为了，给我：你就错了的压倒一切的感觉。为什么输出到这一点是为了？我会一直期待的底层散列算法有随机顺序如下：

I have a boost::unordered_map, but it appears to be in order, giving me an overwhelming feeling of "You're Doing It Wrong". Why is the output to this in order? I would've expected the underlying hashing algorithm to have randomized this order:

#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;
}

......给我......

...gives me...

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

---

升压后的源$ C ​​$ C的检查：

---

Upon examination of boost's source code:

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

...这将解释。下面的答案保持较高层次的思维，还有，我发现有用的。

...which would explain it. The answers below hold the higher level thinking, as well, which I found useful.

推荐答案

虽然因为我不是一个C ++的人，我不能升压内部说话，我可以建议可能会缓解你的关注一些高层次问题

While I can't speak to the boost internals as I'm not a C++ guy, I can propose a few higher-level questions that may alleviate your concerns:

1）什么是一个无序地图的保证？假设你有一个有序图，你想创建一个地图，并不能保证订货。最初的实现可以简单地使用有序图。它几乎从来没有一个问题，提供的强大的比你做广告的保证。

1) What are the guarantees of an "unordered" map? Say you have an ordered map, and you want to create a map that does not guarantee ordering. An initial implementation may simply use the ordered map. It's almost never a problem to provide stronger guarantees than you advertise.

2）哈希函数是什么，散列点¯x - > int类型。如果你已经有了一个整数，你可以使用的标识功能。虽然它可能不是最有效的在所有情况下，能解释一下你所看到的行为。

2) A hash function is something that hashes X -> int. If you already have an integer, you could use the identity function. While it may not be the most efficient in all cases, it could explain the behavior you're seeing.

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

Basically, seeing behavior like this is not necessarily a problem.

这篇关于提高:: unordered_map是...订购？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！