Customizing TR1 unordered_map Hashing and Equality Functions

A common problem people run into when using the C++ std::tr1::unordered_map or std::tr1::unordered_set is when they want to use a custom or aggregate type as the key in the hash table, and aren’t sure how to do it.

There isn’t really any official documentation about this; you can find some forum and StackOverflow discussions which may help; but I’ll run through a detailed example here too. Let’s start by taking a look at how the unordered_map class is defined:

template<class Key,
         class T,
         class Hash = hash<Key>,
         class Pred = std::equal_to<Key>,
         class Alloc = std::allocator<std::pair<const Key, T> > >
  class unordered_map;

The templated types in the class are:

  • class Key: key type (duh)
  • class T: value type
  • class Hash: hash function for type Key
  • class Pred: an equality predicate for type Key
  • class Alloc: the memory allocator for <Key, T>

The function represented in class Hash produces a hash value given a reference to type Key. This is the value that the map will use to locate the appropriate bucket to insert the corresponding value. The function represented by Pred is a predicate; it returns true if the values (as opposed to hash values) of Key types are equal. If the Key type is a class with operator== () defined, then defining a separate Pred function won’t be an issue.

Changing the Hash and Pred types is easy, but non-obvious. The most common reasons for this are either using a custom type as the key for the hash table, as I mentioned above, or for using a custom hash function to achieve better performance from the container.

Let’s say we have the following setup:

typedef struct
{
  uint32_t a;
  double x;
  double y;
} AggregateKey;

{ ... }

AggregateKey k;

{...}

std::tr1::unordered_map<AggregateKey, int> M;
M[k] = 1;

{...}

Attempting to compile this will generate a ton of error output. Depending on the situation, it’ll complain about Pred with something like

error: no match for ‘operator==’ in ‘__x == __y’

or about Hash with

undefined reference to `std::tr1::hash<AggregateKey>::operator()(AggregateKey) const'

Fix the issue by defining the following functors:

typedef struct
{
  long operator() (const AggregateKey &k) const { return my_hash_fnct (k); }
} AggregateKeyHash;

typedef struct
{
  bool operator() (const AggregateKey &x, const AggregateKey &y) const { return my_eq_test (x, y); }
} AggregateKeyEq;

AggregateKey k;

{...}

// Now, hash value generation and equality&nbsp;testing are
// defined for the AggregateKeyHash&nbsp;type, so declare the
// map using the functors&nbsp;above in the object's template list
std::tr1::unordered_map<AggregateKey, int, AggregateKeyHash, AggregateKeyEq> M;
M[k] = 1;

{...}

The same logic applies to the std::tr1::unordered_set, with the exception that its template list doesn’t include a class T value type. Also note that you can grab the any map’s default hash function and equality predicate at any time from the object:

std::tr1::unordered_map<int, int> M;

const std::tr1::unordered_map<int, int>::hasher &hfn = M.hash_function ();
const std::tr1::unordered_map<int, int>::key_equal &eqfn = M.key_eq ();

long h = hfn (123);
bool b = eqfn (1, 2);
About these ads

6 responses to “Customizing TR1 unordered_map Hashing and Equality Functions

  • --

    Many thanks! I’ve been trying to figure this out for the last few hours, trawling through SO and other forums. This is the only actually complete, working example that I’ve been able to find, and it was just what I needed!

    • --

      actually i guess i spoke too soon. this still is not a full working example. how would the hash and equality functions be defined in this example??

      • michael cvet

        The hash and equality functions are implementation-dependent – it all depends on how you want to do it. The equality test is straightforward: just test equality of each of the fields in the AggregateKey. For the hash, throw the AggregateKey struct into a hashing function like murmur hash or the like.

  • --

    the equality bit is pretty simple, but i still don’t quite get how i ought to go about the custom hashing function. i realize that this will be implementation dependent to a certain extent, but any working example with a struct or class based key would probably provide sufficient insight to generalize the process. are there any actual examples of doing this out there? i’ve been unable to find any.

    • --

      for example, how would i go about “throwing the aggregatekey struct into a hashing function like murmur”? i looked up the murmur project on googlecode, but there appear to be no examples of how to use it. clearly it is popular and does an excellent job, but for a noob like me it might as well be greek (and i dont speak greek).

      • michael cvet

        You just need to pass an opaque pointer to the struct into the hashing function. For example,

        AggregateKey a;

        …. // stuff

        int hash = murmurhash ((const void *) &a, sizeof (AggregateKey), 12345);

        and you have a hash.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: