stl_hash_fun.h学习
最后更新于：2022-04-01 15:51:07
### 前言
在SGI STL中hash表的实现是采用拉链法，其中用到了哈希函数，哈希函数的作用是把元素键值映射到对应的桶子里面，一般哈希值是键值对桶子数取余。在SGI STL提供的哈希函数是有限的，只支持特定的元素类型，若用户需要使用其他类型的哈希函数，则必须自行定义。定义的时候注意一下几点：
1. 使用struct，然后重载operator().
1. 返回是size_t
1. 参数是你要hash的key的类型。
1. 函数是const类型的。
例如定义string类型的哈希函数：
~~~
struct str_hash{
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函数源码剖析
~~~
#ifndef __SGI_STL_HASH_FUN_H
#define __SGI_STL_HASH_FUN_H
#include <stddef.h>
__STL_BEGIN_NAMESPACE
//hash function 是计算元素位置的函数
//这些函数可以对hashtable进行取模运算
//这是hashtable所提供的散列函数是取模运算决定的
/*
SGI hashtable以下有限的定义类型：
struct hash<char*>
struct hash<const char*>
struct hash<char>
struct hash<unsigned char>
struct hash<signed char>
struct hash<short>
struct hash<unsigned short>
struct hash<int>
struct hash<unsigned int>
struct hash<long>
struct hash<unsigned long>
不在这里定义的类型，不能使用，若用户想要使用，则必须自己定义。例如：string，double，float
*/
/*定义自己的哈希函数时要注意以下几点：
[1]使用struct，然后重载operator().
[2]返回是size_t
[3]参数是你要hash的key的类型。
[4]函数是const类型的。
*/
template <class _Key> struct hash { };
//对const char* 提供字符串转换函数
inline size_t __stl_hash_string(const char* __s)
{
unsigned long __h = 0;
for ( ; *__s; ++__s)
__h = 5*__h + *__s;
return size_t(__h);
}
__STL_TEMPLATE_NULL struct hash<char*>
{
size_t operator()(const char* __s) const { return __stl_hash_string(__s); }
};
__STL_TEMPLATE_NULL struct hash<const char*>
{
size_t operator()(const char* __s) const { return __stl_hash_string(__s); }
};
//下面的hash函数都是直接返回原值
//对于char,unsigned char,signed char,int,unsigned int,
//short, unsigned short, long,unsigned long都只是返回数值本身
__STL_TEMPLATE_NULL struct hash<char> {
size_t operator()(char __x) const { return __x; }
};
__STL_TEMPLATE_NULL struct hash<unsigned char> {
size_t operator()(unsigned char __x) const { return __x; }
};
__STL_TEMPLATE_NULL struct hash<signed char> {
size_t operator()(unsigned char __x) const { return __x; }
};
__STL_TEMPLATE_NULL struct hash<short> {
size_t operator()(short __x) const { return __x; }
};
__STL_TEMPLATE_NULL struct hash<unsigned short> {
size_t operator()(unsigned short __x) const { return __x; }
};
__STL_TEMPLATE_NULL struct hash<int> {
size_t operator()(int __x) const { return __x; }
};
__STL_TEMPLATE_NULL struct hash<unsigned int> {
size_t operator()(unsigned int __x) const { return __x; }
};
__STL_TEMPLATE_NULL struct hash<long> {
size_t operator()(long __x) const { return __x; }
};
__STL_TEMPLATE_NULL struct hash<unsigned long> {
size_t operator()(unsigned long __x) const { return __x; }
};
__STL_END_NAMESPACE
#endif /* __SGI_STL_HASH_FUN_H */
// Local Variables:
// mode:C++
// End:
~~~