說來慚愧，使用了很久Visual Stdio 2003了，只知道MFC升級(jí)到了7.0，ATL也升級(jí)到了7.0，對于這兩個(gè)經(jīng)典的類庫做了一些研究，但一直沒有注意C++標(biāo)準(zhǔn)庫的變化。

     今天嘗試的使用了stdext::hash_map這個(gè)庫，果然不錯(cuò)。下面寫下一些心得。

     hash_map類在頭文件hash_map中，和所有其它的C++標(biāo)準(zhǔn)庫一樣，頭文件沒有擴(kuò)展名。如下聲明：

          #include <hash_map>
          using namespace std;
          using namespace stdext;

     hash_map是一個(gè)聚合類，它繼承自_Hash類，包括一個(gè)vector，一個(gè)list和一個(gè)pair，其中vector用于保存桶，list用于進(jìn)行沖突處理，pair用于保存key->value結(jié)構(gòu)，簡要地偽碼如下：

          class hash_map<class _Tkey, class _Tval>
          {
          private:
               typedef pair<_Tkey, _Tval> hash_pair;
               typedef list<hash_pair>    hash_list;
               typedef vector<hash_list>  hash_table;
          };

     當(dāng)然，這只是一個(gè)簡單模型，C++標(biāo)準(zhǔn)庫的泛型模版一向以嵌套復(fù)雜而聞名，初學(xué)時(shí)看類庫，無疑天書啊。微軟的hash_map類還聚合了hash_compare仿函數(shù)類，hash_compare類里有聚合了less仿函數(shù)類，亂七八糟的。

     下面說說使用方法：

     一、簡單變量作為索引：整形、實(shí)性、指針型
     其實(shí)指針型也就是整形，算法一樣。但是hash_map會(huì)對char*, const char*, wchar_t*, const wchar_t*做特殊處理。
     這種情況最簡單，下面代碼是整形示例：
            hash_map<int, int> IntHash;
            IntHash[1] = 123;
            IntHash[2] = 456;

            int val = IntHash[1];
            int val = IntHash[2];
     實(shí)型和指針型用法和整形一樣，原理如下：
     1、使用簡單類型作索引聲明hash_map的時(shí)候，不需要聲明模版的后兩個(gè)參數(shù)（最后一個(gè)參數(shù)指名hash_map節(jié)點(diǎn)的存儲(chǔ)方式，默認(rèn)為pair，我覺得這就挺好，沒必要修改），使用默認(rèn)值就好。
     2、對于除過字符串的其它簡單類型，hash_map使用模版函數(shù) size_t hash_value(const _Kty& _Keyval) 計(jì)算hash值，計(jì)算方法是經(jīng)典的掩碼異或法，自動(dòng)溢出得到索引hash值。微軟的工程師也許開了一個(gè)玩笑，這個(gè)掩碼被定義為0xdeadbeef(死牛肉，抑或是某個(gè)程序員的外號(hào)）。
     3、對于字符串指針作索引的時(shí)候，使用定類型函數(shù)inline size_t hash_value(const char *_Str)或inline size_t hash_value(const wchar_t *_Str)計(jì)算hash值，計(jì)算方法是取出每一個(gè)字符求和，自動(dòng)溢出得到hash值。對于字符串型的hash索引，要注意需要自定義less仿函數(shù)。
     因?yàn)槲覀冇欣碛烧J(rèn)為，人們使用hash表進(jìn)行快速查找的預(yù)期成本要比在hash表中插入的預(yù)期成本低得多，所以插入可以比查找昂貴些；基于這個(gè)假設(shè)，hash_map在有沖突時(shí)，插入鏈表是進(jìn)行排序插入的，這樣在進(jìn)行查詢沖突解決的時(shí)候就能夠更快捷的找到需要的索引。
     但是，基于泛型編程的原則，hash_map也有理由認(rèn)為每一種類型都支持使用"<"來判別兩個(gè)類型值的大小，這種設(shè)計(jì)恰好讓字符串類型無所適從，眾所周知，兩個(gè)字符串指針的大小并不代表字符串值的大小。見如下代碼：
          hash_map<const char*, int> CharHash;
          CharHash["a"] = 123;
          CharHash["b"] = 456;

          char szInput[64] = "";
          scanf("%s", szInput);

          int val = CharHash[szInput];

     最終的結(jié)果就是無論輸入任何字符串，都無法找到對應(yīng)的整數(shù)值。因?yàn)檩斎氲淖址羔樖莝zInput指針，和"a"或"b"字符串常量指針的大小是絕對不會(huì)相同。解決方法如下：
     首先寫一個(gè)仿函數(shù)CharLess，繼承自仿函數(shù)基類binary_function（當(dāng)然也可以不繼承，這樣寫只是符合標(biāo)準(zhǔn)，而且寫起來比較方便，不用被類似于指針的指針和指針的引用搞暈。

          struct CharLess : public binary_function<const char*, const char*, bool>
          {
          public:
               result_type operator()(const first_argument_type& _Left, const second_argument_type& _Right) const
               {
                    return(stricmp(_Left, _Right) < 0 ? true : false);
               }
          };

     很好，有了這個(gè)仿函數(shù)，就可以正確的使用字符串指針型hash_map了。如下：

          hash_map<const char*, int, hash_compare<const char*, CharLess> > CharHash;
          CharHash["a"] = 123;
          CharHash["b"] = 456;

          char szInput[64] = "";
          scanf("%s", szInput);

          int val = CharHash[szInput];
     
     現(xiàn)在就可以正常工作了。至此，簡單類型的使用方法介紹完畢。

     二、用戶自定義類型：比如對象類型，結(jié)構(gòu)體。
     這種情況比價(jià)復(fù)雜，我們先說簡單的，對于C++標(biāo)準(zhǔn)庫的string類。
     
     慶幸的是，微軟為basic_string（string類的基類）提供了hash方法，這使得使用string對象做索引簡單了許多。值得注意（也值得郁悶）的是，雖然支持string的hash，string類卻沒有重載比較運(yùn)算符，所以標(biāo)準(zhǔn)的hash_compare仿函數(shù)依舊無法工作。我們繼續(xù)重寫less仿函數(shù)。
         
          struct string_less : public binary_function<const string, const string, bool>
          {
          public:
               result_type operator()(const first_argument_type& _Left, const second_argument_type& _Right) const
               {
                    return(_Left.compare(_Right) < 0 ? true : fase);
               }
          };
           
     好了，我們可以書寫如下代碼：
           
          hash_map<string, int, hash_compare<string, string_less> > StringHash;
          StringHash["a"] = 123;
          StringHash["b"] = 456;

          string strKey = "a";

          int val = CharHash[strKey];
     
     這樣就可以了。
     
     對于另外的一個(gè)常用的字符串類CString（我認(rèn)為微軟的CString比標(biāo)準(zhǔn)庫的string設(shè)計(jì)要灑脫一些）更加復(fù)雜一些。很顯然，標(biāo)準(zhǔn)庫里不包含對于CString的支持，但CString卻重載了比較運(yùn)算符（郁悶）。我們必須重寫hash_compare仿函數(shù)。值得一提的是，在Virtual Stdio 2003中，CString不再是MFC的成員，而成為ATL的成員，使用#include <atlstr.h>就可以使用。我沒有采用重寫hash_compare仿函數(shù)的策略，而僅僅是繼承了它，在模版庫中的繼承是沒有性能損耗的，而且能讓我偷一點(diǎn)懶。
     首先重寫一個(gè)hash_value函數(shù)：
     
          inline size_t CString_hash_value(const CString& str)
          {
               size_t value = _HASH_SEED;
               size_t size  = str.GetLength();
               if (size > 0) {
                    size_t temp = (size / 16) + 1;
                    size -= temp;
                    for (size_t idx = 0; idx <= size; idx += temp) {
                         value += (size_t)str[(int)idx];
                    }
               }
               return(value);
          }
     
     其次重寫hash_compare仿函數(shù)：
     
          class CString_hash_compare : public hash_compare<CString>
          {
          public:
               size_t operator()(const CString& _Key) const
               {
                    return((size_t)CString_hash_value(_Key));
               }
  
               bool operator()(const CString& _Keyval1, const CString& _Keyval2) const
               {
                    return (comp(_Keyval1, _Keyval2));
               }
          };
           
     上面的重載忽略了基類對于less仿函數(shù)的引入，因?yàn)镃String具備比較運(yùn)算符，我們可以使用默認(rèn)的less仿函數(shù)，在這里映射為comp。好了，我們可以聲明新的hash_map對象如下：

          hash_map<CString, int, CString_hash_compare> CStringHash;

     其余的操作一樣一樣的。

     下來就說說對于自定義對象的使用方法：首先定義
     
          struct IHashable
          {
               virtual unsigned long hash_value() const = 0;
               virtual bool operator < (const IHashable& val) const = 0;
               virtual IHashable& operator = (const IHashable& val) = 0;
          };
     
     讓我們自寫的類都派生自這里，有一個(gè)標(biāo)準(zhǔn)，接下來定義我們的類：
     
          class CTest : public IHashable
          {
          public:
               int m_value;
               CString m_message;
          public:
               CTest() : m_value(0)
               {
               }
           
               CTest(const CTest& obj)
               {
                    m_value = obj.m_value;
                    m_message = obj.m_message;
               }
          public:
               virtual IHashable& operator = (const IHashable& val)
               {
                    m_value   = ((CTest&)val).m_value;
                    m_message = ((CTest&)val).m_message;
                    return(*this);
               }
           
               virtual unsigned long hash_value() const
               {
                    // 這里使用類中的m_value域計(jì)算hash值，也可以使用更復(fù)雜的函數(shù)計(jì)算所有域總的hash值
                    return(m_value ^ 0xdeadbeef 
               }
           
               virtual bool operator < (const IHashable& val) const
               {
                    return(m_value < ((CTest&)val).m_value);
               }
          };
     
     用這個(gè)類的對象做為hash索引準(zhǔn)備工作如下，因?yàn)榻涌谥幸?guī)定了比較運(yùn)算符，所以這里可以使用標(biāo)準(zhǔn)的less仿函數(shù)，所以這里忽略：
     
          template<class _Tkey>
          class MyHashCompare : public hash_compare<_Tkey>
          {
          public:
               size_t operator()(const _Tkey& _Key) const
               {
                    return(_Key.hash_value());
               }
           
               bool operator()(const _Tkey& _Keyval1, const _Tkey& _Keyval2) const
               {
                    return (comp(_Keyval1, _Keyval2));
               }
          };
           
     下來就這樣寫：
     
          CTest test;
          test.m_value = 123;
          test.m_message = "This is a test";
     
          MyHash[test] = 2005;
           
          int val = MyHash[test];
     
     可以看到正確的數(shù)字被返回。
     
     三、關(guān)于hash_map的思考：
     
     1、性能分析：采用了內(nèi)聯(lián)代碼和模版技術(shù)的hash_map在效率上應(yīng)該是非常優(yōu)秀的，但我們還需要注意如下幾點(diǎn)：
     
     * 經(jīng)過查看代碼，字符串索引會(huì)比簡單類型索引速度慢，自定義類型索引的性能則和我們選擇hash的內(nèi)容有很大關(guān)系，簡單為主，這是使用hash_map的基本原則。
     * 可以通過重寫hash_compair仿函數(shù)，更改里面關(guān)于桶數(shù)量的定義，如果取值合適，也可以得到更優(yōu)的性能。如果桶數(shù)量大于10，則牢記它應(yīng)該是一個(gè)質(zhì)數(shù)。
     * 在自定義類型是，重載的等號(hào)（或者拷貝構(gòu)造）有可能成為性能瓶頸，使用對象指針最為索引將是一個(gè)好的想法，但這就必須重寫less仿函數(shù)，理由同使用字符串指針作為索引。