### 前言 ? 在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: ~~~