在STL中STL

Question

與C++ STL中的map和hashmap有什麼區別，有兩個map，map和hashmap。任何人都知道他們的主要區別？

Answer 1

地圖採用了紅黑樹的數據結構，所以你把元素有排序，插入/刪除是O（日誌（N））。元素需要至少實現operator<。

散列映射使用散列，所以元件未排序，插入/刪除是O（1）。元素至少需要實現operator==，並且您需要散列函數。

Answer 2

map是紅黑樹，O(log(n))訪問時間。 hash_map（這不是標準，然而unordered_map將成爲標準）使用（在概念上）一個在鏈表的陣列的關鍵字作爲索引的散列，並因此具有的O(1)最好的情況存取時間和O(n)最壞情況。

見http://en.wikipedia.org/wiki/Red-black_tree

Answer 3

主要區別在於搜索時間。

的幾個數據是更好的地圖

的大量數據是更好的HashMap

反正前面給出的答案軟件Tecnical是正確的。

Answer 4

hash_map使用散列表。理論上這是「不變的」時間。大多數實現使用「碰撞」散列表。會發生什麼事在現實中是：

• 它創建了一個大桌子
• 你必須爲你的對象「散列」功能，生成您隨機發生在表（隨機尋找，但是哈希函數永遠會返回與你的對象相同的值），通常這是實際的32位（或64位）散列值與表的大小的模。
• 該表查看空間是否可用。如果是這樣，它將項目放在表格中。如果不是，它會檢查是否存在您正在嘗試插入的元素。如果是這樣，它是重複的，所以沒有插入。如果不是，則稱爲「碰撞」，它使用一些公式來查找另一個單元格，並繼續執行，直到它找到一個重複單元格或一個空單元格。
• 當表格被填滿太多時，它會調整大小。一個有效的（及時的）實現將所有的原始散列值與元素一起存儲起來，因此當它這樣做時不需要重新計算散列值。此外，比較哈希通常比比較元素更快，所以它可以在搜索時做到這一點，以消除大部分碰撞作爲前期步驟。
• 如果你從不刪除任何東西，那很簡單。但是刪除元素會增加額外的複雜性。一個已經被刪除的元素的單元格與一直處於空白狀態的單元格處於不同的狀態，因爲您可能發生了衝突，並且如果您只是將其清空，則將找不到這些元素。所以通常有一些「標記」。當然，現在當我們想要重用單元格時，如果存在重複的更低下（在這種情況下，我們無法在此單元格中插入），我們仍然不得不減弱，然後記住重新使用已刪除的單元格。
• 通常的約束是你的對象必須執行檢查的平等，而是Dinkumware的（或者說是SGI）來實現他們與運營商<可能會比較慢，但有脫鉤的元件和相關容器的類型的優勢，他們可以存儲在中，儘管你仍然需要一個散列函數來存儲散列。

理論是，如果你有一個足夠大的表，操作是恆定的時間，即它不取決於你有實際元素的數量。當然，在實踐中，發生更多碰撞的元素越多。

std :: map使用二叉樹。沒有必要爲一個對象定義一個散列函數，只是嚴格地排序比較。插入時，向下遞歸搜索樹以找到插入點（以及是否有任何重複項）並添加節點，並且可能需要重新平衡樹，以便樹葉的深度永遠不會超過1。再平衡時間也與樹的深度有關，所以所有這些操作都是O（log N），其中N是元素的數量。

散的優點是複雜 樹的優點是：

• 完全可擴展的。它只使用它需要的東西，不需要一個巨大的表格或預先佔據表格的大小，雖然哈希每個元素可能需要比樹更少的「包袱」。
• 不需要首先進行哈希，如果數據集不是很大，那麼對於一個好的函數來說，這可能需要比比較更長的時間。

另外一個問題與std::map是，它使用一個單一的嚴格有序的比較函數，而該返回-1，0或1將是一個很大更有效率，特別是最常用的鍵「比較」功能類型，std :: string，它已經實現了這個功能（它是char_traits::compare）。 （這種效率低下的前提是要檢查x==y，你檢查x<y和y<x，這樣你就可以進行兩次比較了，每次查找只做一次）。