#include <HashMap.h>
Inheritance diagram for HashMap:
It uses a hash function to distribute all search keys over an array of buckets, and the same hash function to look them up again. Keys may be evaluating to the same bucket. In this case, they are both put into it. If the number of keys gets too high, a larger number of buckets is used, and all keys are distributed again.
Definition at line 48 of file HashMap.h.
Public Member Functions | |
bool | ContainsKey (void *key) const |
Returns, if the hash table contains a given key. | |
void | Delete (void *key) |
Removes a key/value pair from the hash table. | |
void | DeleteAll () |
Removes all key/value pairs from the hash table. | |
VALUETYPE * | Get (void *key) const |
Returns the value of a key/value pair by its key. | |
long | GetCount () const |
Returns the number of set keys. | |
int | GetDesiredFillRatio () const |
Returns the fill ratio after a hash table resize. | |
int | GetFillRatio () const |
Returns the current fill ratio. | |
PointeredList * | GetKeys () const |
Returns a new PointeredList of all keys currently in the hash table. | |
long | GetSize () const |
Returns the number of buckets currently used. | |
PointeredList * | GetValues () const |
Returns a new PointeredList of all values currently in the hash table. | |
HashMap (long initSize, int desiredFillRatio) | |
Creates a new hash table with customized settings. | |
HashMap (long initSize) | |
Creates a new hash table with an initial size. | |
HashMap () | |
Creates a new hash table. | |
bool | IsEmpty () const |
Returns whether there are no elements in the hash table. | |
void | Set (void *key, VALUETYPE *Value) |
Sets a key/value pair into the hash table. | |
VALUETYPE * | Unset (void *key) |
Removes a key/value pair from the hash table. | |
void | UnsetAll () |
Removes all key/value pairs from the hash table. | |
virtual | ~HashMap () |
Destroys the hash table. | |
Protected Member Functions | |
virtual void * | CreateKey (void *key) const |
Creates the key object that shall be stored in the key buckets. | |
virtual void | DestroyKey (void *key) const |
Disposes a key created by the CreateKey method. | |
virtual bool | Equals (void *key1, void *key2) const |
Checks, if to keys equal each other. | |
virtual unsigned long | HashCode (void *key) const |
Returns the hash code of the key. | |
Protected Attributes | |
PointeredList ** | KeyBuckets |
The array of key buckets. | |
long | Size |
The number of buckets currently used. | |
PointeredList ** | ValueBuckets |
The array of value buckets. | |
Private Member Functions | |
void | CheckSize () |
Checks, whether the hash table has to be resized, and resizes it if necessary. | |
void | Init (long initSize, int desiredFillRatio) |
Initializes the hash table. | |
void | Rehash (long newSize) |
Resizes and rehashes the hash table. | |
void | SetWithoutSizeChecking (void *key, VALUETYPE *Value) |
Sets a key/value pair into the hash table without checking the hash table size afterwards. | |
Private Attributes | |
long | Count |
The number of used hash table cells. | |
int | DesiredFillRatio |
The fill ratio after a hash table resize. | |
long | InitSize |
The minimum and initial size of the hash table. |
|
Creates a new hash table.
|
|
Creates a new hash table with an initial size.
|
|
Creates a new hash table with customized settings.
|
|
Destroys the hash table. The memory of the keys is not freed, since it was not acquired, but the memory of the values is freed. |
|
Checks, whether the hash table has to be resized, and resizes it if necessary.
|
|
Returns, if the hash table contains a given key.
|
|
Creates the key object that shall be stored in the key buckets. The method receives a key and e.g. creates a clone, or uses the key directly, if this is possible. The Equals and HashCode method must return the same values when using the original key and the one returned by this method. The DestroyKey method disposes this key again. In the HashMap class, the key is returned directly.
Reimplemented in StringKeyHashMap, StringKeyHashMap< Void >, StringKeyHashMap< Option >, StringKeyHashMap< ConfigSection >, and StringKeyHashMap< ConfigParameter >. |
|
Removes a key/value pair from the hash table. The memory of the key is not freed, since it was not acquired, but the memory of the value is freed.
|
|
Removes all key/value pairs from the hash table. The memory of the keys is not freed, since it was not acquired, but the memory of the values is freed. |
|
Disposes a key created by the CreateKey method. This can be done by freeing the memory, if the key was cloned, or by simply doing nothing, if the user's key was directly used. This method should do the opposite of the CreateKey method. In the HashMap class, this method does nothing, since the key was directly used.
Reimplemented in StringKeyHashMap, StringKeyHashMap< Void >, StringKeyHashMap< Option >, StringKeyHashMap< ConfigSection >, and StringKeyHashMap< ConfigParameter >. |
|
Checks, if to keys equal each other. In the HashMap class, this is true, if they point to the same memory.
Reimplemented in StringKeyHashMap, ICStringKeyHashMap, StringKeyHashMap< Void >, StringKeyHashMap< Option >, StringKeyHashMap< ConfigSection >, StringKeyHashMap< ConfigParameter >, and ICStringKeyHashMap< Void >. |
|
Returns the value of a key/value pair by its key.
|
|
Returns the number of set keys.
Reimplemented in HashSet. |
|
Returns the fill ratio after a hash table resize.
|
|
Returns the current fill ratio. This is the ratio between the used hash table cells (Count), and the reserved cells (Size).
|
|
Returns a new PointeredList of all keys currently in the hash table.
|
|
Returns the number of buckets currently used.
|
|
Returns a new PointeredList of all values currently in the hash table.
|
|
Returns the hash code of the key. This is a value that has to be constant for the same key all the time, needs not to be injective, and should distribute the keys quite good.
Reimplemented in IntKeyHashMap, StringKeyHashMap, ICStringKeyHashMap, IntKeyHashMap< Void >, StringKeyHashMap< Void >, StringKeyHashMap< Option >, StringKeyHashMap< ConfigSection >, StringKeyHashMap< ConfigParameter >, and ICStringKeyHashMap< Void >. |
|
Initializes the hash table.
|
|
Returns whether there are no elements in the hash table.
Reimplemented in HashSet. |
|
Resizes and rehashes the hash table.
|
|
Sets a key/value pair into the hash table. Afterwards, the method checks if the hash table has to be resized. If the key existed, the old value is replaced, and its memory is freed.
|
|
Sets a key/value pair into the hash table without checking the hash table size afterwards. This is required during the rehashing and setting. If the key already exists, it is destroyed and the old value is replaced by the new one.
|
|
Removes a key/value pair from the hash table. Afterwards, the method checks if the hash table has to be resized. Both the memory of the key and the memory of the value are not freed, but the value is returned.
|
|
Removes all key/value pairs from the hash table. Afterwards, the method checks if the hash table has to be resized. Both the memory of the keys and the memory of the values are not freed.
|
|
The number of used hash table cells. This is the number of set keys. |
|
The fill ratio after a hash table resize. This happens, if the fill ratio gets higher than one and a half times the fill ratio or lower than half the fill ratio. The rest of the buckets is reserved for further setting of keys. |
|
The minimum and initial size of the hash table. This is the minimum and initial number of buckets. |
|
The array of key buckets.
|
|
The number of buckets currently used.
|
|
The array of value buckets.
|