Tools.h++ Manual

104011 Tandem Computers Incorporated 22-41
22
RWTPtrHashTable<T>
Synopsis #include <rw/tphasht.h>
unsigned hashFun(const T&);
RWTPtrHashTable<T> table(hashFun);
Description This class implements a parameterized hash table of types T . It uses chaining
to resolve hash collisions. Duplicates are allowed.
It is a pointer based collection: pointers to objects are copied in and out of the
hash buckets.
Parameter T represents the type of object to be inserted into the table, either a
class or built in type. The class T must have:
• well-defined equality semantics ( T::operator==(const T&) ).
A user-supplied hashing function for type T must be supplied to the
constructor when creating a new table. If T is a Tools.h++ class, then this
requirement is usually trivial because all Tools.h++ objects know how to return
a hashing value. This function has prototype:
unsigned hFun (const T& a);
and should return a suitable hash value for the object a.
To find an object, it is first hashed to determine in which bucket it occurs. The
bucket is then searched for an object that is equal (as determined by the
equality operator) to the candidate.
The initial number of buckets in the table is set by the constructor. There is a
default value. If the number of items in the collection greatly exceeds the
number of buckets then efficiency will sag because each bucket must be
searched linearly. The number of buckets can be changed by calling member
function resize() . This is relatively expensive because all of the keys must
be rehashed.
If you wish for this to be done automatically, then you can subclass from this
class and implement your own special insert() and remove() functions
which perform a resize() as necessary.