- #include <cstdlib>
- #include <iostream>
- #include <string>
- #include <hash_map>
-
- using namespace std;
-
-
-
-
-
- class str_hash{
- public:
- 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);
- }
- };
-
-
-
-
-
- class str_compare
- {
- public:
- bool operator()(const string& str1,const string& str2)const
- {return str1==str2;}
- };
-
- int
- main(int argc, char *argv[])
- {
- hash_map<string,string,str_hash,str_compare> myhash;
-
- myhash["google"]="newplan";
-
- myhash["baidu"]="zhaoziming";
-
- if(myhash.find("google")!=myhash.end())
- cout<<myhash["google"]<<endl;
-
- system("PAUSE");
-
- return EXIT_SUCCESS;
- }
在SGI STL中,提供了以下hash函数:
- 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>
在声明自己的hash函数时要注意以下几点: 1、使用struct,然后重载operator(); 2、返回size_t; 3、参数是你要hash的key的类型; 4、函数是const类型的;
hash_map和map的区别在哪里? (1)构造函数 hash_map需要hash函数,等于函数;map只需要比较函数(小于函数)。 (2)存储结构 hash_map采用hash表存储,map一般采用红黑树实现。因此内存数据结构是不一样的。
什么时候需要使用hash_map,什么时候需要map? 总体来说,hash_map 查找速度会比map快,而且查找速度基本和数据数据量大小,属于常数级别;而map的查找速度是log(n)级别。并不一定常数就比log(n)小, hash还有hash函数的耗时,明白了吧,如果你考虑效率,特别是在元素达到一定数量级时,考虑考虑hash_map。但若你对内存使用特别严格,希望 程序尽可能少消耗内存,那么一定要小心,hash_map可能会让你陷入尴尬,特别是当你的hash_map对象特别多时,你就更无法控制了,而且 hash_map的构造速度较慢。 现在知道如何选择了吗?权衡三个因素: 查找速度, 数据量, 内存使用。
为什么hash_map不是标准的? 具体为什么不 是标准的,我也不清楚,有个解释说在STL加入标准C++之时,hash_map系列当时还没有完全实现,以后应该会成为标准。如果谁知道更合理的解释, 也希望告诉我。但我想表达的是,正是因为hash_map不是标准的,所以许多平台上安装了g++编译器,不一定有hash_map的实现。我就遇到了这 样的例子。因此在使用这些非标准库的时候,一定要事先测试。另外,如果考虑到平台移植,还是少用为佳。
|