哈希映射和樹映射的優點和缺點？

默認情況下，C++提供了一個基於樹的地圖。隨着升壓，你可以得到一個hashmap。哈希映射和樹映射的優點和缺點？

什麼是

C++的基於樹地圖和
Boost的哈希映射的優勢和劣勢？

2011-07-07 jmasterx

[Binary Trees vs. Linked Lists vs. Hash Tables]的可能重複（http://stackoverflow.com/questions/371136/binary-trees-vs-linked-lists-vs-hash-tables） – Nemo

樹= O（log（N）），散列= O（k）和O（1）關於N. – Damon

@Nemo：我不認爲這是重複的，因爲問題詢問了基於樹的地圖和boost的hashmap。 – 2011-07-07 19:18:00

C++ 0x/TR1還提供了unordered_map，它通常實現爲散列映射。

的區別是雙重的：

鍵類型。在有序地圖中，鍵類型必須遵守嚴格的弱排序，並且按照該順序維護條目。在無序映射中，密鑰類型必須相等，並且您必須提供散列函數h，以使h(Key)返回size_t [感謝Steve Jessop的澄清]。
訪問複雜度：在地圖大小n中，在有序地圖中插入/刪除/查找是O（log n）。在無序映射中，它通常是O（1），但最壞情況的行爲是O（n）（例如，如果所有鍵映射到相同的散列值）。

於是下令地圖提供了一個總的複雜性保障，而無序的地圖在良好的情況下提供了一個（更好）的複雜性，這取決於你的哈希函數的質量。

無序映射的內部實現複雜度大於有序映射，但您可以想象得到更好的訪問複雜性，因爲您獲得的功能較少，即無法免費進行排序。這是一個經典的交易。另一點：實際上，如果弱排序操作符計算起來很昂貴，就像字符串一樣，無序映射實際上可能會快很多，因爲哈希類型的比較速度非常快。另一方面，如果你的鍵類型是一個具有簡單散列函數的類型（就像任何內置的整型），並且如果你不需要排序，可以考慮使用一個無序的容器。

來源

2011-07-07 19:15:54

@Kerrick：你的意思是'operator size_t（const Key＆）'？你可以引用TR1（或C++ 0x）的部分，說你所要做的只是提供一個'operator size_t'？（不是說你錯了，只是說我沒有看到它，我認爲你必須專門研究'hash '來使用你自己的密鑰類型。） – Nemo

不，不是'operator size_t'，只是任何簽名函數size_t （const Key＆）'。像'size_t hash_my_int（const int＆x）{return x; }'。你必須在容器中指定函數'unordered_set '，或專門化'std :: hash'。 –

@Kerrik：好的。你可能想在你的回答中說清楚，因爲'size_t（const Key＆）'不是一個格式良好的表達式:-)。 – Nemo

散列表提供了非常快速的搜索訪問和對象的插入/刪除......這種操作的複雜度平均爲O（1），這意味着恆定的時間。這兩個操作的主要限制是散列算法的速度（對於某些類型的不是POD的對象，這些可能有點複雜，需要花費更多時間才能避免兩個不同對象哈希到的「碰撞」相同的值）。散列表的主要缺點是它需要很多額外的空間。

另一方面，二叉樹的插入和搜索時間相對較快，刪除和對象的複雜性與插入相同。由於二叉樹的工作方式，每個節點有兩個子節點，因此搜索和訪問時間（以及插入和刪除）需要O（log N）時間。所以binaty樹比hash表「慢」，但實現並不複雜（儘管平衡二叉搜索樹更復雜，以至於不平衡樹）。

二叉搜索樹的另一個副作用是，通過迭代容器從「第一個」元素到「最後一個」元素，可以獲得一個排序的對象列表，其中與hash-地圖，該列表不會被排序。因此，插入的額外時間也考慮到二叉搜索樹是排序插入的表面。例如，一組N個項目上的快速排序的複雜度與爲同一組N個項目構建平衡二叉搜索樹（即，紅/黑樹）的複雜度相同。這兩個操作都是O（N log N）。

來源

2011-07-07 19:15:59 Jason

哈希映射和樹映射的優點和缺點？

回答

相關問題