Home IT Linux Windows Database Network Programming Server Mobile  
           
  Home \ Programming \ map and hash_map STL containers     - Java object initialization (Programming)

- VMware virtual machine to use bridged mode fast Internet access (Linux)

- Lucene Getting Started Tutorial (Server)

- Thrift 0.9.3 compiler installation under Ubuntu (Linux)

- Oracle GoldenGate Installation and Configuration Tutorial Introduction (Database)

- How to adjust the system time CentOS (Linux)

- How to use secure FTP file transfer (Server)

- SSL VPN SSL VPN access to security websites patron (Linux)

- Oracle Client Easy Connection error ORA-12154, TNS-03505 (Database)

- Binary tree traversal: the first sequence in order preorder recursive and non-recursive and traversal sequence (Programming)

- Linux system package manager (rpm, yum, source packages installation) (Linux)

- Linux, security encryption to transfer files between machines (Linux)

- Compile Android libwebcore.so error occurs when solving (Programming)

- Linux systems for entry-learning - Install Go language in Linux (Linux)

- Oracle procedure or function Empty Table (Database)

- Install GAMIT / GLOBK 10.50 software under Ubuntu 14.04 (Linux)

- CentOS yum install LAMP (Server)

- Nginx version information hidden or modified (Server)

- Detailed LVM2 (Linux)

- Zabbix monitors Nginx status (Server)

 
         
  map and hash_map STL containers
     
  Add Date : 2017-01-08      
         
       
         
  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;
}
     
         
       
         
  More:      
 
- CentOS install Redis (Database)
- Shell Common Command Summary (Programming)
- Try to use Lets Encrypt (Linux)
- VMware11 virtual machine Ubuntu14.10 system partition sda1 disk expansion (Linux)
- LAMP environment to build Apache, MySQL, PHP under Ubuntu (Server)
- Forbid screen change the window size when creating a new window under CentOS (Linux)
- MySQL Data Types (Database)
- learning Linux ls command examples (Linux)
- Lua non-blocking write log (Programming)
- Configuring Allatori code confusion when developing general Java applications in NetBeans (Programming)
- Compression decompression command under Linux (Linux)
- How to use the command line to obtain Freely RSS source on Linux (Linux)
- Oracle database with test data insertion speed (Database)
- Linux shell script debugging (Linux)
- How wifi-linux AP signal strength detection (Linux)
- Shilpa Nair interview experience sharing RedHat Linux package management (Linux)
- Java development specifications summary (Programming)
- Linux check disk parameters trapping lack amendments (Linux)
- Java reflection technology explain (Programming)
- Ubuntu 12.04 installation DHCP Server (Server)
     
           
     
  CopyRight 2002-2016 newfreesoft.com, All Rights Reserved.