1. map :
C++的STL中map是使用樹來做查找算法; 時間復雜度:O(log2N)
2. hash_map :
使用hash表來排列配對,hash表是使用關鍵字來計算表位置; 時間復雜度:O(1), 最壞的時間復雜度:O(n)
總體來說:hash_map 比 map 查找速度快,而且查找速度基本和數據量大小無關,屬於常數級別,節省一定內存,如果沒有必要排序的話,盡量使用 hash_map 。
注:hash還有hash函數的耗時。當有100w條記錄的時候,map也只需要20次的比較,200w也只需要21次的比較!所以並不一定常數就比log(n) ;用map,還是hash_map,從3個方面來權衡: 查找速度,數據量, 內存使用,還有一個就是你的經驗!沒有特別的標准