Open
Graph Drawing
Framework

 v.2015.05
 

ogdf::Hashing< K, I, H > Class Template Reference

Hashing with chaining and table doubling. More...

#include <ogdf/basic/Hashing.h>

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

Public Types

typedef HashConstIterator< K, I, H > const_iterator
 The type of const-iterators for hash tables. More...
 

Public Member Functions

 Hashing (int minTableSize=256, const H &hashFunc=H())
 Creates a hash table for given initial table size minTableSize. More...
 
 Hashing (const Hashing< K, I > &h)
 Copy constructor. More...
 
 ~Hashing ()
 
HashConstIterator< K, I, H > begin () const
 Returns an hash iterator to the first element in the list of all elements. More...
 
void clear ()
 Removes all elements from the hash table. More...
 
void del (const K &key)
 Removes the element with key key from the hash table (does nothing if no such element). More...
 
bool empty () const
 Returns true iff the table is empty, i.e., contains no elements. More...
 
HashElement< K, I > * fastInsert (const K &key, const I &info)
 Inserts a new element with key key and information info into the hash table. More...
 
HashElement< K, I > * insert (const K &key, const I &info)
 Inserts a new element with key key and information info into the hash table. More...
 
HashElement< K, I > * insertByNeed (const K &key, const I &info)
 Inserts a new element with key key and information info into the hash table. More...
 
HashElement< K, I > * lookup (const K &key) const
 Returns the hash element with key key in the hash table; returns 0 if no such element. More...
 
bool member (const K &key) const
 Returns true iff the hash table contains an element with key key. More...
 
Hashing< K, I > & operator= (const Hashing< K, I > &hashing)
 Assignment operator. More...
 
int size () const
 Returns the number of elements in the hash table. More...
 

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

Private Member Functions

virtual HashElementBasecopy (HashElementBase *pElement) const
 Returns a copy of hash element pElement. More...
 
virtual void destroy (HashElementBase *pElement)
 Deletes hash element pElement. More...
 
- Private Member Functions inherited from ogdf::HashingBase
 HashingBase (int minTableSize)
 Creates a hash table with minimum table size minTableSize. More...
 
 HashingBase (const HashingBase &H)
 Copy constructor. More...
 
virtual ~HashingBase ()
 
void clear ()
 Removes all elements from the hash table. More...
 
void del (HashElementBase *pElement)
 Removes the element pElement from the hash table. More...
 
int empty () const
 Returns if the hash table is empty. More...
 
HashElementBasefirstElement (HashElementBase ***pList) const
 Returns the first element in the list of all elements in the hash table. More...
 
HashElementBasefirstListElement (size_t hashValue) const
 Returns the first element in the list for elements with hash value hashValue. More...
 
void insert (HashElementBase *pElement)
 Inserts a new element pElement into the hash table. More...
 
HashElementBasenextElement (HashElementBase ***pList, HashElementBase *pElement) const
 Returns the successor of pElement in the list of all elements in the hash table. More...
 
HashingBaseoperator= (const HashingBase &H)
 Assignment operator. More...
 
void resize (int newTableSize)
 Resizes the hash table to newTableSize. More...
 
int size () const
 Returns the number of elements in the hash table. More...
 
void destroyAll ()
 Deletes all elements in hash table (but does not free m_table!). More...
 

Private Attributes

m_hashFunc
 The hash function. More...
 
- Private Attributes inherited from ogdf::HashingBase
int m_count
 The current number of elements. More...
 
int m_hashMask
 The current table size minus one. More...
 
int m_minTableSize
 The minimal table size. More...
 
HashElementBase ** m_table
 The hash table (an array of lists). More...
 
int m_tableSize
 The current table size. More...
 
int m_tableSizeHigh
 The maximal number of elements at this table size. More...
 
int m_tableSizeLow
 The minimal number of elements at this table size. More...
 

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:

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

Definition at line 190 of file Hashing.h.

Member Typedef Documentation

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

The type of const-iterators for hash tables.

Definition at line 293 of file Hashing.h.

Constructor & Destructor Documentation

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 296 of file Hashing.h.

template<class K, class I, class H = DefHashFunc<K>>
ogdf::Hashing< K, I, H >::Hashing ( const Hashing< K, I > &  h)
inline

Copy constructor.

Definition at line 300 of file Hashing.h.

template<class K, class I, class H = DefHashFunc<K>>
ogdf::Hashing< K, I, H >::~Hashing ( )
inline

Definition at line 303 of file Hashing.h.

Member Function Documentation

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 512 of file Hashing.h.

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 391 of file Hashing.h.

template<class K, class I, class H = DefHashFunc<K>>
virtual HashElementBase* ogdf::Hashing< K, I, H >::copy ( HashElementBase pElement) const
inlineprivatevirtual

Returns a copy of hash element pElement.

Implements ogdf::HashingBase.

Definition at line 429 of file Hashing.h.

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 382 of file Hashing.h.

template<class K, class I, class H = DefHashFunc<K>>
virtual void ogdf::Hashing< K, I, H >::destroy ( HashElementBase pElement)
inlineprivatevirtual

Deletes hash element pElement.

Implements ogdf::HashingBase.

Definition at line 424 of file Hashing.h.

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 309 of file Hashing.h.

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 375 of file Hashing.h.

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
pListis assigned the list containing the first element.
Returns
a pointer to the first element or 0 if hash table is empty.

Definition at line 402 of file Hashing.h.

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 341 of file Hashing.h.

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 360 of file Hashing.h.

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 0 if no such element.

Definition at line 318 of file Hashing.h.

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 312 of file Hashing.h.

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
pListis assigned the list containing the first element.
pElementpoints to an element in the has table.
Returns
a pointer to the first element or 0 if hash table is empty.

Definition at line 415 of file Hashing.h.

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

Assignment operator.

Definition at line 328 of file Hashing.h.

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 306 of file Hashing.h.

Friends And Related Function Documentation

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

Definition at line 288 of file Hashing.h.

Member Data Documentation

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

The hash function.

Definition at line 289 of file Hashing.h.


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