关联容器 — hash_map
最后更新于：2022-04-01 19:54:26
hash_map和map的用法很相似，只是底层机制有所不同。
hash_map容器采用的底层机制是hash table代码：
~~~
template ,
class EqualKey = equal_to,
class Alloc = alloc>
class hash_map
{
private:
typedef hashtable, Key, HashFcn,
select1st >, EqualKey, Alloc> ht;
ht rep; // 底层机制——hash table
....
}
~~~
注意，hashtable类型的第一个类型参数是pair，继续跟踪hashtable代码：
~~~
template
class hashtable { // hash table数据结构
public:
typedef Key key_type;
typedef Value value_type;
....
typedef __hashtable_node node;
typedef simple_alloc node_allocator; // 空间配置器
vector buckets; // 桶的集合
....
}
~~~
可以看出，Value或value_type的实际类型是一个pair，那么一个node中也存储了一个pair，而vector中的bucket还是指针不变。即每个bucket指向一串nodes，每个node中存放一个pair。这和map容器是类似的，map容器底层的红黑树中，每个节点也是存储了一个pair。
下面是测试代码：
~~~
#include
#include
#include
using namespace std;
using namespace __gnu_cxx;
struct eqstr {
bool operator() (const char *s1, const char *s2) const
{ return strcmp(s1, s2) == 0; }
};
int main()
{
hash_map, eqstr> m;
// 两种插入方法
m["hello"] = 123;
m["byebye"] = 234;
m["test"] = 345;
m.insert(pair("a", 222));
hash_map, eqstr>::iterator iter = m.begin();
for ( ; iter != m.end(); ++iter)
cout << iter->first << ' ' << iter->second << endl;
return 0;
}
~~~
运行结果：
由于hash_map提供的默认键值比较标准为equal_to：
~~~
template
struct equal_to : public binary_function {
bool operator()(const T& x, const T& y) const { return x == y; }
};
~~~
这个仿函数只是简单的拿两个值进行比较，如果传入的key为const char *，那么比较的将会是两个地址，这不是我们想要的。正确的字符串比较应该是逐个字符进行比较，这就是为什么要定义eqstr的原因。
从运行结果也能够看出，和hash_set一样，hash_map内的元素无特定排序。
参考：
《STL源码剖析》 P275.
';