ABA_HASH< KeyType, ItemType > Class Template Reference

6.64 ABA_HASH< KeyType, ItemType > Class Template Reference

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.

#include <hash.h>

Inheritance diagram for ABA_HASH< KeyType, ItemType >::

Public Member Functions

ABA_HASH (ABA_GLOBAL *glob, int size)

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

The destructor deletes for each hash item by going through all non-empty lists of hash items.
void insert (const KeyType &newKey, const ItemType &newItem)
void overWrite (const KeyType &newKey, const ItemType &newItem)

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.
ItemType *find (const KeyType &key)
bool find (const KeyType &key, const ItemType &item)

This version of the function find() checks if a prespecified item with a prespecified key is contained in the hash table.
int remove (const KeyType &key)
int remove (const KeyType &key, const ItemType &item)

This version of the function remove() removes the first item with a given key and a prespecified element from the hash table.
int size () const
int nCollisions () const
void resize (int newSize)

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)
ItemType *next (const KeyType &key)

The function next() can be used to go to the next item in the hash table with key key.

Private Member Functions

int hf (int key)
int hf (unsigned key)

This version of hf() implements a Fibonacci hash function for keys of type unsigned.
int hf (const ABA_STRING &string)
ABA_HASH (const ABA_HASH &rhs)
ABA_HASH & operator= (const ABA_HASH &rhs)

Private Attributes

ABA_GLOBAL *glob_
ABA_HASHITEM< KeyType, ItemType > **table_
int size_
int nCollisions_
ABA_HASHITEM< KeyType, ItemType > *iter_

Friends

ostream & operator<< (ostream &out, const ABA_HASH< KeyType, ItemType > &hash)

The output operator writes row by row all elements stored in the list associated with a slot on an output stream.

6.64.1 Detailed Description

template<class KeyType, class ItemType> class ABA_HASH< KeyType, ItemType >

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.

Definition at line 137 of file hash.h.

6.64.2 Constructor & Destructor Documentation

6.64.2.1 template<class KeyType, class ItemType> ABA_HASH< KeyType, ItemType >::ABA_HASH (ABA_GLOBAL * glob, int size)

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

Parameters:

glob: A pointer to the corresponding global object.
size: The size of the hash table.

6.64.2.2 template<class KeyType, class ItemType> ABA_HASH< KeyType, ItemType >::~ABA_HASH ()

The destructor deletes for each hash item by going through all non-empty lists of hash items.

6.64.2.3 template<class KeyType, class ItemType> ABA_HASH< KeyType, ItemType >::ABA_HASH (const ABA_HASH< KeyType, ItemType > & rhs) [private]

6.64.3 Member Function Documentation

6.64.3.1 template<class KeyType, class ItemType> void ABA_HASH< 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:

key: The key of the new item.
item: The item being inserted.

6.64.3.2 template<class KeyType, class ItemType> void ABA_HASH< KeyType, ItemType >::overWrite (const KeyType & newKey, const ItemType & newItem)

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:

key: The key of the new item.
item: The item being inserted.

6.64.3.3 template<class KeyType, class ItemType> ItemType*ABA_HASH< KeyType, ItemType >::find (const KeyType & key)

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

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.

Parameters:

key: The key of the searched item.

6.64.3.4 template<class KeyType, class ItemType> bool ABA_HASH< KeyType, ItemType >::find (const KeyType & key, const ItemType & item)

This version of the function find() checks if a prespecified item with a prespecified key is contained in the hash table.

Returns:

true If there is an element (key, item) in the hash table,

false otherwise.

Parameters:

key: The key of the item.
item: The searched item.

6.64.3.5 template<class KeyType, class ItemType> ItemType*ABA_HASH< KeyType, ItemType >::initializeIteration (const KeyType & key)

The function initializeIteration() retrieves the first item.

Returns:: A pointer to the first item found in the hash table having key key, or 0 if there is no such item.

Parameters:

key: The key of the items through which we want to iterate.

6.64.3.6 template<class KeyType, class ItemType> ItemType*ABA_HASH< KeyType, ItemType >::next (const KeyType & key)

The function next() 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.

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.

Parameters:

key: The key of the items through which we want to iterate.

6.64.3.7 template<class KeyType, class ItemType> int ABA_HASH< KeyType, ItemType >::remove (const KeyType & key)

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

Returns:

0 If an item with the key is found.

1 If there is no item with this key.

Parameters:

key: The key of the item that should be removed.

6.64.3.8 template<class KeyType, class ItemType> int ABA_HASH< KeyType, ItemType >::remove (const KeyType & key, const ItemType & item)

This version of the function remove() removes the first item with a given key and a prespecified element from the hash table.

Returns:

0 If an item with the key is found.

1 If there is no item with this key.

Parameters:

key: The key of the item that should be removed.
item: The item which is searched.

6.64.3.9 template<class KeyType, class ItemType> int ABA_HASH< KeyType, ItemType >::size () const

Returns:: The length of the hash table.

6.64.3.10 template<class KeyType, class ItemType> int ABA_HASH< KeyType, ItemType >::nCollisions () const

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

6.64.3.11 template<class KeyType, class ItemType> void ABA_HASH< KeyType, ItemType >::resize (int newSize)

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

Parameters:

newSize: The new size of the hash table (must be positive).

6.64.3.12 template<class KeyType, class ItemType> int ABA_HASH< KeyType, ItemType >::hf (int key) [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.

6.64.3.13 template<class KeyType, class ItemType> int ABA_HASH< KeyType, ItemType >::hf (unsigned key) [private]

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

6.64.3.14 template<class KeyType, class ItemType> int ABA_HASH< KeyType, ItemType >::hf (const ABA_STRING & string) [private]

This is a hash function for character strings.

It is taken from Knu93a}, page 300.

6.64.3.15 template<class KeyType, class ItemType> ABA_HASH& ABA_HASH< KeyType, ItemType >::operator= (const ABA_HASH< KeyType, ItemType > & rhs) [private]

6.64.4 Friends And Related Function Documentation

6.64.4.1 template<class KeyType, class ItemType> ostream& operator<< (ostream & out, const ABA_HASH< 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.

Returns:: A reference to the output stream.

Parameters:

out: The output stream.
rhs: The hash table being output.

6.64.5 Member Data Documentation

6.64.5.1 template<class KeyType, class ItemType> ABA_GLOBAL*ABA_HASH< KeyType, ItemType >::glob_ [private]

A pointer to the corresponding global object.

Definition at line 331 of file hash.h.

6.64.5.2 template<class KeyType, class ItemType> ABA_HASHITEM<KeyType, ItemType>**ABA_HASH< 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 339 of file hash.h.

6.64.5.3 template<class KeyType, class ItemType> int ABA_HASH< KeyType, ItemType >::size_ [private]

The length of the hash table.

Definition at line 343 of file hash.h.

6.64.5.4 template<class KeyType, class ItemType> int ABA_HASH< KeyType, ItemType >::nCollisions_ [private]

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

Definition at line 347 of file hash.h.

6.64.5.5 template<class KeyType, class ItemType> ABA_HASHITEM<KeyType, ItemType>*ABA_HASH< KeyType, ItemType >::iter_ [private]

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 355 of file hash.h.

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

Include/abacus/hash.h

[next] [prev] [prev-tail] [front] [up]