【专业技术】hash_map使用（二）
这种情况比价复杂，我们先说简单的，对于C++标准库的string类。 庆幸的是，微软为basic_string（string类的基类）提供了hash方法，这使得使用string对象做索引简单了许多。值得注意（也值得郁闷）的是，虽然支持string的hash，string类却没有重载比较运算符，所以标准的hash_compare仿函数依旧无法工作。我们继续重写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);
}
};
好了，我们可以书写如下代码：
hash_map<string, int, hash_compare<string, string_less> > StringHash;
StringHash["a"] = 123;
StringHash["b"] = 456;
string strKey = "a";
int val = CharHash[strKey];
这样就可以了。 对于另外的一个常用的字符串类CString（我认为微软的CString比标准库的string设计要洒脱一些）更加复杂一些。很显然，标准库里不包含对于CString的支持，但CString却重载了比较运算符（郁闷）。我们必须重写hash_compare仿函数。值得一提的是，在Virtual Stdio 2003中，CString不再是MFC的成员，而成为ATL的成员，使用#include <atlstr.h>就可以使用。我没有采用重写hash_compare仿函数的策略，而仅仅是继承了它，在模版库中的继承是没有性能损耗的，而且能让我偷一点懒。
首先重写一个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);
}
其次重写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));
}
};
上面的重载忽略了基类对于less仿函数的引入，因为CString具备比较运算符，我们可以使用默认的less仿函数，在这里映射为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;
};
让我们自写的类都派生自这里，有一个标准，接下来定义我们的类：
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域计算hash值，也可以使用更复杂的函数计算所有域总的hash值
return(m_value ^ 0xdeadbeef
}
virtual bool operator < (const IHashable& val) const {
return(m_value < ((CTest&)val).m_value);
}
};
用这个类的对象做为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));
}
};
下来就这样写：
CTest test;
test.m_value = 123;
test.m_message = "This is a test";
MyHash[test] = 2005;
int val = MyHash[test];
可以看到正确的数字被返回。 关于hash_map的思考： 1、性能分析：采用了内联代码和模版技术的hash_map在效率上应该是非常优秀的，但我们还需要注意如下几点： * 经过查看代码，字符串索引会比简单类型索引速度慢，自定义类型索引的性能则和我们选择hash的内容有很大关系，简单为主，这是使用hash_map的基本原则。 * 可以通过重写hash_compair仿函数，更改里面关于桶数量的定义，如果取值合适，也可以得到更优的性能。如果桶数量大于10，则牢记它应该是一个质数。 * 在自定义类型是，重载的等号（或者拷贝构造）有可能成为性能瓶颈，使用对象指针最为索引将是一个好的想法，但这就必须重写less仿函数，理由同使用字符串指针作为索引。
自己使用上面的方法成功解决了使用PTCHAR作为Key的使用，其解决方法如下：
inline size_t PTCHAR_hash_value(const PTCHAR str)
{
size_t value = _HASH_SEED;
size_t size = _tcslen(str);
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;
}
class PTCHAR_hash_compare : public stdext::hash_compare<PTCHAR>
{
public:
size_t operator()(const PTCHAR _Key) const {
return ((size_t)PTCHAR_hash_value(_Key));
}
bool operator()(const PTCHAR _Keyval1, const PTCHAR _Keyval2) const {
return (_tcscmp(_Keyval1, _Keyval2));
}
};
stdext::hash_map<PTCHAR, long, PTCHAR_hash_compare > myHash;
转自：http://blog.csdn.net/sdhongjun/article/details/4517325