STL---hash_map【十全十美】

    正在趕一個關於證劵交易的項目，其中用到了很多數據的查找等操作，開始用了map，同事看到後建議我用hash_map，查了查hash_map的內部實現，這裡順帶也就寫了下來。

    hash_map基於hash table哈希表）。 哈希表最大的優點，就是把數據的存儲和查找消耗的時間大大降低，幾乎可以看成是常數時間；而代價僅僅是消耗比較多的內存。然而在當前可利用內存越來越多的情況下，用空間換時間的做法是值得的。另外，編碼比較容易也是它的特點之一。     其基本原理是：使用一個下標范圍比較大的數組來存儲元素。可以設計一個函數哈希函數，也叫做散列函數），使得每個元素的關鍵字都與一個函數值即數組下標，hash值）相對應，於是用這個數組單元來存儲這個元素；也可以簡單的理解為，按照關鍵字為每一個元素“分類”，然後將這個元素存儲在相應“類”所對應的地方，稱為桶。但是，不能夠保證每個元素的關鍵字與函數值是一一對應的，因此極有可能出現對於不同的元素，卻計算出了相同的函數值，這樣就產生了“沖突”，換句話說，就是把不同的元素分在了相同的“類”之中。 總的來說，“直接定址”與“解決沖突”是哈希表的兩大特點。hash_map，首先分配一大片內存，形成許多桶。是利用hash函數，對key進行映射到不同區域桶）進行保 存。其插入過程是：    得到key    通過hash函數得到hash值    得到桶號(一般都為hash值對桶數求模)    存放key和value在桶內。 其取值過程是:    得到key    通過hash函數得到hash值    得到桶號(一般都為hash值對桶數求模)    比較桶的內部元素是否與key相等，若都不相等，則沒有找到。    取出相等的記錄的value。      hash_map中直接地址用hash函數生成，解決沖突，用比較函數解決。這裡可以看出，如果每個桶內部只有一個元素，那麼查找的時候只有一次比較。當許多桶內沒有值時，許多查詢就會更快了(指查不到的時候).    由此可見，要實現哈希表, 和用戶相關的是：hash函數和比較函數。這兩個參數剛好是我們在使用hash_map時需要指定的參數。     使用hash_map的一個簡單的例子：  

#if defined(__GNUC__) 
#if __GNUC__ < 3 && __GNUC__ >= 2 && __GNUC_MINOR__ >= 95 
#include <hash_map> 
#elif __GNUC__ >= 3 
#include <ext/hash_map> 
using namespace __gnu_cxx; 
#else 
#include <hash_map.h> 
#endif 
#elif defined(__MSVC_VER__) 
#if __MSVC_VER__ >= 7 
#include <hash_map> 
#else 
#error "std::hash_map is not available with this compiler" 
#endif 
#elif defined(__sgi__) 
#include <hash_map> 
#else 
#error "std::hash_map is not available with this compiler" 
#endif 
#include <string> 
#include <iostream> 
#include <algorithm> 
using namespace std; 
struct str_hash{ 
        size_t operator()(const string& str) const 
        { 
                return __stl_hash_string(str.c_str()); 
        } 
}; 
struct str_equal{ 
    bool operator()(const string& s1,const string& s2) const    {      
   return s1==s2; 
    } 
}; 
 
int main(int argc, char *argv[]) 
{ 
        hash_map<string,string,str_hash,str_equal> mymap; 
        mymap.insert(pair<string,string>("hcq","20")); 
        mymap["sgx"]="24"; 
        mymap["sb"]="23"; 
        cout<<mymap["sb"]<<endl; 
        if(mymap.find("hcq")!=mymap.end()) 
        cout<<mymap["hcq"]<<endl; 
        return 0; 
} 

hash_map與map的區別：    1、構造函數。hash_map需要hash函數，等於函數；map只需要比較函數(小於函數).    2、存儲結構。hash_map采用hash表存儲，map一般采用紅黑樹(RB Tree)實現。因此其memory數據結構是不一樣的。      總體來說，hash_map 查找速度會比map快，而且查找速度基本和數據數據量大小，屬於常數級別;而map的查找速度是log(n)級別。並不一定常數就比log(n)小，hash還有hash函數的耗時，明白了吧，如果你考慮效率，特別是在元素達到一定數量級時，考慮考慮hash_map。但若你對內存使用特別嚴格，希望程序盡可能少消耗內存，那麼一定要小心，hash_map可能會讓你陷入尴尬，特別是當你的hash_map對象特別多時，你就更無法控制了，而且hash_map的構造速度較慢。現在知道如何選擇了嗎？權衡三個因素: 查找速度, 數據量, 內存使用。       哈哈，不說了，要不讓BOSS看到我不干活那就麻煩了……繼續工作！！！

 

本文出自 “驿落黃昏” 博客，轉載請與作者聯系！