数据结构：hash

数据结构：hash_map

在C++11以上的开发环境中，请直接把map替换成unordered_map，不要使用hash_map

之前我们专门有一篇介绍哈希表，多维哈希表的博文，当时就是以map举例子，然后说了一句把map替换成hash_map就好了

但是事实并非如此，在使用hash_map的时候还需要遵循两个规范

其一就是引用头文件和命名空间的时候要注意，并且这种hash_map只能在GNU C++下使用

其二就是对于自定义类型必须手写一个hash函数，就连string也不例外，而且在必要时提供“==”运算符的重载

这里以Luogu3370的字符串哈希例题来说明一下用法

 1 #include<ext/hash_map>
 2 #include<string>
 3 #include<cstdio>
 4 #include<iostream> 
 5 using namespace std;
 6 using namespace __gnu_cxx;
 7 const int maxn=10005;
 8 int n;
 9 struct str_hash
10 {
11     size_t operator()(const string &str) const
12     {
13         return __stl_hash_string(str.c_str());
14     }
15 };
16 /*
17 struct str_hash
18 {
19     size_t operator()(const string& str) const
20     {
21         unsigned long __h = 0;
22         for (size_t i = 0 ; i < str.size() ; i ++)
23         __h = 5*__h + str[i];
24         return size_t(__h);
25     }
26 };
27 */
28 struct str_euqal
29 {
30     bool operator()(const string &s1,const string &s2) const
31     {
32         return s1==s2;
33     }
34 };
35 hash_map<string,int,str_hash,str_euqal> mp;
36 int main()
37 {
38     string str;
39     scanf("%d",&n);
40     while(n--)
41     {
42         cin>>str;
43         mp[str]++;
44     }
45     cout<<mp.size()<<endl;
46     return 0;
47 }

如果你觉得C++的string太慢了不爽，可以用C语言的形式

struct compare_str
{
    bool operator()(const char* p1, const char*p2) const
    {
        return strcmp(p1,p2)==0;
    }
};
hash_map<const char*, string, hash<const char*>, compare_str> StrIntMap;

我们注意到second那一维度无所谓，只需要处理键那一位，也就是first那一维就好了