實際上這個問題不光C++會遇到，其他所有語言的標準容器的實現及選擇上都是要考慮的。做應用程序你可能覺得影響不大，但是寫算法或者核心代碼就要小心了。今天改進代碼，順便又來溫習基礎功課了。

　　還記得Herb Sutter那極有味道的《C++對話系列》么，在其中《產生真正的hash對象》這個故事里就講了map的選擇。順便回顧一下，也講一下我在實用中的理解。

　　選擇map容器，是為了更快的從關鍵字查找到相關的對象。與使用list這樣的線性表容器相比，一可以簡化查找的算法，二可以使任意的關鍵字做索引，并與目標對象配對，優化查找算法。在C++的STL中map是使用樹來做查找算法，這種算法差不多相當與list線性容器的折半查找的效率一樣，都是O(log2N)，而list就沒有map這樣易定制和操作了。

　　相比hash_map，hash_map使用hash表來排列配對，hash表是使用關鍵字來計算表位置。當這個表的大小合適，并且計算算法合適的情況下，hash表的算法復雜度為O(1)的，但是這是理想的情況下的，如果hash表的關鍵字計算與表位置存在沖突，那么最壞的復雜度為O(n)。

　　那么有了這樣的認識，我們應該怎么樣選用算法呢？前兩天看Python文章的時候，不知道哪個小子說Python的map比c++的map快，如何如何的。但是他并不知道Python是默認使用的hash_map，而且這些語言特征本質上是使用c/c++寫出來的，問題在與算法和手段，而不是在于語言本身的優劣，你熟悉了各種算法，各種語言的細節、設計思想，還能在這偏激的嚷嚷孰好孰壞(片面與偏激的看待事物只能表明愚昧與無知，任何事物都有存在的價值，包括技術)。顯然C++的STL默認使用樹結構來實現map，是有考究的。

　　樹查找，在總查找效率上比不上hash表，但是它很穩定，它的算法復雜度不會出現波動。在一次查找中，你可以斷定它最壞的情況下其復雜度不會超過O(log2N)。而hash表就不一樣，是O(1)，還是O(N)，或者在其之間，你并不能把握。假若你在開發一個供外部調用的接口，其內部有關鍵字的查找，但是這個接口調用并不頻繁，你是會希望其調用速度快、但不穩定呢，還是希望其調用時間平均、且穩定呢。反之假若你的程序需要查找一個關鍵字，這個操作非常頻繁，你希望這些操作在總體上的時間較短，那么hash表查詢在總時間上會比其他要短，平均操作時間也會短。這里就需要權衡了。

　　這里總結一下，選用map還是hash_map，關鍵是看關鍵字查詢操作次數，以及你所需要保證的是查詢總體時間還是單個查詢的時間。如果是要很多次操作，要求其整體效率，那么使用hash_map，平均處理時間短。如果是少數次的操作，使用hash_map可能造成不確定的O(N)，那么使用平均處理時間相對較慢、單次處理時間恒定的map，考慮整體穩定性應該要高于整體效率，因為前提在操作次數較少。如果在一次流程中，使用hash_map的少數操作產生一個最壞情況O(N)，那么hash_map的優勢也因此喪盡了。