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

Hash tables. More...

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

Inheritance diagram for abacus::AbaHash< KeyType, ItemType >:

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.
	~AbaHash ()
	The destructor.
ItemType *	find (const KeyType &key)
	Looks for an item in the hash table with a given key.
const ItemType *	find (const KeyType &key) const
	Looks for an item in the hash table with a given key.
bool	find (const KeyType &key, const ItemType &item) const
	Checks if a prespecified item with a prespecified key is contained in the hash table.
void	insert (const KeyType &newKey, const ItemType &newItem)
	Adds an item to the hash table.
int	nCollisions () const
	Returns the number of collisions which occurred during all previous calls of the functions insert() and overWrite().
void	overWrite (const KeyType &newKey, const ItemType &newItem)
	Adds a item to the has table (with overwrite).
int	remove (const KeyType &key)
	Removes the first item with a given key from the hash table.
int	remove (const KeyType &key, const ItemType &item)
	Removes the first item with a given key and a prespecified element from the hash table.
void	resize (int newSize)
	Can be used to change the size of the hash table.
int	size () const
	Returns the length of the hash table.
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.
const ItemType *	initializeIteration (const KeyType &key) const
	This function retrieves the first item.
ItemType *	next (const KeyType &key)
	This function can be used to go to the next item in the hash table with key key.
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.
Public Member Functions inherited from abacus::AbacusRoot
virtual	~AbacusRoot ()
	The destructor.

Private Member Functions
	AbaHash (const AbaHash &rhs)
int	hf (const string &str) const
	This is a hash function for character strings.
int	hf (int key) const
	Computes the hash value of key.
int	hf (unsigned key) const
	This version of hf() implements a Fibonacci hash function for keys of type unsigned.
AbaHash &	operator= (const AbaHash &rhs)

Private Attributes
AbaHashItem< KeyType, ItemType > *	iter_
	An iterator for all items stored in a slot.
int	nCollisions_
	The number of collisions on calls of insert() and overWrite().
int	size_
	The length of the hash table.
AbaHashItem< KeyType, ItemType > **	table_
	The hash table storing a linked list of hash items in each slot.

Friends
std::ostream &	operator<< (std::ostream &out, const AbaHash< KeyType, ItemType > &hash)
	The output operator.

Additional Inherited Members
Static Public Member Functions inherited from abacus::AbacusRoot
static bool	ascii2bool (const string &str)
	Converts the string str to a boolean value.
static bool	endsWith (const string &str, const string &end)
	Returns true if str ends with end, false otherwise.
static double	fracPart (double x)
	Returns the absolute value of the fractional part of x.
static const char *	onOff (bool value)
	Converts a boolean variable to the strings "on" and "off".

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 124 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

size	The 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

key	The 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

key	The 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

key	The key of the item.
item	The 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

key	The 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

key	The 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

newKey	The key of the new item.
newItem	The 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

key	The 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

key	The 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

newKey	The key of the new item.
newItem	The 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

key	The 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

key	The key of the item that should be removed.
item	The 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

newSize

The 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 Symbol 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

out	The output stream.
hash	The 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:

• include/ogdf/lib/abacus/hash.h