Heath's Blog

There is no end, it is just the beginning! - A Game Developer's Notes

实现一个以字符串为Key大小写不敏感的Hash Map

    Hash Map有两个关键方法：哈希值计算方法和比较方法。以STLPort为例，通过Hash Map的模版定义可以看出，其缺省的哈希Functor是hash，比较functor为equal_to：

  1. template <class _Key, class _Tp, _STLP_DFL_TMPL_PARAM(_HashFcn,hash<_Key>),
  2.           _STLP_DFL_TMPL_PARAM(_EqualKey,equal_to<_Key>),
  3.           _STLP_DEFAULT_PAIR_ALLOCATOR_SELECT(_STLP_CONST _Key, _Tp) >
  4. class hash_map

    在_hash_fun.h中有针对各种类型的哈希值计算特化版本，下面仅摘录针对C字符串的代码：

  1. inline size_t __stl_hash_string(const char* __s) {
  2.   _STLP_FIX_LITERAL_BUG(__s)
  3.   unsigned long __h = 0;
  4.   for ( ; *__s; ++__s)
  5.     __h = 5*__h + *__s;
  6.  
  7.   return size_t(__h);
  8. }
  9.  
  10. _STLP_MOVE_TO_STD_NAMESPACE
  11.  
  12. _STLP_TEMPLATE_NULL
  13. struct hash<char*> {
  14.   size_t operator()(const char* __s) const {
  15.     _STLP_FIX_LITERAL_BUG(__s)
  16.     return _STLP_PRIV __stl_hash_string(__s);
  17.   }
  18. };
  19.  
  20. _STLP_TEMPLATE_NULL
  21. struct hash<const char*> {
  22.   size_t operator()(const char* __s) const {
  23.     _STLP_FIX_LITERAL_BUG(__s)
  24.     return _STLP_PRIV __stl_hash_string(__s);
  25.   }
  26. };

    __stl_hash_string实现了一个简单的哈希算法，因为算法中使用了字符的ASCII码，为了达到大小写不敏感的目的，可将每个字符转换成小写/大写来计算。对于hash functor，我们也需要一个string的特化版。

    在_function_base.h中定义了equal_to functor：

  1. template <class _Arg1, class _Arg2, class _Result>
  2. struct binary_function {
  3.   typedef _Arg1 first_argument_type;
  4.   typedef _Arg2 second_argument_type;
  5.   typedef _Result result_type;
  6. #if !defined (__BORLANDC__) || (__BORLANDC__ < 0x580)
  7. protected:
  8.   /* See unary_function comment. */
  9.   ~binary_function() {}
  10. #endif
  11. };
  12.  
  13. template <class _Tp>
  14. struct equal_to : public binary_function<_Tp, _Tp, bool> {
  15.   bool operator()(const _Tp& __x, const _Tp& __y) const { return __x == __y; }
  16. };

    通过定制一个string版本的equal_to，使用stricmp进行字符串比较。下面列出实现及测试代码：

Test Codes
  1. #include <hash_map>
  2. #include <string>
  3. #include <algorithm>
  4. #include <cctype>
  5.  
  6. inline size_t __stl_hash_string(const char* __s)
  7. {
  8.     unsigned long __h = 0;
  9.     for ( ; *__s; ++__s)
  10.         __h = 5*__h + tolower(*__s);
  11.  
  12.     return size_t(__h);
  13. }
  14.  
  15. template<>
  16. struct stlport::hash<stlport::string>
  17. {
  18.     size_t operator()(const stlport::string& __s) const
  19.     {
  20.         return __stl_hash_string(__s.c_str());
  21.     }
  22. };
  23.  
  24. template<>
  25. struct stlport::equal_to<stlport::string>
  26.     : public stlport::binary_function<stlport::string , stlport::string , bool>
  27. {
  28.     bool operator()(const stlport::string& __x, const stlport::string& __y) const
  29.     {
  30.         return !_stricmp(__x.c_str() , __y.c_str());
  31.     }
  32. };
  33.  
  34. int _tmain(int argc, _TCHAR* argv[])
  35. {
  36.     stlport::hash_map<stlport::string , int> map;
  37.  
  38.     map.insert(stlport::make_pair("Test" , 123));
  39.  
  40.     stlport::hash_map<stlport::string , int>::iterator iter = map.find("teSt");
  41.     if(iter != map.end())
  42.         printf("Found!\n");
  43.  
  44.     return 0;
  45. }

posted on 2011-07-13 23:36 Heath 阅读(3777) 评论(0)  编辑 收藏 引用 所属分类: Studying


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理