Hash Map有兩個關鍵方法：哈希值計算方法和比較方法。以STLPort為例，通過Hash Map的模版定義可以看出，其缺省的哈希Functor是hash，比較functor為equal_to：
- template <class _Key, class _Tp, _STLP_DFL_TMPL_PARAM(_HashFcn,hash<_Key>),
- ??????????_STLP_DFL_TMPL_PARAM(_EqualKey,equal_to<_Key>),
- ??????????_STLP_DEFAULT_PAIR_ALLOCATOR_SELECT(_STLP_CONST _Key, _Tp) >
- class hash_map
在_hash_fun.h中有針對各種類型的哈希值計算特化版本，下面僅摘錄針對C字符串的代碼：
- inline size_t __stl_hash_string(const char* __s) {
- ??_STLP_FIX_LITERAL_BUG(__s)
- ??unsigned long __h = 0;
- ??for ( ; *__s; ++__s)
- ????__h = 5*__h + *__s;
-
- ??return size_t(__h);
- }
-
- _STLP_MOVE_TO_STD_NAMESPACE
-
- _STLP_TEMPLATE_NULL
- struct hash<char*> {
- ??size_t operator()(const char* __s) const {
- ????_STLP_FIX_LITERAL_BUG(__s)
- ????return _STLP_PRIV __stl_hash_string(__s);
- ??}
- };
-
- _STLP_TEMPLATE_NULL
- struct hash<const char*> {
- ??size_t operator()(const char* __s) const {
- ????_STLP_FIX_LITERAL_BUG(__s)
- ????return _STLP_PRIV __stl_hash_string(__s);
- ??}
- };
__stl_hash_string實現了一個簡單的哈希算法，因為算法中使用了字符的ASCII碼，為了達到大小寫不敏感的目的，可將每個字符轉換成小寫/大寫來計算。對于hash functor，我們也需要一個string的特化版。
在_function_base.h中定義了equal_to functor：
- template <class _Arg1, class _Arg2, class _Result>
- struct binary_function {
- ??typedef _Arg1 first_argument_type;
- ??typedef _Arg2 second_argument_type;
- ??typedef _Result result_type;
- #if !defined (__BORLANDC__) || (__BORLANDC__ < 0x580)
- protected:
- ??/* See unary_function comment. */
- ??~binary_function() {}
- #endif
- };
-
- template <class _Tp>
- struct equal_to : public binary_function<_Tp, _Tp, bool> {
- ??bool operator()(const _Tp& __x, const _Tp& __y) const { return __x == __y; }
- };
通過定制一個string版本的equal_to，使用stricmp進行字符串比較。下面列出實現及測試代碼：
Test Codes
- #include <hash_map>
- #include <string>
- #include <algorithm>
- #include <cctype>
-
- inline size_t __stl_hash_string(const char* __s)
- {
- ????unsigned long __h = 0;
- ????for ( ; *__s; ++__s)
- ????????__h = 5*__h + tolower(*__s);
-
- ????return size_t(__h);
- }
-
- template<>
- struct stlport::hash<stlport::string>
- {
- ????size_t operator()(const stlport::string& __s) const
- ????{
- ????????return __stl_hash_string(__s.c_str());
- ????}
- };
-
- template<>
- struct stlport::equal_to<stlport::string>
- ????: public stlport::binary_function<stlport::string , stlport::string , bool>
- {
- ????bool operator()(const stlport::string& __x, const stlport::string& __y) const
- ????{
- ????????return !_stricmp(__x.c_str() , __y.c_str());
- ????}
- };
-
- int _tmain(int argc, _TCHAR* argv[])
- {
- ????stlport::hash_map<stlport::string , int> map;
-
- ????map.insert(stlport::make_pair("Test" , 123));
-
- ????stlport::hash_map<stlport::string , int>::iterator iter = map.find("teSt");
- ????if(iter != map.end())
- ????????printf("Found!\n");
-
- ????return 0;
- }