【专业技术】STL hash_map使用（一）
hash_map类在头文件hash_map中，和所有其它的C++标准库一样，头文件没有扩展名。如下声明：
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;
};
hash_map是一个聚合类，它继承自_Hash类，包括一个vector，一个list和一个pair，其中vector用于保存桶，list用于进行冲突处理，pair用于保存key->value结构，简要地伪码如下：
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;
};
当然，这只是一个简单模型，C++标准库的泛型模版一向以嵌套复杂而闻名，初学时看类库，无疑天书啊。微软的hash_map类还聚合了hash_compare仿函数类，hash_compare类里又聚合了less仿函数类，乱七八糟的。
下面说说使用方法：
一、简单变量作为索引：整形、实性、指针型 其实指针型也就是整形，算法一样。但是hash_map会对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];
实型和指针型用法和整形一样，原理如下： 1、使用简单类型作索引声明hash_map的时候，不需要声明模版的后两个参数（最后一个参数指名hash_map节点的存储方式，默认为pair，我觉得这就挺好，没必要修改），使用默认值就好。 2、对于除过字符串的其它简单类型，hash_map使用模版函数 size_t hash_value(const _Kty& _Keyval) 计算hash值，计算方法是经典的掩码异或法，自动溢出得到索引hash值。微软的工程师也许开了一个玩笑，这个掩码被定义为0xdeadbeef(死牛肉，抑或是某个程序员的外号）。 3、对于字符串指针作索引的时候，使用定类型函数inline size_t hash_value(const char *_Str)或inline size_t hash_value(const wchar_t *_Str)计算hash值，计算方法是取出每一个字符求和，自动溢出得到hash值。对于字符串型的hash索引，要注意需要自定义less仿函数。 因为我们有理由认为，人们使用hash表进行快速查找的预期成本要比在hash表中插入的预期成本低得多，所以插入可以比查找昂贵些；基于这个假设，hash_map在有冲突时，插入链表是进行排序插入的，这样在进行查询冲突解决的时候就能够更快捷的找到需要的索引。 但是，基于泛型编程的原则，hash_map也有理由认为每一种类型都支持使用"<"来判别两个类型值的大小，这种设计恰好让字符串类型无所适从，众所周知，两个字符串指针的大小并不代表字符串值的大小。见如下代码：
hash_map<const char*, int> CharHash;
CharHash["a"] = 123;
CharHash["b"] = 456;
char szInput[64] = "";
scanf("%s", szInput);
int val = CharHash[szInput];
最终的结果就是无论输入任何字符串，都无法找到对应的整数值。因为输入的字符串指针是szInput指针，和"a"或"b"字符串常量指针的大小是绝对不会相同。解决方法如下： 首先写一个仿函数CharLess，继承自仿函数基类binary_function（当然也可以不继承，这样写只是符合标准，而且写起来比较方便，不用被类似于指针的指针和指针的引用搞晕。
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);
}
};
很好，有了这个仿函数，就可以正确的使用字符串指针型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];
现在就可以正常工作了。至此，简单类型的使用方法介绍完毕。
未完待续
转自：http://blog.csdn.net/sdhongjun/article/details/4517325