Util::HashTable< KEYTYPE, VALUETYPE > Class Template Reference
#include <hashtable.h>
Detailed Description
template<class KEYTYPE, class VALUETYPE>
class Util::HashTable< KEYTYPE, VALUETYPE >
Organizes key/value pairs by a hash code. Looks very similar to a Dictionary, but may provide better search times (up to O(1)) by computing a (ideally unique) hash code on the key and using that as an index into an array. The flipside is that the key class must provide a hash code and the memory footprint may be larger then Dictionary.The default capacity is 128. Matching the capacity against the number of expected elements in the hash table is one key to get optimal insertion and search times, the other is to provide a good (and fast) hash code computation which produces as few collissions as possible for the key type.
The key class must implement the following method in order to work with the HashTable: IndexT HashCode() const;
The Util::String class implements this method as an example. Internally the hash table is implemented as a fixed array of sorted arrays. The fixed array is indexed by the hash code of the key, the sorted arrays contain all values with identical keys.
(C) 2006 Radon Labs GmbH
Public Member Functions | |
| HashTable () | |
| default constructor | |
| HashTable (SizeT capacity) | |
| constructor with capacity | |
| HashTable (const HashTable< KEYTYPE, VALUETYPE > &rhs) | |
| copy constructor | |
| void | operator= (const HashTable< KEYTYPE, VALUETYPE > &rhs) |
| assignment operator | |
| VALUETYPE & | operator[] (const KEYTYPE &key) const |
| read/write [] operator, assertion if key not found | |
| SizeT | Size () const |
| return current number of values in the hashtable | |
| SizeT | Capacity () const |
| return fixed-size capacity of the hash table | |
| void | Clear () |
| clear the hashtable | |
| bool | IsEmpty () const |
| return true if empty | |
| void | Add (const KeyValuePair< KEYTYPE, VALUETYPE > &kvp) |
| add a key/value pair object to the hash table | |
| void | Add (const KEYTYPE &key, const VALUETYPE &value) |
| add a key and associated value | |
| void | Erase (const KEYTYPE &key) |
| erase an entry | |
| bool | Contains (const KEYTYPE &key) const |
| return true if key exists in the array | |
|
Array< KeyValuePair< KEYTYPE, VALUETYPE > > | Content () const |
| return array of all key/value pairs in the table (slow) | |