RWHashTableRWCollection
#include <rw/hashtab.h> RWHashTable h ;
This class is a simple hash table for objects inheriting from RWCollectable. It uses chaining (as implemented by class RWSlistCollectables) to resolve hash collisions. Duplicate objects are allowed.
An object stored by RWHashTable must inherit from the abstract base class RWCollectable, with suitable definition for virtual functions hash() and isEqual() (see class RWCollectable).
To find an object that matches a key, the key's virtual function hash() is first called to determine in which bucket the object occurs. The bucket is then searched linearly by calling the virtual function isEqual() for each candidate, with the key as the argument. The first object to return TRUE is the returned object.
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 will require that all objects be rehashed.
The iterator for this class is RWHashTableIterator.
Polymorphic
#include <rw/hashtab.h>
#include <rw/colldate.h>
#include <rw/rstream.h>
main(){
RWHashTable table;
RWCollectableDate *july
= new RWCollectableDate(7, "July", 1990);
RWCollectableDate *may
= new RWCollectableDate (1, "May", 1977);
RWCollectableDate *feb
= new RWCollectableDate (22, "Feb", 1983);
RWCollectableDate *aug
= new RWCollectableDate (2, "Aug", 1966);
table.insert(july);
table.insert(may);
table.insert(feb);
table.insert(aug);
cout << "Table contains " << table.entries() << " entries.\n";
RWCollectableDate key(22, "Feb", 1983);
cout << "It does ";
if (!table.contains(&key)) cout << "not ";
cout << "contain the key " << key << endl;
delete july;
delete may;
delete feb;
delete aug;
return 0;
}
Program output:
Table contains 4 entries. It does contain the key February 22, 1983
RWHashTable(size_t N = RWCollection::DEFAULT_CAPACITY);
Construct an empty hash table with N buckets.
RWHashTable(const RWHashTable& t);
Copy constructor. Create a new hash table as a shallow copy of the table t. The new table will have the same number of buckets as the old table. Hence, the members need not be and will not be rehashed.
void operator=(const RWHashTable& t);
Assignment operator. Sets self as a shallow copy of t. Afterwards, the two tables will have the same number of buckets. Hence, the members need not be and will not be rehashed.
RWBoolean operator==(const RWHashTable& t) const;
Returns TRUE if self and t have the same number of elements and if for every key in self there is a corresponding key in t which isEqual.
RWBoolean operator<=(const RWHashTable& t) const;
Returns TRUE if self is a subset of t, that is, every element of self has a counterpart in t which isEqual. Note: If you inherit from RWHashTable in the presence of the Standard C++ Library, we recommend that you override this operator and explicitly forward the call. Overload resolution in C++ will choose the Standard Library provided global operators over inherited class members. These global definitions are not appropriate for set-like partial orderings.
RWBoolean operator!=(const RWHashTable&) const;
Returns the negation of operator==(), above.
virtual void apply(RWapplyCollectable ap, void*);
Redefined from RWCollection. The function pointed to by ap will be called for each member in the collection. Because of the nature of hashing collections, this will not be done in any particular order. The function should not do anything that could change the hash value or equality properties of the objects.
virtual RWspace binaryStoreSize() const;
Inherited from RWCollection.
virtual void clear();
Redefined from RWCollection.
virtual void clearAndDestroy();
Inherited from RWCollection.
virtual int compareTo(const RWCollectable*) const;
Inherited from RWCollection.
virtual RWBoolean contains(const RWCollectable*) const;
Inherited from RWCollection.
virtual size_t entries() const;
Redefined from RWCollection.
virtual RWCollectable* find(const RWCollectable*) const;
Redefined from RWCollection.
virtual unsigned hash() const;
Inherited from RWCollection.
virtual RWCollectable* insert(RWCollectable* a);
Redefined from RWCollection. Returns a if successful, nil otherwise.
virtual RWClassID isA() const;
Redefined from RWCollection to return __RWHASHTABLE.
virtual RWBoolean isEmpty() const;
Redefined from RWCollection.
virtual RWBoolean isEqual(const RWCollectable*) const;
Redefined from RWCollection.
virtual RWCollectable* newSpecies() const;
Redefined from RWCollection.
virtual size_t occurrencesOf(const RWCollectable*) const;
Redefined from RWCollection.
virtual RWCollectable* remove(const RWCollectable*);
Redefined from RWCollection.
virtual void removeAndDestroy(const RWCollectable*);
Inherited from RWCollection.
virtual void resize(size_t n = 0);
Resizes the internal hash table to have n buckets. This causes rehashing all the members of the collection. If n is zero, then an appropriate size will be picked automatically.
virtual void restoreGuts(RWvistream&); virtual void restoreGuts(RWFile&); virtual void saveGuts(RWvostream&) const; virtual void saveGuts(RWFile&) const;
Inherited from class RWCollection.
RWStringID stringID();
(acts virtual) Inherited from class RWCollectable.