Hash tables. More...
#include <ogdf/lib/abacus/hash.h>
Public Member Functions  
AbaHash (int size)  
Initializes each slot with a 0pointer to indicate that the linked list of hash items of this slot is empty. More...  
~AbaHash ()  
The destructor. More...  
ItemType *  find (const KeyType &key) 
Looks for an item in the hash table with a given key. More...  
const ItemType *  find (const KeyType &key) const 
Looks for an item in the hash table with a given key. More...  
bool  find (const KeyType &key, const ItemType &item) const 
Checks if a prespecified item with a prespecified key is contained in the hash table. More...  
void  insert (const KeyType &newKey, const ItemType &newItem) 
Adds an item to the hash table. More...  
int  nCollisions () const 
Returns the number of collisions which occurred during all previous calls of the functions insert() and overWrite(). More...  
void  overWrite (const KeyType &newKey, const ItemType &newItem) 
Adds a item to the has table (with overwrite). More...  
int  remove (const KeyType &key) 
Removes the first item with a given key from the hash table. More...  
int  remove (const KeyType &key, const ItemType &item) 
Removes the first item with a given key and a prespecified element from the hash table. More...  
void  resize (int newSize) 
Can be used to change the size of the hash table. More...  
int  size () const 
Returns the length of the hash table. More...  
The functions initializeIteration() and next() can be used to iterate through all items stored in the hash table having the same key.  
ItemType *  initializeIteration (const KeyType &key) 
This function retrieves the first item. More...  
const ItemType *  initializeIteration (const KeyType &key) const 
This function retrieves the first item. More...  
ItemType *  next (const KeyType &key) 
This function can be used to go to the next item in the hash table with key key. More...  
const ItemType *  next (const KeyType &key) const 
This function can be used to go to the next item in the hash table with key key. More...  
Private Member Functions  
AbaHash (const AbaHash &rhs)  
int  hf (const string &str) const 
This is a hash function for character strings. More...  
int  hf (int key) const 
Computes the hash value of key. More...  
int  hf (unsigned key) const 
This version of hf() implements a Fibonacci hash function for keys of type unsigned. More...  
AbaHash &  operator= (const AbaHash &rhs) 
Private Attributes  
AbaHashItem< KeyType, ItemType > *  iter_ 
An iterator for all items stored in a slot. More...  
int  nCollisions_ 
The number of collisions on calls of insert() and overWrite(). More...  
int  size_ 
The length of the hash table. More...  
AbaHashItem< KeyType, ItemType > **  table_ 
The hash table storing a linked list of hash items in each slot. More...  
Friends  
std::ostream &  operator<< (std::ostream &out, const AbaHash< KeyType, ItemType > &hash) 
The output operator. More...  
Hash tables.
This data structure stores a set of items and provides as central functions the insertion of a new item, the search for an item, and the deletion of an item.
Each item is associated with a key. The set of all possible keys is called the universe. A hash table has a fixed size n. A hash function assigns to each key of the universe a number in {0,..., n1}, which we denote slot. If an item is inserted in the hash table, then it is stored in the component of the array associated with its slot. Usually, n is much smaller than the cardinality of the universe. Hence, it can happen that two elements are mapped to the same slot. This is called a collision. In order to resolve collisions, each slot of the hash table does not store an item explicitly, but is the start of a linear list storing all items mapped to this slot.
This template implements a hash table where collisions are resolved by chaining. Currently hash functions for keys of type int and string are implemented. If you want to use this data structure for other types (e.g., YOURTYPE), you should derive a class from the class AbaHash and define a hash function {int hf(YOURTYPE key)}.
The following sections implement two new classes. The class AbaHash contains the hash table which consists of pointers to the class AbaHashItem. The class AbaHashItem stores an inserted element and its key and provides the a pointer to the next item in the linked list.

explicit 
Initializes each slot with a 0pointer to indicate that the linked list of hash items of this slot is empty.
size  The size of the hash table. 
abacus::AbaHash< KeyType, ItemType >::~AbaHash  (  ) 
The destructor.
Deletes each hash item by going through all nonempty lists of hash items.

private 
ItemType* abacus::AbaHash< KeyType, ItemType >::find  (  const KeyType &  key  ) 
Looks for an item in the hash table with a given key.
key  The key of the searched item. 
const ItemType* abacus::AbaHash< KeyType, ItemType >::find  (  const KeyType &  key  )  const 
Looks for an item in the hash table with a given key.
key  The key of the searched item. 
bool abacus::AbaHash< KeyType, ItemType >::find  (  const KeyType &  key, 
const ItemType &  item  
)  const 
Checks if a prespecified item with a prespecified key is contained in the hash table.
key  The key of the item. 
item  The searched item. 

private 
This is a hash function for character strings.
It is taken from Knuth, 1993, page 300.

private 
Computes the hash value of key.
It must be overloaded for all key types, which are used together with this template.
This following version of hf() implements a Fibonacci hash function for keys of type int.

private 
This version of hf() implements a Fibonacci hash function for keys of type unsigned.
ItemType* abacus::AbaHash< KeyType, ItemType >::initializeIteration  (  const KeyType &  key  ) 
This function retrieves the first item.
key  The key of the items through which we want to iterate. 
const ItemType* abacus::AbaHash< KeyType, ItemType >::initializeIteration  (  const KeyType &  key  )  const 
This function retrieves the first item.
key  The key of the items through which we want to iterate. 
void abacus::AbaHash< KeyType, ItemType >::insert  (  const KeyType &  newKey, 
const ItemType &  newItem  
) 
Adds an item to the hash table.
The new item is inserted at the head of the list in the corresponding slot. It is possible to insert several items with the same key into the hash table.
newKey  The key of the new item. 
newItem  The item being inserted. 
int abacus::AbaHash< KeyType, ItemType >::nCollisions  (  )  const 
Returns the number of collisions which occurred during all previous calls of the functions insert() and overWrite().
ItemType* abacus::AbaHash< KeyType, ItemType >::next  (  const KeyType &  key  ) 
This function can be used to go to the next item in the hash table with key key.
Before the first call of next() for a certain can the iteration has to be initialized by calling initializeItaration().
key  The key of the items through which we want to iterate. 
const ItemType* abacus::AbaHash< KeyType, ItemType >::next  (  const KeyType &  key  )  const 
This function can be used to go to the next item in the hash table with key key.
Before the first call of next() for a certain can the iteration has to be initialized by calling initializeItaration().
key  The key of the items through which we want to iterate. 

private 
void abacus::AbaHash< KeyType, ItemType >::overWrite  (  const KeyType &  newKey, 
const ItemType &  newItem  
) 
Adds a item to the has table (with overwrite).
Performs a regular insert() if there is no item with the same key in the hash table, otherwise the item is replaced by the new item.
newKey  The key of the new item. 
newItem  The item being inserted. 
int abacus::AbaHash< KeyType, ItemType >::remove  (  const KeyType &  key  ) 
Removes the first item with a given key from the hash table.
key  The key of the item that should be removed. 
int abacus::AbaHash< KeyType, ItemType >::remove  (  const KeyType &  key, 
const ItemType &  item  
) 
Removes the first item with a given key and a prespecified element from the hash table.
key  The key of the item that should be removed. 
item  The item which is searched. 
void abacus::AbaHash< KeyType, ItemType >::resize  (  int  newSize  ) 
Can be used to change the size of the hash table.
newSize  The new size of the hash table (must be positive). 
int abacus::AbaHash< KeyType, ItemType >::size  (  )  const 
Returns the length of the hash table.

friend 
The output operator.
Writes row by row all elements stored in the list associated with a slot on an output stream.
The output of an empty slot is suppressed.
out  The output stream. 
hash  The hash table being output. 

mutableprivate 
An iterator for all items stored in a slot.
This variable is initialized by calling initializeIteration() and incremented by the function next().

private 
The number of collisions on calls of insert() and overWrite().

private 

private 