About Hash Table

# Hash in C++

collate::hash

long hash (const charT* low, const charT* high) const;
Get hash value
Returns the hash value of the string corresponding to the character sequence [low,high).


A hash for a string is a value that uniquely* identifies the content of the string, so that two strings with the same hash value, would compare equal by collate::compare, and two strings with different hash values would compare not equal.


Example

// collate::hash example
#include <iostream>
#include <locale>
using namespace std;

int main ()
{
  string myberry = "strawberry";
  string yourberry;

  locale loc;                 // the "C" locale

  const collate<char>& coll = use_facet<collate<char> >(loc);

  long myhash = coll.hash(myberry.data(),myberry.data()+myberry.length());

  cout << "Please, enter your favorite berry:";
  getline (cin,yourberry);

  long yourhash = coll.hash(yourberry.data(),yourberry.data()+yourberry.length());

  if (myhash == yourhash)
    cout << "Mine too!\n";
  else
    cout << "I prefer strawberries...\n";

  return 0;

# A case in SGI extension, not in C++ standard:
http://www.sgi.com/tech/stl/hash_map.html
http://en.wikipedia.org/wiki/Hash_map_%28C%2B%2B%29


Defined in the header hash_map, and in the backward-compatibility header hash_map.h. This class is an SGI extension; it is not part of the C++ standard.
In C++ computer programming, hash_map is the name of a hashed associative container in the Standard Template Library. It is provided by several implementors, such as the GNU C++ compiler and Microsoft's Visual C++. It is not part of the C++ Standard Library, but the upcoming C++0x standard will define the TR1-proposed class unordered_map.



hash_map<const char*, int, hash<const char*>, eqstr> months;


The hash_map template accepts five template arguments:

std::hash_map<Key, Data, HashFcn, EqualKey, Alloc>

==> Usage with the GNU C++ compiler:

#include <ext/hash_map>
namespace std { using namespace __gnu_cxx; }

==> Usage with Microsoft Visual C++:

#include <hash_map>


==> Example with GNU C++

This is the same example given in the SGI's STL official page.

#include <iostream>
#include <hash_map>
#include <cstring>
using namespace std;
using namespace __gnu_cxx;
struct eqstr{
bool operator()(const char* s1, const char* s2) const {
return strcmp(s1,s2)==0;
}
};
int main(){
hash_map<const char*, int, hash<const char*>, eqstr> months;
months["january"] = 31;
months["february"] = 28;
months["march"] = 31;
months["april"] = 30;
months["may"] = 31;
months["june"] = 30;
months["july"] = 31;
months["august"] = 31;
months["september"] = 30;
months["october"] = 31;
months["november"] = 30;
months["december"] = 31;
cout << "september -> " << months["september"] << endl;
cout << "april     -> " << months["april"] << endl;
cout << "june      -> " << months["june"] << endl;
cout << "november  -> " << months["november"] << endl; 
return 0;
}

==>Another useful links with different implementation for hash table:

http://forums.devshed.com/c-programming-42/tip-about-stl-hash-map-and-string-55093.html


==>Another useful link:
 http://zitronensaft.blogspot.com/2008/02/using-hashmap-on-gcc.html
If you have tried to use some STL containers with GCC, such as hash_map:

// error: hash_map: No such file or directory#include <hash_map>int main()
{
 // error: ‘hash_map’ is not a member of ‘std’ std::hash_map<int,int> hm;
 return 0;
}

Then you have realized that the code above does not compile. That's because on GCC, hash_map is not regarded as a standard container, but rather as a extension included in the __gnu_cxx namespace. In order to use hash_map and other extended containers with a minimum impact in your code (which is very important if it's intended to be cross-platform), you can use the following solution:

#ifdef __GNUC__
#include <ext/hash_map>
#else
#include <hash_map>
#endif
namespace std
{
 using namespace __gnu_cxx;
}

int main()
{
 std::hash_map<int,int> hm;
 return 0;
}

Related Comments:
[C1] In fact, hash maps are not a part of the C++ standard yet. They have been added to the working draft, and there is an almost complete implementation of the specification which was recently accepted into Boost (http://igaztanaga.drivehq.com/unordered/) that should smooth the transition to C++0x even more
[C2] Ricardo J. said...Google has a solution for hash_map. You must install "sparsehash" (apt-get install sparsehash). The documentation is here: http://code.google.com/p/google-sparsehash/
Example:
#include <iostream>
#include <google/sparse_hash_map>

using google::sparse_hash_map; /* namespace where class lives by default */
using std::cout;
using std::endl;
using __gnu_cxx::hash; /* or ext::hash, or maybe tr1::hash, depending on your OS */

struct eqstr
{
   bool operator()(const char* s1, const char* s2) const
   {
      return (s1 == s2) || (s1 && s2 && strcmp(s1, s2) == 0);
   }
};

int main()
{
     sparse_hash_map<const char*, int, hash<const char*>, eqstr> months;
     sparse_hash_map<const char*, int, hash<const char*>, eqstr>::iterator It;

     months.set_deleted_key(NULL);
     months["january"] = 31;
     months["february"] = 28;
     months["march"] = 31;
     months["april"] = 30;
     months["may"] = 31;
     months["june"] = 30;
     months["july"] = 31;
     months["august"] = 31;
     months["september"] = 30;
     months["october"] = 31;
     months["november"] = 30;
     months["december"] = 31;

     cout << "september -> " << months["september"] << endl;
     cout << "april     -> " << months["april"] << endl;
     cout << "june      -> " << months["june"] << endl;
     cout << "november  -> " << months["november"] << endl;

     /* Find and erase */
     It = months.find("january");
     if (It != months.end())
     {
        cout << "january found" << endl;
        cout << "erasing january" << endl;
        months.erase(It);

        if (months.find("january") == months.end())
            cout << "january erased" << endl;
        else

            cout << "january NOT erased" << endl;
     }
     else
        cout << "january NOT found" << endl;
     return 0;
}

♥ ¸¸.•*¨*•♫♪♪♫•*¨*•.¸¸♥