Hashing with chaining and table doubling. More...

#include <ogdf/basic/Hashing.h>

Inheritance diagram for ogdf::Hashing< K, I, H >:

Public Types
using	const_iterator = HashConstIterator< K, I, H >
	The type of const-iterators for hash tables.

Public Member Functions
	Hashing (const Hashing< K, I, H > &h)=default
	Copy constructor.

	Hashing (int minTableSize=256, const H &hashFunc=H())
	Creates a hash table for given initial table size `minTableSize`.

	~Hashing ()
	Destruction.

HashConstIterator< K, I, H >	begin () const
	Returns an hash iterator to the first element in the list of all elements.

void	clear ()
	Removes all elements from the hash table.

void	del (const K &key)
	Removes the element with key `key` from the hash table (does nothing if no such element).

bool	empty () const
	Returns true iff the table is empty, i.e., contains no elements.

HashElement< K, I > *	fastInsert (const K &key, const I &info)
	Inserts a new element with key `key` and information `info` into the hash table.

HashElement< K, I > *	insert (const K &key, const I &info)
	Inserts a new element with key `key` and information `info` into the hash table.

HashElement< K, I > *	insertByNeed (const K &key, const I &info)
	Inserts a new element with key `key` and information `info` into the hash table.

HashElement< K, I > *	lookup (const K &key) const
	Returns the hash element with key `key` in the hash table; returns `nullptr` if no such element exists.

bool	member (const K &key) const
	Returns true iff the hash table contains an element with key `key`.

Hashing< K, I, H > &	operator= (const Hashing< K, I, H > &hashing)=default
	Assignment operator.

int	size () const
	Returns the number of elements in the hash table.

Protected Member Functions
HashElement< K, I > *	firstElement (HashElement< K, I > ***pList) const
	Returns the first element in the list of all elements in the hash table.

HashElement< K, I > *	nextElement (HashElement< K, I > **pList, HashElement< K, I > pElement) const
	Returns the successor of `pElement` in the list of all elements in the hash table.

Private Member Functions
virtual HashElementBase *	copy (HashElementBase *pElement) const override
	Returns a copy of hash element `pElement`.

virtual void	destroy (HashElementBase *pElement) override
	Deletes hash element `pElement`.

Private Member Functions inherited from ogdf::HashingBase
	HashingBase (const HashingBase &H)
	Copy constructor.

	HashingBase (int minTableSize)
	Creates a hash table with minimum table size `minTableSize`.

virtual	~HashingBase ()
	Destruction.

void	clear ()
	Removes all elements from the hash table.

void	del (HashElementBase *pElement)
	Removes the element `pElement` from the hash table.

int	empty () const
	Returns if the hash table is empty.

HashElementBase *	firstElement (HashElementBase ***pList) const
	Returns the first element in the list of all elements in the hash table.

HashElementBase *	firstListElement (size_t hashValue) const
	Returns the first element in the list for elements with hash value `hashValue`.

void	insert (HashElementBase *pElement)
	Inserts a new element `pElement` into the hash table.

HashElementBase *	nextElement (HashElementBase **pList, HashElementBase pElement) const
	Returns the successor of `pElement` in the list of all elements in the hash table.

HashingBase &	operator= (const HashingBase &H)
	Assignment operator.

void	resize (int newTableSize)
	Resizes the hash table to `newTableSize`.

int	size () const
	Returns the number of elements in the hash table.

void	destroyAll ()
	Deletes all elements in hash table (but does not free m_table!).

Private Attributes
H	m_hashFunc
	The hash function.

Private Attributes inherited from ogdf::HashingBase
int	m_count
	The current number of elements.

int	m_hashMask
	The current table size minus one.

int	m_minTableSize
	The minimal table size.

HashElementBase **	m_table
	The hash table (an array of lists).

int	m_tableSize
	The current table size.

int	m_tableSizeHigh
	The maximal number of elements at this table size.

int	m_tableSizeLow
	The minimal number of elements at this table size.

