今天嘗試的使用了stdext::hash_map這個(gè)庫，果然不錯。下面寫(xiě)下一些心得。
hash_map類(lèi)在頭文件hash_map中，和所有其它的C++標準庫一樣，頭文件沒(méi)有擴展名。如下聲明：
#include <hash_map>
using namespace std;
using namespace stdext;
hash_map是一個(gè)聚合類(lèi)，它繼承自_Hash類(lèi)，包括一個(gè)vector，一個(gè)list和一個(gè)pair，其中vector用于保存桶，list用于進(jìn)行沖突處理，pair用于保存key->value結構，簡(jiǎn)要地偽碼如下：
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;
};
當然，這只是一個(gè)簡(jiǎn)單模型，C++標準庫的泛型模版一向以嵌套復雜而聞名，初學(xué)時(shí)看類(lèi)庫，無(wú)疑天書(shū)啊。微軟的hash_map類(lèi)還聚合了hash_compare仿函數類(lèi)，hash_compare類(lèi)里有聚合了less仿函數類(lèi)，亂七八糟的。
下面說(shuō)說(shuō)使用方法：
一、簡(jiǎn)單變量作為索引：整形、實(shí)性、指針型
其實(shí)指針型也就是整形，算法一樣。但是hash_map會(huì )對char*, const char*, wchar_t*, const wchar_t*做特殊處理。
這種情況最簡(jiǎn)單，下面代碼是整形示例：
hash_map<int, int> IntHash;
IntHash[1] = 123;
IntHash[2] = 456;
int val = IntHash[1];
int val = IntHash[2];
實(shí)型和指針型用法和整形一樣，原理如下：
1、使用簡(jiǎn)單類(lèi)型作索引聲明hash_map的時(shí)候，不需要聲明模版的后兩個(gè)參數（最后一個(gè)參數指名hash_map節點(diǎn)的存儲方式，默認為pair，我覺(jué)得這就挺好，沒(méi)必要修改），使用默認值就好。
2、對于除過(guò)字符串的其它簡(jiǎn)單類(lèi)型，hash_map使用模版函數 size_t hash_value(const _Kty&_Keyval)計算hash值，計算方法是經(jīng)典的掩碼異或法，自動(dòng)溢出得到索引hash值。微軟的工程師也許開(kāi)了一個(gè)玩笑，這個(gè)掩碼被定義為0xdeadbeef(死牛肉，抑或是某個(gè)程序員的外號）。
3、對于字符串指針作索引的時(shí)候，使用定類(lèi)型函數inline size_thash_value(const char *_Str)或inline size_t hash_value(const wchar_t*_Str)計算hash值，計算方法是取出每一個(gè)字符求和，自動(dòng)溢出得到hash值。對于字符串型的hash索引，要注意需要自定義less仿函數。
因為我們有理由認為，人們使用hash表進(jìn)行快速查找的預期成本要比在hash表中插入的預期成本低得多，所以插入可以比查找昂貴些；基于這個(gè)假設，hash_map在有沖突時(shí)，插入鏈表是進(jìn)行排序插入的，這樣在進(jìn)行查詢(xún)沖突解決的時(shí)候就能夠更快捷的找到需要的索引。
但是，基于泛型編程的原則，hash_map也有理由認為每一種類(lèi)型都支持使用"<"來(lái)判別兩個(gè)類(lèi)型值的大小，這種設計恰好讓字符串類(lèi)型無(wú)所適從，眾所周知，兩個(gè)字符串指針的大小并不代表字符串值的大小。見(jiàn)如下代碼：
hash_map<const char*, int> CharHash;
CharHash["a"] = 123;
CharHash["b"] = 456;
char szInput[64] = "";
scanf("%s", szInput);
int val = CharHash[szInput];
最終的結果就是無(wú)論輸入任何字符串，都無(wú)法找到對應的整數值。因為輸入的字符串指針是szInput指針，和"a"或"b"字符串常量指針的大小是絕對不會(huì )相同。解決方法如下：
首先寫(xiě)一個(gè)仿函數CharLess，繼承自仿函數基類(lèi)binary_function（當然也可以不繼承，這樣寫(xiě)只是符合標準，而且寫(xiě)起來(lái)比較方便，不用被類(lèi)似于指針的指針和指針的引用搞暈。
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è)仿函數，就可以正確的使用字符串指針型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];
現在就可以正常工作了。至此，簡(jiǎn)單類(lèi)型的使用方法介紹完畢。
二、用戶(hù)自定義類(lèi)型：比如對象類(lèi)型，結構體。
這種情況比價(jià)復雜，我們先說(shuō)簡(jiǎn)單的，對于C++標準庫的string類(lèi)。
慶幸的是，微軟為basic_string（string類(lèi)的基類(lèi)）提供了hash方法，這使得使用string對象做索引簡(jiǎn)單了許多。值得注意（也值得郁悶）的是，雖然支持string的hash，string類(lèi)卻沒(méi)有重載比較運算符，所以標準的hash_compare仿函數依舊無(wú)法工作。我們繼續重寫(xiě)less仿函數。
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);
}
};
好了，我們可以書(shū)寫(xiě)如下代碼：
hash_map<string, int, hash_compare<string, string_less> > StringHash;
StringHash["a"] = 123;
StringHash["b"] = 456;
string strKey = "a";
int val = CharHash[strKey];
這樣就可以了。
對于另外的一個(gè)常用的字符串類(lèi)CString（我認為微軟的CString比標準庫的string設計要灑脫一些）更加復雜一些。很顯然，標準庫里不包含對于CString的支持，但CString卻重載了比較運算符（郁悶）。我們必須重寫(xiě)hash_compare仿函數。值得一提的是，在VirtualStdio 2003中，CString不再是MFC的成員，而成為ATL的成員，使用#include<atlstr.h>就可以使用。我沒(méi)有采用重寫(xiě)hash_compare仿函數的策略，而僅僅是繼承了它，在模版庫中的繼承是沒(méi)有性能損耗的，而且能讓我偷一點(diǎn)懶。
首先重寫(xiě)一個(gè)hash_value函數：
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);
}
其次重寫(xiě)hash_compare仿函數：
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));
}
};
上面的重載忽略了基類(lèi)對于less仿函數的引入，因為CString具備比較運算符，我們可以使用默認的less仿函數，在這里映射為comp。好了，我們可以聲明新的hash_map對象如下：
hash_map<CString, int, CString_hash_compare> CStringHash;
其余的操作一樣一樣的。
下來(lái)就說(shuō)說(shuō)對于自定義對象的使用方法：首先定義
struct IHashable
{
virtual unsigned long hash_value() const = 0;
virtual bool operator < (const IHashable& val) const = 0;
virtual IHashable& operator = (const IHashable& val) = 0;
};
讓我們自寫(xiě)的類(lèi)都派生自這里，有一個(gè)標準，接下來(lái)定義我們的類(lèi)：
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
{
// 這里使用類(lèi)中的m_value域計算hash值，也可以使用更復雜的函數計算所有域總的hash值
return(m_value ^ 0xdeadbeef
}
virtual bool operator < (const IHashable& val) const
{
return(m_value < ((CTest&)val).m_value);
}
};
用這個(gè)類(lèi)的對象做為hash索引準備工作如下，因為接口中規定了比較運算符，所以這里可以使用標準的less仿函數，所以這里忽略：
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));
}
};
下來(lái)就這樣寫(xiě)：
CTest test;
test.m_value = 123;
test.m_message = "This is a test";
MyHash[test] = 2005;
int val = MyHash[test];
可以看到正確的數字被返回。
三、關(guān)于hash_map的思考：
1、性能分析：采用了內聯(lián)代碼和模版技術(shù)的hash_map在效率上應該是非常優(yōu)秀的，但我們還需要注意如下幾點(diǎn)：
* 經(jīng)過(guò)查看代碼，字符串索引會(huì )比簡(jiǎn)單類(lèi)型索引速度慢，自定義類(lèi)型索引的性能則和我們選擇hash的內容有很大關(guān)系，簡(jiǎn)單為主，這是使用hash_map的基本原則。
* 可以通過(guò)重寫(xiě)hash_compair仿函數，更改里面關(guān)于桶數量的定義，如果取值合適，也可以得到更優(yōu)的性能。如果桶數量大于10，則牢記它應該是一個(gè)質(zhì)數。
* 在自定義類(lèi)型是，重載的等號（或者拷貝構造）有可能成為性能瓶頸，使用對象指針最為索引將是一個(gè)好的想法，但這就必須重寫(xiě)less仿函數，理由同使用字符串指針作為索引。
聯(lián)系客服
