程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> C++ STL中的哈希表 hash_map

C++ STL中的哈希表 hash_map

編輯:關於C++

在定義hash_map容器的時候,不僅需要指定鍵和值的類型,還需要指定hash函數和相等函數

 

(一)hash_map 的hash函數

 

hash< int>到底是什麼樣子?看看源碼:


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函數。例如:

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函數,你可以這樣寫:
struct str_hash{
        size_t operator()(const string& str) const
        {
                return __stl_hash_string(str.c_str());
        }
};

在聲明自己的哈希函數時要注意以下幾點:

  1. 使用struct,然後重載operator().返回是size_t參數是你要hash的key的類型。函數是const類型的。

    (二)hash_map 的比較函數

     

    在map中的比較函數,需要提供less函數。如果沒有提供,缺省的也是less< Key> 。在hash_map中,要比較桶內的數據和key是否相等,因此需要的是是否等於的函數:equal_to< Key> 。先看看equal_to的源碼:

    //本代碼可以從SGI STL
    //先看看binary_function 函數聲明,其實只是定義一些類型而已。
    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 mystruct{ int iID; int len; bool operator==(const mystruct & my) const{ return (iID==my.iID) && (len==my.len) ; } };

    這樣,就可以使用equal_to< mystruct>作為比較函數了。另一種方法就是使用函數對象。自定義一個比較函數體:

    struct compare_str{
            bool operator()(const char* p1, const char*p2) const{
                    return strcmp(p1,p2)==0;
            }
    };

    有了compare_str,就可以使用hash_map了。

    typedef hash_map, compare_str> StrIntMap;
    StrIntMap namemap;
    namemap["岳不群"]="華山派掌門人,人稱君子劍";
    namemap["張三豐"]="武當掌門人,太極拳創始人";
    namemap["東方不敗"]="第一高手,葵花寶典";

    (三)如何在hash_map中加入自己定義的類型?

     

    #include 
    #include 
    #include 
    
    using namespace std;
    //define the class
    class ClassA{
            public:
            ClassA(int a):c_a(a){}
            int getvalue()const { return c_a;}
            void setvalue(int a){c_a;}
            private:
            int c_a;
    };
    
    //1 define the hash function
    struct hash_A{
            size_t operator()(const class ClassA & A)const{
                    //  return  hash(classA.getvalue());
                    return A.getvalue();
            }
    };
    

    //2 define the equal function
    struct equal_A{
            bool operator()(const class ClassA & a1, const class ClassA & a2)const{
                    return  a1.getvalue() == a2.getvalue();
            }
    };
    
    int main()
    {
            hash_map hmap;
            ClassA a1(12);
            hmap[a1]="I am 12";
            ClassA a2(198877);
            hmap[a2]="I am 198877";
            
            cout<

     

     

     

     

     

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved