Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

abacus::AbaHash< KeyType, ItemType > Class Template Reference

Hash tables. More...

#include <ogdf/lib/abacus/hash.h>

Public Member Functions

 AbaHash (int size)
 Initializes each slot with a 0-pointer 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...
 
AbaHashoperator= (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...
 

Detailed Description

template<class KeyType, class ItemType>
class abacus::AbaHash< KeyType, ItemType >

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,..., n-1}, 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.

Definition at line 38 of file hash.h.

Constructor & Destructor Documentation

◆ AbaHash() [1/2]

template<class KeyType , class ItemType >
abacus::AbaHash< KeyType, ItemType >::AbaHash ( int  size)
explicit

Initializes each slot with a 0-pointer to indicate that the linked list of hash items of this slot is empty.

Parameters
sizeThe size of the hash table.

◆ ~AbaHash()

template<class KeyType , class ItemType >
abacus::AbaHash< KeyType, ItemType >::~AbaHash ( )

The destructor.

Deletes each hash item by going through all non-empty lists of hash items.

◆ AbaHash() [2/2]

template<class KeyType , class ItemType >
abacus::AbaHash< KeyType, ItemType >::AbaHash ( const AbaHash< KeyType, ItemType > &  rhs)
private

Member Function Documentation

◆ find() [1/3]

template<class KeyType , class ItemType >
ItemType* abacus::AbaHash< KeyType, ItemType >::find ( const KeyType &  key)

Looks for an item in the hash table with a given key.

Parameters
keyThe key of the searched item.
Returns
A pointer to an item with the given key, or a 0-pointer if there is no item with this key in the hash table. If there is more than one item in the hash table with this key, a pointer to the first item found is returned.

◆ find() [2/3]

template<class KeyType , class ItemType >
const ItemType* abacus::AbaHash< KeyType, ItemType >::find ( const KeyType &  key) const

Looks for an item in the hash table with a given key.

Parameters
keyThe key of the searched item.
Returns
A pointer to an item with the given key, or a 0-pointer if there is no item with this key in the hash table. If there is more than one item in the hash table with this key, a pointer to the first item found is returned.

◆ find() [3/3]

template<class KeyType , class ItemType >
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.

Parameters
keyThe key of the item.
itemThe searched item.
Returns
true If there is an element (key, item) in the hash table, false otherwise.

◆ hf() [1/3]

template<class KeyType , class ItemType >
int abacus::AbaHash< KeyType, ItemType >::hf ( const string &  str) const
private

This is a hash function for character strings.

It is taken from Knuth, 1993, page 300.

◆ hf() [2/3]

template<class KeyType , class ItemType >
int abacus::AbaHash< KeyType, ItemType >::hf ( int  key) const
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.

◆ hf() [3/3]

template<class KeyType , class ItemType >
int abacus::AbaHash< KeyType, ItemType >::hf ( unsigned  key) const
private

This version of hf() implements a Fibonacci hash function for keys of type unsigned.

◆ initializeIteration() [1/2]

template<class KeyType , class ItemType >
ItemType* abacus::AbaHash< KeyType, ItemType >::initializeIteration ( const KeyType &  key)

This function retrieves the first item.

Parameters
keyThe key of the items through which we want to iterate.
Returns
A pointer to the first item found in the hash table having key key, or 0 if there is no such item.

◆ initializeIteration() [2/2]

template<class KeyType , class ItemType >
const ItemType* abacus::AbaHash< KeyType, ItemType >::initializeIteration ( const KeyType &  key) const

This function retrieves the first item.

Parameters
keyThe key of the items through which we want to iterate.
Returns
A const pointer to the first item found in the hash table having key key, or 0 if there is no such item.

◆ insert()

template<class KeyType , class ItemType >
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.

Parameters
newKeyThe key of the new item.
newItemThe item being inserted.

◆ nCollisions()

template<class KeyType , class ItemType >
int abacus::AbaHash< KeyType, ItemType >::nCollisions ( ) const

Returns the number of collisions which occurred during all previous calls of the functions insert() and overWrite().

◆ next() [1/2]

template<class KeyType , class ItemType >
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().

Note
The function next() gives you the next item having key key but not the next item in the linked list starting in a slot of the hash table.
Parameters
keyThe key of the items through which we want to iterate.
Returns
A pointer to the next item having key key, or 0 if there is no more item with this key in the hash table.

◆ next() [2/2]

template<class KeyType , class ItemType >
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().

Note
The function next() gives you the next item having key key but not the next item in the linked list starting in a slot of the hash table.
Parameters
keyThe key of the items through which we want to iterate.
Returns
A const pointer to the next item having key key, or 0 if there is no more item with this key in the hash table.

◆ operator=()

template<class KeyType , class ItemType >
AbaHash& abacus::AbaHash< KeyType, ItemType >::operator= ( const AbaHash< KeyType, ItemType > &  rhs)
private

◆ overWrite()

template<class KeyType , class ItemType >
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.

Parameters
newKeyThe key of the new item.
newItemThe item being inserted.

◆ remove() [1/2]

template<class KeyType , class ItemType >
int abacus::AbaHash< KeyType, ItemType >::remove ( const KeyType &  key)

Removes the first item with a given key from the hash table.

Parameters
keyThe key of the item that should be removed.
Returns
0 If an item with the key is found.
1 If there is no item with this key.

◆ remove() [2/2]

template<class KeyType , class ItemType >
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.

Parameters
keyThe key of the item that should be removed.
itemThe item which is searched.
Returns
0 If an item with the key is found.
1 If there is no item with this key.

◆ resize()

template<class KeyType , class ItemType >
void abacus::AbaHash< KeyType, ItemType >::resize ( int  newSize)

Can be used to change the size of the hash table.

Parameters
newSizeThe new size of the hash table (must be positive).

◆ size()

template<class KeyType , class ItemType >
int abacus::AbaHash< KeyType, ItemType >::size ( ) const

Returns the length of the hash table.

Friends And Related Function Documentation

◆ operator<<

template<class KeyType , class ItemType >
std::ostream& operator<< ( std::ostream &  out,
const AbaHash< KeyType, ItemType > &  hash 
)
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.

Parameters
outThe output stream.
hashThe hash table being output.
Returns
A reference to the output stream.

Member Data Documentation

◆ iter_

template<class KeyType , class ItemType >
AbaHashItem<KeyType, ItemType>* abacus::AbaHash< KeyType, ItemType >::iter_
mutableprivate

An iterator for all items stored in a slot.

This variable is initialized by calling initializeIteration() and incremented by the function next().

Definition at line 332 of file hash.h.

◆ nCollisions_

template<class KeyType , class ItemType >
int abacus::AbaHash< KeyType, ItemType >::nCollisions_
private

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

Definition at line 325 of file hash.h.

◆ size_

template<class KeyType , class ItemType >
int abacus::AbaHash< KeyType, ItemType >::size_
private

The length of the hash table.

Definition at line 322 of file hash.h.

◆ table_

template<class KeyType , class ItemType >
AbaHashItem<KeyType, ItemType>** abacus::AbaHash< KeyType, ItemType >::table_
private

The hash table storing a linked list of hash items in each slot.

table_[i] is initialized with a 0-pointer in order to indicate that it is empty. The linked lists of each slot are terminated with a 0-pointer, too.

Definition at line 319 of file hash.h.


The documentation for this class was generated from the following file: