程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> STL中map與hash_map的比較

STL中map與hash_map的比較

編輯:C++入門知識

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個方面來權衡: 查找速度,數據量, 內存使用,還有一個就是你的經驗!沒有特別的標准

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved