C/C++ Hash表 (三)

struct hash {
size_t operator()(int __x) const { return __x; }
};
原来是个函数对象。在SGI STL中，提供了以下hash函数：
struct hash
struct hash
struct hash
struct hash
struct hash
struct hash
struct hash
struct hash
struct hash
struct hash
struct hash
也就是说，如果你的key使用的是以上类型中的一种，你都可以使用缺省的hash函数。当然你自己也可以定义自己的hash函数。对于自定义变量，你只能如此，例如对于string，就必须自定义hash函数。例如：
[cpp]
struct hash_string{
size_t operator()(const string& str) const
{
unsigned long __h = 0;
for (size_t i = 0 ; i < str.size() ; i ++)
__h = 5*__h + str[i];
return size_t(__h);
}
};

struct hash_string{
size_t operator()(const string& str) const
{
unsigned long __h = 0;
for (size_t i = 0 ; i < str.size() ; i ++)
__h = 5*__h + str[i];
return size_t(__h);
}
};//如果你希望利用系统定义的字符串hash函数，你可以这样写：
[cpp]
struct hash_string{
size_t operator()(const string& str) const
{
return __stl_hash_string(str.c_str());
}
};

struct hash_string{
size_t operator()(const string& str) const
{
return __stl_hash_string(str.c_str());
}
};在Visual Studio下，hash function 和 equal function 在一个结构中，不想SGI的是分开的。
[cpp]
struct hash_string
{
static const size_t bucket_size = 4;
static const size_t min_buckets = 8;
// 1. define the hash function
size_t operator()(const string& str) const
{
unsigned long __h = 0;
for (size_t i = 0 ; i < str.size() ; i ++)
__h = 5*__h + str[i];
return size_t(__h);
}
//// 1. define the hash function
//size_t operator()(const string& str) const
//{
// return __stl_hash_string(str.c_str());
//}
// 2. define the equal function
bool operator()(const string& p1, const string& p2) const{
return p1 == p2;
}
};

struct hash_string
{
static const size_t bucket_size = 4;
static const size_t min_buckets = 8;
// 1. define the hash function
size_t operator()(const string& str) const
{
unsigned long __h = 0;
for (size_t i = 0 ; i < str.size() ; i ++)
__h = 5*__h + str[i];
return size_t(__h);
}
//// 1. define the hash function
//size_t operator()(const string& str) const
//{
// return __stl_hash_string(str.c_str());
//}
// 2. define the equal function
bool operator()(const string& p1, const string& p2) const{
return p1 == p2;
}
};在声明自己的哈希函数时要注意以下几点：
使用struct，然后重载operator();
返回是size_t;
参数是你要hash的key的类型;
函数是const类型的。
如果这些比较难记，最简单的方法就是照猫画虎，找一个函数改改就是了。

现在可以对开头的"岳不群"进行哈希化了 . 直接替换成下面的声明即可：

map namemap;
//改为：
hash_map namemap;
其他用法都不用边。当然不要忘了吧hash_string的声明以及头文件改为hash_map。
你或许会问：比较函数呢？别着急，这里就开始介绍hash_map中的比较函数。

2.3 hash_map 的 比较函数
在map中的比较函数，需要提供less函数。如果没有提供，缺省的也是less< Key> 。在hash_map中，要比较桶内的数据和key是否相等，因此需要的是是否等于的函数:equal_to< Key> 。先看看equal_to的源码：

//本代码可以从SGI STL
//先看看binary_function 函数声明，其实只是定义一些类型而已。

[cpp]
template
struct binary_function {
typedef _Arg1 first_argument_type;
typedef _Arg2 second_argument_type;
typedef _Result result_type;
};
//看看equal_to的定义：
template
struct equal_to : public binary_function<_Tp,_Tp,bool>
{
bool operator()(const _Tp& __x, const _Tp& __y) const { return __x == __y; }
};

template
struct binary_function {
typedef _Arg1 first_argument_type;
typedef _Arg2 second_argument_type;
typedef _Result result_type;
};
//看看equal_to的定义：
template
struct equal_to : public binary_function<_Tp,_Tp,bool>
{
bool operator()(const _Tp& __x, const _Tp& __y) const { return __x == __y; }
};如果你使用一个自定义的数据类型，如struct mystruct, 或者const char* 的字符串，如何使用比较函数？
使用比较函数，有两种方法.

第一种是：重载==操作符，利用equal_to;看看下面的例子：

struct mys