C++ Hash Table Memoization: Simplifying Dynamic Programming

Sample Code for gcc

gcc puts the hashing header files in the ext folder, and uses the __gnu_cxx namespace, isolating the non-standard library extensions into a ghetto of sorts. Both of these are dealt with in the first two lines of the sample code below.

The gcc implementation of hash_map needs two template parameters to handle keys that aren't defined as built-in types: one class that has an operator which returns a hash index given an input key, and a second that returns a boolean value for equality test. I pack both of these into a single class, SampleTraits. The traits class is then passed to the hash_map type definition as the third and fourth template parameters.

When you are defining the hash function, you need to somehow combine hash values for each of the members of your structure. Creating hash keys is somewhat of an art, so I try to use the ones provided by the library writer as the basis for my hash function. In this case I take the hash values for the two members of class Sample and simply XOR them together, which should provide a decent value.

If you are using g++ 4.x, you may be better off using the TR1 unordered_map class. While it is not quite part of the standard yet, it should be soon, and that will insure its future support and compatibility.

#include <ext/hash_map> 
using namespace __gnu_cxx; 
#include <string> 
class Sample { 
public : 
   Sample( int age=-1, const std::string &genre="" ) 
   : mAge( age ) 
   , mGenre( genre ){} 
   int mAge; 
   std::string mGenre; 
}; 
struct SampleTraits 
{ 
   size_t operator()( const Sample& that ) const 
   { 
      return hash<int>()( that.mAge ) ^ 
        hash<const char *>()( that.mGenre.c_str() ); 
   } 
   bool operator()( const Sample &that1, const Sample& that2 ) const 
   { 
      return that1.mAge == that2.mAge && that1.mGenre == that2.mGenre; 
   } 
}; 
int main() 
{ 
   hash_map<Sample, 
      int, 
      SampleTraits, 
      SampleTraits< AnnualBooksReadByAgeAndGenre; 
      AnnualBooksReadByAgeAndGenre[ Sample( 15, "Fantasy" ) ] = 15; 
      AnnualBooksReadByAgeAndGenre[ Sample( 18, "Sports" ) ] = 12; 
      AnnualBooksReadByAgeAndGenre[ Sample( 35, "Mystery" ) ] = 17; 
      AnnualBooksReadByAgeAndGenre[ Sample( 42, "Romance" ) ] = 125; 
   return 1; 
} 

Visual C++ .NET 2003/2005

Microsoft's compilers have similar issues, but deal with them differently. (That's the problem with non-standard features.)

Although the hash_map header file is accessed from the normal C++ header folder, the class itself, as was the case with g++, is defined in a different namespace, stdext. Again, that is dealt with in the first two lines of the sample code.

The remaining two issues are resolved by defining a global hash_value class that has an operator that returns a hash key for a given object of class Sample, and a global comparison operator that is used to test for equality of two objects of class Sample. (It is not unusual to use the less-than operator to test for equality, by testing both a > b and a < b, we determine whether the objects are equal or not.)

#include <hash_map> 
using namespace stdext; 
#include <string> 
class Sample { 
public : 
  Sample( int age=-1, const std::string &genre="" ) 
    : mAge( age ) 
    , mGenre( genre ){} 
    int mAge; 
    std::string mGenre; 
}; 
   namespace stdext { 
     size_t hash_value( const Sample& that ) 
     { 
        return hash_value( that.mAge ) ^ hash_value( that.mGenre ); 
     } 
}; 
bool operator<( const Sample& that1, const Sample& that2) 
{ 
    return that1.mAge <that2.mAge && that1.mGenre <that2.mGenre; 
} 
int main() 
{ 
    hash_map<Sample,int> AnnualBooksReadByAgeAndGenre; 
    AnnualBooksReadByAgeAndGenre[ Sample( 15, "Fantasy" ) ] = 15; 
    AnnualBooksReadByAgeAndGenre[ Sample( 18, "Sports" )  ] = 12; 
    AnnualBooksReadByAgeAndGenre[ Sample( 35, "Mystery" ) ] = 17; 
    AnnualBooksReadByAgeAndGenre[ Sample( 42, "Romance" ) ] = 125; 
    return 1; 
} 

Some Notes on Usage

The member functions of most implementations of hash_map will be identical to those of the standard std::map container. Storing an entry in a hash_map can be done using an overloaded operator that makes the container look like an associative array:

hash_map<std::string,int>my_map; 
 ... 
my_map[ "foo" ] = 42; 

Looking up a value from the table is done using a call to hash_map::find(). This method takes a reference to a key as its argument, and returns an iterator which points to the end of the container on failure, or to a key/value pair on success. The pair is stored in an std::pair object, which allows you to access the elements with the first and second members of that object:

hash_map<std::string,int>::iterator ii = my_map.find( "bar" ); 
if ( ii == my_map.end() ) 
    std::cout <<"Couldn't find an entry for 'bar'\n"; 
else 
    std::cout <<"Entry in map for key '" 
              <<ii->first 
              <<" is " 
              <<ii->second 
              <<"\n";