Friends
class	HashConstIterator< K, I, H >

Detailed Description

template<class K, class I, class H = DefHashFunc<K>>
class ogdf::Hashing< K, I, H >

Hashing with chaining and table doubling.

The class Hashing<K,I> implements a hashing table which realizes a mapping from a key type K to an information type I.

The class requires three template parameters:

Template Parameters

K	is the type of keys.
I	is the type of information.
H	is the hash function type. The hash function type argument is optional; its default uses the class DefHashFunc.

Hash function classes have to define int hash(const E &key) or int hash(E key).

Definition at line 261 of file Hashing.h.

Member Typedef Documentation

◆ const_iterator

template<class K , class I , class H = DefHashFunc<K>>

using ogdf::Hashing< K, I, H >::const_iterator = HashConstIterator<K, I, H>

The type of const-iterators for hash tables.

Definition at line 267 of file Hashing.h.

Constructor & Destructor Documentation

◆ Hashing() [1/2]

template<class K , class I , class H = DefHashFunc<K>>

ogdf::Hashing< K, I, H >::Hashing	(	int	minTableSize = `256`,
		const H &	hashFunc = `H()`
	)

inlineexplicit

Creates a hash table for given initial table size minTableSize.

Definition at line 270 of file Hashing.h.

◆ Hashing() [2/2]

template<class K , class I , class H = DefHashFunc<K>>

ogdf::Hashing< K, I, H >::Hashing ( const Hashing< K, I, H > & h )

default

Copy constructor.

◆ ~Hashing()

template<class K , class I , class H = DefHashFunc<K>>

ogdf::Hashing< K, I, H >::~Hashing ( )

inline

Destruction.

Definition at line 277 of file Hashing.h.

Member Function Documentation

◆ begin()

template<class K , class I , class H >

HashConstIterator< K, I, H > ogdf::Hashing< K, I, H >::begin ( ) const

inline

Returns an hash iterator to the first element in the list of all elements.

Definition at line 484 of file Hashing.h.

◆ clear()

template<class K , class I , class H = DefHashFunc<K>>

void ogdf::Hashing< K, I, H >::clear ( )

inline

Removes all elements from the hash table.

Definition at line 364 of file Hashing.h.

◆ copy()

template<class K , class I , class H = DefHashFunc<K>>

virtual HashElementBase * ogdf::Hashing< K, I, H >::copy ( HashElementBase * pElement ) const

inlineoverrideprivatevirtual

Returns a copy of hash element pElement.

Implements ogdf::HashingBase.

Definition at line 399 of file Hashing.h.

◆ del()

template<class K , class I , class H = DefHashFunc<K>>

void ogdf::Hashing< K, I, H >::del ( const K & key )

inline

Removes the element with key key from the hash table (does nothing if no such element).

Definition at line 355 of file Hashing.h.

◆ destroy()

template<class K , class I , class H = DefHashFunc<K>>

virtual void ogdf::Hashing< K, I, H >::destroy ( HashElementBase * pElement )

inlineoverrideprivatevirtual

Deletes hash element pElement.

Implements ogdf::HashingBase.

Definition at line 394 of file Hashing.h.

◆ empty()

template<class K , class I , class H = DefHashFunc<K>>

bool ogdf::Hashing< K, I, H >::empty ( ) const

inline

Returns true iff the table is empty, i.e., contains no elements.

Definition at line 283 of file Hashing.h.

◆ fastInsert()

template<class K , class I , class H = DefHashFunc<K>>

HashElement< K, I > * ogdf::Hashing< K, I, H >::fastInsert	(	const K &	key,
		const I &	info
	)

inline

Inserts a new element with key key and information info into the hash table.

This is a faster version of insert() that assumes that no element with key key is already contained in the hash table.

Definition at line 348 of file Hashing.h.

◆ firstElement()

template<class K , class I , class H = DefHashFunc<K>>

HashElement< K, I > * ogdf::Hashing< K, I, H >::firstElement ( HashElement< K, I > *** pList ) const

inlineprotected

