Tools.h++ Manual

104011 Tandem Computers Incorporated 22-85
22
RWTValHashDictionary<K,V>
Synopsis #include <rw/tvhdict.h>
unsigned hashFun(const K&);
RWTValHashDictionary<K,V> dictionary(hashFun);
Description RWTValHashDictionary<K,V> is a dictionary of keys of type K and values of
type V , implemented using a hash table. While duplicates of values are
allowed, duplicates of keys are not.
It is a value based collection: keys and values are copied in and out of the hash
buckets.
Parameters K and V represent the type of the key and the type of the value,
respectively, to be inserted into the table. These can be either classes or built in
types. Classes K and V must have:
• well-defined copy semantics ( T::T(const T&) or equiv.);
• well-defined assignment semantics ( T::operator=(const T&) or equiv.).
In addition, class K must have
• well-defined equality semantics ( K::operator==(const K&) .
A user-supplied hashing function for type K must be supplied to the
constructor when creating a new table. If K is a “ 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 K& a);
and should return a suitable hash value for the object a .
To find a value, the key is first hashed to determine in which bucket the key
and value can be found. The bucket is then searched for an object that is equal
(as determined by the equality operator) to the key.
The initial number of buckets in the table is set by the constructor. There is a
default value. If the number of (key/value) pairs 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