| |
First, Introduction
On applications, map already a member of STL standard library, and hash_map yet to enter standard library, ext is an extension of a function, but it is also very common and very important library.
Second, a simple comparison
First, to say that these two data structures are provided in the KEY-VALUE storage and search functions. But implementation is not the same, map with a red-black tree, query time complexity log (n). And hash_map hash table is used, query time complexity theory can be a constant, but consume large memory, to store a method for time.
Tree Find, compare hash lookup table in the total efficiency, but it is very stable, its computational complexity does not fluctuate. In a lookup, you can conclude that under the worst case it will not exceed its complexity is O (log2N). The hash table is not the same, is O (1), or O (N), or in between, you can not grasp.
Three, hash_map use
Visible, if you define a complete hash_map, the need to provide and other five template parameters, since the latter three have default values, so in general we only you need to provide the first two.
1> Defines __gnu_cxx :: hash_map < string, int> myHashMap not go wrong, but once on myHashMap operation, a compile error occurs "instantiated from here", this is because the gnu version hash_map only achieved a limited number of hash function template (see the third template parameters, these functions hash_fun.h in), and these functions include in hash < const char *>, but does not include the hash < std :: string> is instantiated. The solution is to define a hash table before an instance of your own specialization, so that the compiler knows the call this function.
namespace __gnu_cxx
{
template < >
struct hash < string>
{
size_t operator () (const string & s) const
{Return __stl_hash_string (s.c_str ());}
};
}
2> The fourth parameter is equal to determine significance of key functions
int main ()
{
__gnu_cxx :: hash_map < const char *, int> myHashMap;
char name1 [10] = "zhu";
char name2 [10] = "zhu";
myHashMap [name1] = 1;
__gnu_cxx :: hash_map :: iterator it = myHashMap.find (name2);
if (it == myHashMap.end ())
cout << "not find" << endl;
return 0;
}
You will find that although name1 and name2 are zhu, but inserted name1, name2 when used to find or search no results. This is related to the fourth template parameter determines key equal, the default is std :: equal_to, this function is defined by operator == to judge, of course, is the address pointer is equal to the same, and name1 and name2 the address is obviously different. The solution is to use your specified function template instead of the default.
#include < cstring>
#include < iostream>
#include < ext / hash_map>
#include < backward / hash_fun.h>
using namespace std;
template < class _Tp>
struct my_equal_to: public binary_function < _Tp, _Tp, bool>
{
bool operator () (const _Tp & __x, const _Tp & __y) const
{Return strcmp (__ x, __y) == 0;}
};
int main ()
{
__gnu_cxx :: hash_map < const char *, int, __gnu_cxx :: hash < const char *>, my_equal_to < const char *>> myHashMap;
char name1 [10] = "zhu";
char name2 [10] = "zhu";
myHashMap [name1] = 1;
__gnu_cxx :: hash_map < const char *, int, __gnu_cxx :: hash < const char *>, my_equal_to < const char *>> :: iterator it = myHashMap.find (name2);
if (it == myHashMap.end ())
cout << "not find" << endl;
else
cout << it-> second << endl;
return 0;
}
With just specialized hash_map < string, int> is to be found, because the string overloaded operator == operators.
Compiled using -Wno-deprecated option, otherwise there will be backward_warning.h header file alarms.
Fourth, superficial comparison test (map, hash_map system hash function and self-write hash function hash_map)
[Linuxhost @ localhost ~] $ cat /tmp/name.txt | wc -l
25848136
# From an existing game database of 561,916 lira role name (which already has a duplicate), then added several times repeated, becomes
# 25840000 row of data
hash_map 1. System hash function to achieve
#include < iostream>
#include < fstream>
#include < string>
#include < ext / hash_map>
using namespace std;
// Specialization hash function string version
namespace __gnu_cxx
{
template < >
struct hash < string>
{
size_t operator () (const string & s) const
{Return __stl_hash_string (s.c_str ());}
};
}
// Calculate the current time
void curTime ()
{
time_t aTime = time (NULL);
struct tm * curtime = localtime (& aTime);
char ctemp [20];
strftime (ctemp, 20, "% Y-% m-% d% H:% M:% S", curtime);
cout << ctemp << endl;
}
int main ()
{
__gnu_cxx :: hash_map < string, int> fileMap;
string temp; // temporary storage string of each line
int i = 0; // count the total number of
ifstream in;
in.open ( "/ tmp / name.txt", ifstream :: in);
if (! in)
{
cout << "open file failed" << endl;
return 1;
}
curTime (); // timer starts here
while (in >> temp)
{
if (fileMap.find (temp) == fileMap.end ())
{
++ I;
fileMap [temp] = i;
}
}
curTime (); // Timing End
cout << i << endl;
in.close ();
return 0;
}
# Compiler
[Linuxhost @ localhost ~] $ g ++ -Wno-deprecated 3.cpp -o hashMap
2. Since the write hash function hash_map
#include < iostream>
#include < fstream>
#include < string>
#include < ext / hash_map>
using namespace std;
struct strHash {
size_t operator () (const string & str) const
{
unsigned long __h = 0;
for (size_t i = 0; i
__h = 107 * __ h + str [i];
return size_t (__ h);
}
};
void curTime ()
{
time_t aTime = time (NULL);
struct tm * curtime = localtime (& aTime);
char ctemp [20];
strftime (ctemp, 20, "% Y-% m-% d% H:% M:% S", curtime);
cout << ctemp << endl;
}
int main ()
{
__gnu_cxx :: hash_map < string, int, strHash> fileMap;
string temp;
int i = 0;
ifstream in;
in.open ( "/ tmp / name.txt", ifstream :: in);
if (! in)
{
cout << "open file failed" << endl;
return 1;
}
curTime ();
while (in >> temp)
{
if (fileMap.find (temp) == fileMap.end ())
{
++ I;
fileMap [temp] = i;
}
}
curTime ();
cout << i << endl;
in.close ();
return 0;
}
# Compiler
[Linuxhost @ localhost ~] $ g ++ -Wno-deprecated 4.cpp -o strhashMap
3.STL the map
#include < iostream>
#include < fstream>
#include < string>
#include < map>
using namespace std;
void curTime ()
{
time_t aTime = time (NULL);
struct tm * curtime = localtime (& aTime);
char ctemp [20];
strftime (ctemp, 20, "% Y-% m-% d% H:% M:% S", curtime);
cout << ctemp << endl;
}
int main ()
{
map < string, int> fileMap;
string temp;
int i = 0;
ifstream in;
in.open ( "/ tmp / name.txt", ifstream :: in);
if (! in)
{
cout << "open file failed" << endl;
return 1;
}
curTime ();
while (in >> temp)
{
if (fileMap.find (temp) == fileMap.end ())
{
++ I;
fileMap [temp] = i;
}
}
curTime ();
cout << i << endl;
in.close ();
return 0;
}
1
2 # compiler
[Linuxhost @ localhost ~] $ g ++ 2.cpp -o map
4. Run View results
[Linuxhost @ localhost ~] $ ./hashMap # 7 Miao
2015-11-06 16:25:41
2015-11-06 16:25:48
459 256
[Linuxhost @ localhost ~] $ ./strhashMap # 8 seconds and above is almost the same
2015-11-06 16:25:50
2015-11-06 16:25:58
459 256
[Linuxhost @ localhost ~] $ ./map # 26 Miao
2015-11-06 16:26:02
2015-11-06 16:26:28
459 256
V. Summary
This test is only for personal entertainment, and there is no real value. Finally, in one sentence, hash_map based hash_table achieve, and to hash_table is to double-edged sword, with good efficiency high O (1), and ran with the bad O (N) went.
Sixth, pay attention hash_map loop
This question simply, it is a gnu implementation is inside has a _M_Cur pointer indicating the current location A, each calculation operator ++, calls the hash function to calculate the next position with the key B the current position, if key after incoming hash_map, and its contents externally damaged, leading to B position hash function calculated before the a position, then after the arrival a from B, will jump back to B, forming a BA interval loop.
#include < iostream>
#include < cstring>
#include < ext / hash_map>
using namespace std;
int main ()
{
__gnu_cxx :: hash_map < char *, int> hashMap;
char name [10] = "zhu";
hashMap.insert (pair < char *, int> (name, 1));
strncpy (name, "wang", 10); // external changes that have been passed hash_map the key, resulting in an infinite loop
for (__gnu_cxx :: hash_map :: iterator it = hashMap.begin (); it = hashMap.end ();! ++ it)
{
cout << it-> first << "" << it-> second << endl;
}
return 0;
} |
|
|
|