#include <hash.h>
Public Methods | |
| HashTable (Key(*get)(T x), unsigned(*hFunc)(Key x)) | |
| initialize a hash table. More... | |
| ~HashTable () | |
| deallocate a hash table. More... | |
| void | Insert (T item) |
| Put item into hash table. More... | |
| T | Remove (Key key) |
| Remove item from hash table. More... | |
| bool | Find (Key key, T *itemPtr) const |
| Find an item from its key. More... | |
| bool | IsInTable (Key key) |
| Is the item in the table? More... | |
| bool | IsEmpty () |
| does the table have anything in it. More... | |
| void | Apply (void(*f)(T)) const |
| apply function to all elements in table. More... | |
| void | SanityCheck () const |
| is this still a legal hash table? More... | |
| void | SelfTest (T *p, int numItems) |
| is the module working? More... | |
Private Types | |
| typedef List<T>* | Bucket |
Private Methods | |
| void | InitBuckets (int size) |
| void | DeleteBuckets (Bucket *table, int size) |
| deallocate bucket array. More... | |
| int | HashValue (Key key) const |
| which bucket does the key hash to? More... | |
| void | ReHash () |
| expand the hash table. More... | |
| bool | FindInBucket (int bucket, Key key, T *itemPtr) const |
| find item in bucket. More... | |
| int | FindNextFullBucket (int start) const |
| find next full bucket starting from this one. More... | |
Private Attributes | |
| Bucket* | buckets |
| the array of hash buckets. More... | |
| int | numBuckets |
| the number of buckets. More... | |
| int | numItems |
| the number of items in the table. More... | |
| Key (* | getKey )(T x) |
| get Key from value. More... | |
| unsigned (* | hash )(Key x) |
| the hash function. More... | |
| friend | HashIterator<Key,T> |
Definition at line 40 of file hash.h.
|
|||
|
|
|
||||||
|
initialize a hash table. HashTable<Key,T>::HashTable Initialize a hash table, empty to start with. Elements can now be added to the table. |
|
||||
|
deallocate a hash table. HashTable<T>~HashTable Prepare a hash table for deallocation. |
|
||||
|
apply function to all elements in table. HashTable<Key,T>::Apply Apply function to every item in the hash table. "func" -- the function to apply |
|
||||||
|
deallocate bucket array.
Referenced by ReHash(), and ~HashTable().
|
|
||||||
|
Find an item from its key. HashTable<Key,T>::Find Find an item from the hash table. Returns: The item or NULL if not found. Definition at line 193 of file hash.cc. Referenced by IsInTable().
|
|
||||||||
|
find item in bucket. HashTable<Key,T>::FindInBucket Find an item in a hash table bucket, from it's key "bucket" -- the list storing the item, if it's in the table "key" -- the key uniquely identifying the item Returns: Whether item is found, and if found, the item. Definition at line 168 of file hash.cc. Referenced by Find(), and Remove().
|
|
||||
|
find next full bucket starting from this one. HashTable<Key,T>::FindNextFullBucket Find the next bucket in the hash table that has any items in it. "bucket" -- where to start looking for full buckets Definition at line 251 of file hash.cc. Referenced by HashIterator::HashIterator(), and HashIterator::Next().
|
|
||||
|
which bucket does the key hash to? HashTable<Key,T>::HashValue Return hash table bucket that would contain key. Definition at line 89 of file hash.cc. Referenced by Find(), Insert(), ReHash(), Remove(), and SanityCheck().
|
|
||||
|
HashTable<Key,T>::InitBuckets Initialize the bucket array for a hash table. Called by the constructor and by ReHash(). Definition at line 45 of file hash.cc. Referenced by ReHash().
|
|
||||
|
Put item into hash table. HashTable<Key,T>::Insert Put an item into the hashtable. Resize the table if the # of elements / # of buckets is too big. Then allocate a HashElement to keep track of the key, item pair, and add it to the right bucket. "key" is the key we'll use to find this item. "item" is the thing to put in the table. Definition at line 110 of file hash.cc. Referenced by SelfTest().
|
|
||||
|
does the table have anything in it.
Definition at line 54 of file hash.h. Referenced by SelfTest(), and ~HashTable().
|
|
||||
|
Is the item in the table?
Definition at line 51 of file hash.h. Referenced by Insert(), Remove(), and SelfTest().
|
|
||||
|
expand the hash table. HashTable<Key,T>::ReHash Increase the size of the hashtable, by (i) making a new table (ii) moving all the elements into the new table (iii) deleting the old table Definition at line 136 of file hash.cc. Referenced by Insert().
|
|
||||
|
Remove item from hash table. HashTable<Key,T>::Remove Remove an item from the hash table. The item must be in the table. Returns: The removed item. Definition at line 210 of file hash.cc. Referenced by SelfTest().
|
|
||||
|
is this still a legal hash table? HashTable<Key,T>::SanityCheck Test whether this is still a legal hash table. Tests: are all the buckets legal? does the table have the right # of elements? do all the elements hash to where they are stored? Definition at line 272 of file hash.cc. Referenced by ReHash(), and SelfTest().
|
|
||||||
|
is the module working? HashTable<Key,T>::SelfTest Test whether this module is working. Definition at line 297 of file hash.cc. Referenced by LibSelfTest().
|
|
|||
|
|
|
|||
|
the array of hash buckets.
|
|
|||
|
get Key from value.
Referenced by FindInBucket(), Insert(), ReHash(), SanityCheck(), and SelfTest().
|
|
|||
|
the hash function.
|
|
|||
|
the number of buckets.
|
|
|||
|
the number of items in the table.
|
1.2.8.1 written by Dimitri van Heesch,
© 1997-2001