Returns the first element in the list of all elements in the hash table.

This function is used by hash iterators for iterating over all elements in the hash table.

Parameters

pList is assigned the list containing the first element.

Returns: a pointer to the first element or nullptr if hash table is empty.

Definition at line 375 of file Hashing.h.

◆ insert()

template<class K , class I , class H = DefHashFunc<K>>

HashElement< K, I > * ogdf::Hashing< K, I, H >::insert	(	const K &	key,
		const I &	info
	)

inline

Inserts a new element with key key and information info into the hash table.

The new element will only be inserted if no element with key key is already contained; if such an element already exists the information of this element will be changed to info.

Definition at line 313 of file Hashing.h.

◆ insertByNeed()

template<class K , class I , class H = DefHashFunc<K>>

HashElement< K, I > * ogdf::Hashing< K, I, H >::insertByNeed	(	const K &	key,
		const I &	info
	)

inline

Inserts a new element with key key and information info into the hash table.

The new element will only be inserted if no element with key key is already contained; if such an element already exists the information of this element remains unchanged.

Definition at line 332 of file Hashing.h.

◆ lookup()

template<class K , class I , class H = DefHashFunc<K>>

HashElement< K, I > * ogdf::Hashing< K, I, H >::lookup ( const K & key ) const

inline

Returns the hash element with key key in the hash table; returns nullptr if no such element exists.

Definition at line 292 of file Hashing.h.

◆ member()

template<class K , class I , class H = DefHashFunc<K>>

bool ogdf::Hashing< K, I, H >::member ( const K & key ) const

inline

Returns true iff the hash table contains an element with key key.

Definition at line 286 of file Hashing.h.

◆ nextElement()

template<class K , class I , class H = DefHashFunc<K>>

HashElement< K, I > * ogdf::Hashing< K, I, H >::nextElement	(	HashElement< K, I > ***	pList,
		HashElement< K, I > *	pElement
	)		const

inlineprotected

Returns the successor of pElement in the list of all elements in the hash table.

This function is used by hash iterators for iterating over all elements in the hash table.

Parameters

pList	is assigned the list containing the first element.
pElement	points to an element in the has table.

Returns: a pointer to the first element or nullptr if hash table is empty.

Definition at line 388 of file Hashing.h.

◆ operator=()

template<class K , class I , class H = DefHashFunc<K>>

Hashing< K, I, H > & ogdf::Hashing< K, I, H >::operator= ( const Hashing< K, I, H > & hashing )

default

Assignment operator.

◆ size()

template<class K , class I , class H = DefHashFunc<K>>

int ogdf::Hashing< K, I, H >::size ( ) const

inline

Returns the number of elements in the hash table.

Definition at line 280 of file Hashing.h.

Friends And Related Symbol Documentation

◆ HashConstIterator< K, I, H >

template<class K , class I , class H = DefHashFunc<K>>

friend class HashConstIterator< K, I, H >

friend

Definition at line 240 of file Hashing.h.

Member Data Documentation

◆ m_hashFunc

template<class K , class I , class H = DefHashFunc<K>>

H ogdf::Hashing< K, I, H >::m_hashFunc

private

The hash function.

Definition at line 263 of file Hashing.h.

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

include/ogdf/basic/Hashing.h

OpenGraph DrawingFramework

Public Types

Public Member Functions

Protected Member Functions

Private Member Functions

Private Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ const_iterator

Constructor & Destructor Documentation

◆ Hashing() [1/2]

◆ Hashing() [2/2]

◆ ~Hashing()

Member Function Documentation

◆ begin()

◆ clear()

◆ copy()

◆ del()

◆ destroy()

◆ empty()

◆ fastInsert()

◆ firstElement()

◆ insert()

◆ insertByNeed()

◆ lookup()

◆ member()

◆ nextElement()

◆ operator=()

◆ size()

Friends And Related Symbol Documentation

◆ HashConstIterator< K, I, H >

Member Data Documentation

◆ m_hashFunc

Open
Graph Drawing
Framework