11.6 Function Objects for Hashing and Equality

The associative hash-based templates use a hash function object to determine how to place and locate objects within the collection class. An advantage of using hash-based collections is efficient, constant-time retrieval of objects. A disadvantage is that objects are maintained in an order determined by mapping the result of the hash function onto the physical layout of the collection class itself. Rarely does this ordering have a useful meaning beyond the internal machinations of the hash-based collection.

To avoid complete chaos, associative hash-based collections make use of an equality object. Collections which allow multiple keys that are equivalent to one another use the equality object to ensure that equivalent objects are grouped together. Hash collections which do not allow multiple keys use the equality object to ensure that only unique items are admitted. To do this, we need two template arguments in addition to the type or types of the elements being collected: a hash function object, and an equality object.

A hash function object is a class or struct that contains a const function-call operator that takes a const reference to a potential element of the collection class, and returns an unsigned long hash value. An equality object is a class or struct that contains a const function-call operator that takes two potential elements of the collection class, and returns true if the elements should be considered equivalent for the purpose of grouping objects or ensuring uniqueness within the collection class. The hash function object and the equality object must be related: any two objects which are considered equivalent must also have the same hash value. For example:

#include <rw/tvhset.h>   // contains RWTValHashSet
#include <rw/cstring.h>  // Contains RWCString

struct StringHash {
   unsigned long operator()(const RWCString& s) const
      {  return s.hash(); }
};

struct StringEqual {
   RWBoolean operator()(const RWCString& s, 
                        const RWCString& t) const
      {  return s == t; }
};

RWTValHashSet<RWCString, StringHash, StringEqual> rwhset;

Here we instantiate an RWTValHashSet of RWCStrings with our own hash function object and equality object. The example shows how to create these structs for use as template arguments even though, in this case, equal-to <RWCString> might have been used for the equality object.