是否有意義使用std :: unordered_map <int, int>而不是std :: map <int, int>？

Question

std::unordered_map<int, int>應該比std :: map`更快嗎？我不關心順序，只是快速查找，所以我認爲我應該使用哈希表。但後來我想也許它會嘗試另外哈希我的密鑰或類似的東西（我不需要）？

和一個相關的問題：我需要通過int鍵檢索int值。我應該使用unordered_map<int, int>還是unordered_set<pair<int, int> >（在這種情況下，我需要爲我的配對正確實現散列函數）？

Answer 1

map<T,K>和unordered_map<T,K>之間的區別在於第一個實現依賴於一棵樹，而第二個實現依賴於散列圖。

這意味着基本操作（get和set）的複雜性對於map是對數，而對於unordered_map是複數。

有在任何情況下其他方面：一個unordered_map可能需要在達到它的負載因數時的翻版（這需要時間和可以是不可預知的），而正常map不涉及這種問題。此外，unordered_map實現可以使用分隔鏈接與桶，所以如果它碰巧有很多碰撞，複雜性變得恆定+線性檢索的關鍵。

我建議你用一些與你需要的模式相似的數據對兩個結構進行基準測試，這將會使你的選擇。

因爲它已經實施，您不需要爲unordered_map定義您自己的hash<int>。