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是...命令？

回答

相關問題