boost :: unordered_map是...命令？

我有一个boost :: unordered_map，但它似乎是按顺序的，给我一种压倒性的感觉：“你做错了”。为什么按顺序输出？我会一直期待的底层散列算法已经随机顺序如下：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; 
}

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

的后提升的源代码检查：

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

......这将解释它。下面的答案也支持更高层次的思考，我觉得这很有用。

来源

2010-06-14 Thanatos

而不是插入'我'，尝试插入（并在插入时同时打印到控制台，同时插入）随机数，看看结果是否仍然有序，或者他们只是按他们插入的顺序排序.. 。 – FrustratedWithFormsDesigner 2010-06-14 18:32:52

如果您需要随机订购，请使用std :: random_shuffle :) – Drakosha 2010-06-14 18:36:10

@Drakosha：我不是在寻找随机订单，但按顺序unordered_map让我感到不安。（非最小测试用例有几千个整数，但它们仍然是有序的） – Thanatos 2010-06-14 18:38:53

虽然因为我不是一个C++的人，我不能到升压内部讲，我可以建议，可以减轻你的疑虑一些更高层次的问题：

1）什么是一个企业的担保“无序”地图？假设你有一个有序的地图，并且你想创建一个不保证排序的地图。初始实现可以简单地使用有序地图。提供更强的担保几乎不会出现问题，而不是您做广告。 2）散列函数是散列X - > int的东西。如果你已经有了一个整数，你可以使用标识函数。虽然它可能不是最有效的，但它可以解释你所看到的行为。

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

来源

2010-06-14 18:36:01

我并没有期待使用哈希函数的身份函数，但似乎这正是推动力所在。我想如果没有关于输入的领域知识，这样的散列将会和其他任何东西一样工作。 – Thanatos 2010-06-14 18:45:30

@Thanatos - 由于哈希函数的结果是一个'size_t'（至少对于'boost :: unordered_map'）并且一个'int'将总是适合一个'size_t'，所以除了一个标识之外没有任何理由做任何事情函数来散列一个'int'。 – 2010-06-14 18:53:12

@Michael Burr - 我不关心语言的语义 - 我正在研究散列函数的目的是防止输入之间的冲突，以便散列表有机会成为O（1）。我习惯于看到相当随机的散列函数输出。 – Thanatos 2010-06-14 18:56:09

这可能是因为你的哈希是小整数。哈希表通常会计算这样的项目的桶数：bucket_index = hash%p其中p是一个质数，它是哈希表桶的数量，它足以提供较低的冲突频率。

对于整数散列值等于整数的值。你有很多数据，所以hashtable选择一个大的p。对于任何大于我的p，bucket_index = i%p = i。

迭代时，哈希表按索引顺序从其存储区中返回项目，这对您而言是键的顺序。 :)

如果您想查看一些随机性，请尝试使用较大的数字。

来源

2010-06-14 18:38:11 Rotsor

你做得对。 unordered_map不声称有随机顺序。事实上，它并没有声明任何顺序。你不应该在秩序方面任何东西期望，并且这是无序的！

来源

2010-06-16 22:32:44 John

-3

这是因为默认情况下，按照'按键的插入顺序'排序，如果你插入按键1,2,3,4,5并打印它，你总会得到1,2,3,4,5所以它看起来有序。尝试添加随机密钥值并查看结果。每次都不一样，因为它不应该是。

来源

2012-05-15 00:57:36 theiOSguy

boost :: unordered_map是...命令？

回答

相关问题