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. More...

#include <hash.h>

Inheritance diagram for ABA_HASH< KeyType, ItemType >:

List of all members.

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.

---

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.

---

Constructor & Destructor Documentation

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.

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.

template<class KeyType, class ItemType>

ABA_HASH< KeyType, ItemType >::ABA_HASH

(

const ABA_HASH< KeyType, ItemType > &

rhs

)

[private]

---

Member Function Documentation

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.

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.

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.

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.

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.

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.

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.

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.

template<class KeyType, class ItemType>

int ABA_HASH< KeyType, ItemType >::size

(

)

const

Returns:

The length of the hash table.

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().

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).

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.

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.

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.

template<class KeyType, class ItemType>

ABA_HASH& ABA_HASH< KeyType, ItemType >::operator=

(

const ABA_HASH< KeyType, ItemType > &

rhs

)

[private]

---

Friends And Related Function Documentation

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.

---

Member Data Documentation

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.

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.

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.

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.

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

---