Generic hash table implementation. More...

#include <HashTable.h>

Public Types
typedef Collection::List < RecType >::ConstIterator	ConstIterator
	Bidirectional non-mutable HashTable iterator.
typedef Collection::List < RecType >::Iterator	Iterator
	Bidirectional mutable HashTable iterator.
Public Member Functions
	HashTable (Size bucketHint)
	Default constructor.
	HashTable (const MyType &ht)
	Copy constructor.
	~HashTable ()
	Destructor.
Iterator	Back ()
	Iterator to the last element.
ConstIterator	Back () const
	Iterator to the last element.
Iterator	Begin ()
	Iterator to the first element.
ConstIterator	Begin () const
	Iterator to the first element.
Iterator	BucketBegin (Size bucket)
	Get iterator to the first node in a bucket.
ConstIterator	BucketBegin (Size bucket) const
	Get iterator to the first node in a bucket.
Iterator	BucketEnd (Size bucket)
	Iterator one behind the last element in a bucket.
ConstIterator	BucketEnd (Size bucket) const
	Iterator one behind the last element in a bucket.
Size	Buckets () const
	Get number of buckets.
bool	Contains (const KeyType &key) const
	Check if the table contains an element whose key is equal to `key`.
Size	Elements () const
	Get the number of elements in the table.
Iterator	End ()
	Iterator one behind the last element.
ConstIterator	End () const
	Iterator one behind the last element.
Iterator	Erase (Iterator it)
	Remove a given element from the table.
Iterator	Find (const KeyType &key)
	Find an element in the table whose key is equal to `key`.
ConstIterator	Find (const KeyType &key) const
	Find an element in the table whose key is equal to `key`.
MyType &	Free ()
	Free all memory occupied by the table.
Iterator	Front ()
	Iterator to the first element.
ConstIterator	Front () const
	Iterator to the first element.
Collection::Pair< Iterator, bool >	Insert (const RecType &val)
	Insert a new value into the table.
bool	IsEmpty () const
	Returns true if the table is empty.
Size	KeyBucketIndex (const KeyType &key) const
	Get bucket index for a given key.
MyType &	operator= (const MyType &ht)
	Assignment operator.
MyType &	Rehash (Size bucketHint)
	Rehash table.
MyType &	Swap (MyType &ht)
	Swap the content of two hash tables.
Protected Types
typedef Collection::Pair < Iterator, Iterator >	BucketType
	Each bucket holds iterators to a front and back element.
typedef HashTable< KeyType, RecType, KeySelectorType, HashFuncType, HashPolicyType, CompType >	MyType
Protected Member Functions
void	BucketEraseUpdate (Iterator it, BucketType &bucket)
	Update bucket front and back iterators on erase operation.
Iterator	BucketFind (const KeyType &key, const BucketType &bucket)
	Find an element with key `key` in a given bucket.
ConstIterator	BucketFind (const KeyType &key, const BucketType &bucket) const
	Find an element with key `key` in a given bucket.
void	BucketInsertUpdate (Iterator it, BucketType &bucket)
	Update bucket front and back iterators on insert operation.
void	Reinsert (Iterator last)
	Reinsert the range of elements [Begin(), last) into the buckets.
void	ResizeTable (Size buckets)
	Change the number of buckets.
void	SafeResizeBuckets (Size buckets)
	Change the number of buckets safely.
Size	ValBucketIndex (const RecType &val) const
	Get bucket index for a given record.

Detailed Description

template<class KeyType, class RecType, class KeySelectorType, class HashFuncType, class HashPolicyType, class CompType>
class Saf::Algo::Struct::HashTable< KeyType, RecType, KeySelectorType, HashFuncType, HashPolicyType, CompType >

Generic hash table implementation.

This class implements a classic hash table data structure that enables fast insertion, removal and look-up of values. All of these operations on the hash table work generally in ammortized constant time. However, as opposed to a RedBlackTree this behaviour is not guaranteed and the complexity of insert and look-up may be significantly worse (linear) if the supplied hash function and hash policy generate too many collisions.

Internally, the values in a hash table are split into buckets where the bucket associated to a given key is determined using the hash function and the hash policy. Further, all values are stored in one large bidirectional list where the values corresponding to a particular bucket form a consecutive sequence but otherwise the values are not ordered in any way.

Iterator category: Bidirectional.

Remarks:: The selected implementation is not the most memory efficient but allows bidirectional traversal of the data and avoids any compromises in the speed of the methods. Using a singly-linked list would necessary introduce linear behaviour in the Erase() method or in the iterators or may possibly require to store a cached hash value to reduce the performance penalty of determining bucket boundaries.

Template Parameters:

KeyType	Key data type. The keys are used to determine the corresponding bucket using the hash functor and the hash policy.
RecType	The data type of records stored in the table. The `RecType` will be typically a pair containing the key and the mapped value.
KeySelectorType	Unary functor that takes a value of `RecType` and extracts the associated key.
HashFuncType	Unary hash functor that takes values of `KeyType` and returns a value of type Saf::Size.
HashPolicyType	Hash policy object that controls which hashes map to which buckets and when and how to enlarge the bucket count. The policy should never allow zero bucket count.
CompType	A binary equality predicate on `KeyType`. Keys that have the same hash must be equal according to this predicate.

See also:: Collection::HashMap, Collection::HashSet, Hash, HashPolicy, RedBlackTree.

Member Typedef Documentation

template<class KeyType, class RecType, class KeySelectorType, class HashFuncType, class HashPolicyType, class CompType>

typedef Collection::Pair<Iterator,Iterator> Saf::Algo::Struct::HashTable< KeyType, RecType, KeySelectorType, HashFuncType, HashPolicyType, CompType >::BucketType [protected]

Each bucket holds iterators to a front and back element.

template<class KeyType, class RecType, class KeySelectorType, class HashFuncType, class HashPolicyType, class CompType>

typedef Collection::List<RecType>::ConstIterator Saf::Algo::Struct::HashTable< KeyType, RecType, KeySelectorType, HashFuncType, HashPolicyType, CompType >::ConstIterator

Bidirectional non-mutable HashTable iterator.

Reimplemented in Saf::Collection::HashMap< KeyType, ValType, HashFuncType, HashPolicyType, CompType >.

template<class KeyType, class RecType, class KeySelectorType, class HashFuncType, class HashPolicyType, class CompType>

typedef Collection::List<RecType>::Iterator Saf::Algo::Struct::HashTable< KeyType, RecType, KeySelectorType, HashFuncType, HashPolicyType, CompType >::Iterator

Bidirectional mutable HashTable iterator.

Reimplemented in Saf::Collection::HashMap< KeyType, ValType, HashFuncType, HashPolicyType, CompType >.

template<class KeyType, class RecType, class KeySelectorType, class HashFuncType, class HashPolicyType, class CompType>

typedef HashTable<KeyType,RecType,KeySelectorType,HashFuncType,HashPolicyType,CompType> Saf::Algo::Struct::HashTable< KeyType, RecType, KeySelectorType, HashFuncType, HashPolicyType, CompType >::MyType [protected]

Reimplemented in Saf::Collection::HashMap< KeyType, ValType, HashFuncType, HashPolicyType, CompType >, and Saf::Collection::HashSet< ValType, HashFuncType, HashPolicyType, CompType >.

Constructor & Destructor Documentation

template<class KeyType, class RecType, class KeySelectorType, class HashFuncType, class HashPolicyType, class CompType>

Saf::Algo::Struct::HashTable< KeyType, RecType, KeySelectorType, HashFuncType, HashPolicyType, CompType >::HashTable ( Size bucketHint ) [inline, explicit]

Default constructor.

Parameters:

[in] bucketHint Minimum initial bucket count. The actual number of buckets is determined by the internal hash policy.

template<class KeyType, class RecType, class KeySelectorType, class HashFuncType, class HashPolicyType, class CompType>

Saf::Algo::Struct::HashTable< KeyType, RecType, KeySelectorType, HashFuncType, HashPolicyType, CompType >::HashTable ( const MyType & ht ) [inline]

Copy constructor.

template<class KeyType, class RecType, class KeySelectorType, class HashFuncType, class HashPolicyType, class CompType>

Saf::Algo::Struct::HashTable< KeyType, RecType, KeySelectorType, HashFuncType, HashPolicyType, CompType >::~HashTable ( ) [inline]

Destructor.

Member Function Documentation

template<class KeyType, class RecType, class KeySelectorType, class HashFuncType, class HashPolicyType, class CompType>

Iterator Saf::Algo::Struct::HashTable< KeyType, RecType, KeySelectorType, HashFuncType, HashPolicyType, CompType >::Back ( ) [inline]

Iterator to the last element.

template<class KeyType, class RecType, class KeySelectorType, class HashFuncType, class HashPolicyType, class CompType>

ConstIterator Saf::Algo::Struct::HashTable< KeyType, RecType, KeySelectorType, HashFuncType, HashPolicyType, CompType >::Back ( ) const [inline]

Iterator to the last element.

template<class KeyType, class RecType, class KeySelectorType, class HashFuncType, class HashPolicyType, class CompType>

Iterator Saf::Algo::Struct::HashTable< KeyType, RecType, KeySelectorType, HashFuncType, HashPolicyType, CompType >::Begin ( ) [inline]

Iterator to the first element.

template<class KeyType, class RecType, class KeySelectorType, class HashFuncType, class HashPolicyType, class CompType>

ConstIterator Saf::Algo::Struct::HashTable< KeyType, RecType, KeySelectorType, HashFuncType, HashPolicyType, CompType >::Begin ( ) const [inline]

Iterator to the first element.

template<class KeyType, class RecType, class KeySelectorType, class HashFuncType, class HashPolicyType, class CompType>

Iterator Saf::Algo::Struct::HashTable< KeyType, RecType, KeySelectorType, HashFuncType, HashPolicyType, CompType >::BucketBegin ( Size bucket ) [inline]

Get iterator to the first node in a bucket.

The return value is undefined if bucket is greater than or equal to the number of buckets.

Properties:

Worst-case time complexity: $\mathcal{O}(1)$ .

Returns:: End() in case of an empty bucket.

template<class KeyType, class RecType, class KeySelectorType, class HashFuncType, class HashPolicyType, class CompType>

ConstIterator Saf::Algo::Struct::HashTable< KeyType, RecType, KeySelectorType, HashFuncType, HashPolicyType, CompType >::BucketBegin ( Size bucket ) const [inline]

Get iterator to the first node in a bucket.

The return value is undefined if bucket is greater than or equal to the number of buckets.

Properties:

Worst-case time complexity: $\mathcal{O}(1)$ .

Returns:: End() in case of an empty bucket.

template<class KeyType, class RecType, class KeySelectorType, class HashFuncType, class HashPolicyType, class CompType>

Iterator Saf::Algo::Struct::HashTable< KeyType, RecType, KeySelectorType, HashFuncType, HashPolicyType, CompType >::BucketEnd ( Size bucket ) [inline]

Iterator one behind the last element in a bucket.

The return value is undefined if bucket is greater than or equal to the number of buckets.

Properties:

Worst-case time complexity: $\mathcal{O}(1)$ .

Returns:: End() in case of an empty bucket.

template<class KeyType, class RecType, class KeySelectorType, class HashFuncType, class HashPolicyType, class CompType>

ConstIterator Saf::Algo::Struct::HashTable< KeyType, RecType, KeySelectorType, HashFuncType, HashPolicyType, CompType >::BucketEnd ( Size bucket ) const [inline]

Iterator one behind the last element in a bucket.

The return value is undefined if bucket is greater than or equal to the number of buckets.

Properties:

Worst-case time complexity: $\mathcal{O}(1)$ .

Returns:: End() in case of an empty bucket.

template<class KeyType, class RecType, class KeySelectorType, class HashFuncType, class HashPolicyType, class CompType>

void Saf::Algo::Struct::HashTable< KeyType, RecType, KeySelectorType, HashFuncType, HashPolicyType, CompType >::BucketEraseUpdate	(	Iterator	it,
		BucketType &	bucket
	)		`[inline, protected]`

Update bucket front and back iterators on erase operation.

template<class KeyType, class RecType, class KeySelectorType, class HashFuncType, class HashPolicyType, class CompType>

Iterator Saf::Algo::Struct::HashTable< KeyType, RecType, KeySelectorType, HashFuncType, HashPolicyType, CompType >::BucketFind	(	const KeyType &	key,
		const BucketType &	bucket
	)		`[inline, protected]`

Find an element with key key in a given bucket.

template<class KeyType, class RecType, class KeySelectorType, class HashFuncType, class HashPolicyType, class CompType>

ConstIterator Saf::Algo::Struct::HashTable< KeyType, RecType, KeySelectorType, HashFuncType, HashPolicyType, CompType >::BucketFind	(	const KeyType &	key,
		const BucketType &	bucket
	)		const `[inline, protected]`

Find an element with key key in a given bucket.

template<class KeyType, class RecType, class KeySelectorType, class HashFuncType, class HashPolicyType, class CompType>

void Saf::Algo::Struct::HashTable< KeyType, RecType, KeySelectorType, HashFuncType, HashPolicyType, CompType >::BucketInsertUpdate	(	Iterator	it,
		BucketType &	bucket
	)		`[inline, protected]`

Update bucket front and back iterators on insert operation.

We insert always on the beginning of the bucket.

template<class KeyType, class RecType, class KeySelectorType, class HashFuncType, class HashPolicyType, class CompType>

Size Saf::Algo::Struct::HashTable< KeyType, RecType, KeySelectorType, HashFuncType, HashPolicyType, CompType >::Buckets ( ) const [inline]

Get number of buckets.

Properties:

Worst-case time complexity: $\mathcal{O}(1)$ .

template<class KeyType, class RecType, class KeySelectorType, class HashFuncType, class HashPolicyType, class CompType>

bool Saf::Algo::Struct::HashTable< KeyType, RecType, KeySelectorType, HashFuncType, HashPolicyType, CompType >::Contains ( const KeyType & key ) const [inline]

Check if the table contains an element whose key is equal to key.

Properties:

Typical time complexity: $\mathcal{O}(1)$ .
Worst-case time complexity: $\mathcal{O}(\mathrm{Elements()})$ .

template<class KeyType, class RecType, class KeySelectorType, class HashFuncType, class HashPolicyType, class CompType>

Size Saf::Algo::Struct::HashTable< KeyType, RecType, KeySelectorType, HashFuncType, HashPolicyType, CompType >::Elements ( ) const [inline]

Get the number of elements in the table.

Properties:

Worst-case time complexity: $\mathcal{O}(1)$ .

template<class KeyType, class RecType, class KeySelectorType, class HashFuncType, class HashPolicyType, class CompType>

Iterator Saf::Algo::Struct::HashTable< KeyType, RecType, KeySelectorType, HashFuncType, HashPolicyType, CompType >::End ( ) [inline]

Iterator one behind the last element.

template<class KeyType, class RecType, class KeySelectorType, class HashFuncType, class HashPolicyType, class CompType>

ConstIterator Saf::Algo::Struct::HashTable< KeyType, RecType, KeySelectorType, HashFuncType, HashPolicyType, CompType >::End ( ) const [inline]

Iterator one behind the last element.

template<class KeyType, class RecType, class KeySelectorType, class HashFuncType, class HashPolicyType, class CompType>

Iterator Saf::Algo::Struct::HashTable< KeyType, RecType, KeySelectorType, HashFuncType, HashPolicyType, CompType >::Erase ( Iterator it ) [inline]

Remove a given element from the table.

This operation never causes rehashing. If you want to shrink the table you need to explicitly call Rehash().

Properties:

Worst-case time complexity: $\mathcal{O}(1)$ .
Iterator invalidation: Does not invalidate any iterators.

Returns:: Iterator to the successor of the erased element.

template<class KeyType, class RecType, class KeySelectorType, class HashFuncType, class HashPolicyType, class CompType>

Iterator Saf::Algo::Struct::HashTable< KeyType, RecType, KeySelectorType, HashFuncType, HashPolicyType, CompType >::Find ( const KeyType & key ) [inline]

Find an element in the table whose key is equal to key.

Properties:

Typical time complexity: $\mathcal{O}(1)$ .
Worst-case time complexity: $\mathcal{O}(\mathrm{Elements()})$ .

Returns:: Returns End() if there is no such element in the table.

template<class KeyType, class RecType, class KeySelectorType, class HashFuncType, class HashPolicyType, class CompType>

ConstIterator Saf::Algo::Struct::HashTable< KeyType, RecType, KeySelectorType, HashFuncType, HashPolicyType, CompType >::Find ( const KeyType & key ) const [inline]

Find an element in the table whose key is equal to key.

Properties:

Typical time complexity: $\mathcal{O}(1)$ .
Worst-case time complexity: $\mathcal{O}(\mathrm{Elements()})$ .

Returns:: Returns End() if there is no such element in the table.

template<class KeyType, class RecType, class KeySelectorType, class HashFuncType, class HashPolicyType, class CompType>

MyType& Saf::Algo::Struct::HashTable< KeyType, RecType, KeySelectorType, HashFuncType, HashPolicyType, CompType >::Free ( ) [inline]

Free all memory occupied by the table.

The number of buckets is reset to the minimum allowed by the hash policy.

Warning:: The destructor of RecType should never throw. Otherwise the table may end up in an inconsistent state in case of an exception.

template<class KeyType, class RecType, class KeySelectorType, class HashFuncType, class HashPolicyType, class CompType>

Iterator Saf::Algo::Struct::HashTable< KeyType, RecType, KeySelectorType, HashFuncType, HashPolicyType, CompType >::Front ( ) [inline]

Iterator to the first element.

template<class KeyType, class RecType, class KeySelectorType, class HashFuncType, class HashPolicyType, class CompType>

ConstIterator Saf::Algo::Struct::HashTable< KeyType, RecType, KeySelectorType, HashFuncType, HashPolicyType, CompType >::Front ( ) const [inline]

Iterator to the first element.

template<class KeyType, class RecType, class KeySelectorType, class HashFuncType, class HashPolicyType, class CompType>

Collection::Pair<Iterator,bool> Saf::Algo::Struct::HashTable< KeyType, RecType, KeySelectorType, HashFuncType, HashPolicyType, CompType >::Insert ( const RecType & val ) [inline]

Insert a new value into the table.

The first member of the returned pair is either an iterator to the newly inserted element or to an existing element with equivalent key that already appears in the table (the mapped value is not changed in this case). The second member is set to true in the former situation and false in the latter.

The table may be rehashed after an insert operation depending on the internal hash policy.

Properties:

Typical time complexity: $\mathcal{O}(1)$ .
Worst-case time complexity: $\mathcal{O}(\mathrm{Elements()})$ .
Iterator invalidation: Does not invalidate any iterators.

template<class KeyType, class RecType, class KeySelectorType, class HashFuncType, class HashPolicyType, class CompType>

bool Saf::Algo::Struct::HashTable< KeyType, RecType, KeySelectorType, HashFuncType, HashPolicyType, CompType >::IsEmpty ( ) const [inline]

Returns true if the table is empty.

Properties:

Worst-case time complexity: $\mathcal{O}(1)$ .

template<class KeyType, class RecType, class KeySelectorType, class HashFuncType, class HashPolicyType, class CompType>

Size Saf::Algo::Struct::HashTable< KeyType, RecType, KeySelectorType, HashFuncType, HashPolicyType, CompType >::KeyBucketIndex ( const KeyType & key ) const [inline]

Get bucket index for a given key.

template<class KeyType, class RecType, class KeySelectorType, class HashFuncType, class HashPolicyType, class CompType>

MyType& Saf::Algo::Struct::HashTable< KeyType, RecType, KeySelectorType, HashFuncType, HashPolicyType, CompType >::operator= ( const MyType & ht ) [inline]

Assignment operator.

The table is emptied in case of an exception during the copying.

template<class KeyType, class RecType, class KeySelectorType, class HashFuncType, class HashPolicyType, class CompType>

MyType& Saf::Algo::Struct::HashTable< KeyType, RecType, KeySelectorType, HashFuncType, HashPolicyType, CompType >::Rehash ( Size bucketHint ) [inline]

Rehash table.

Properties:

Worst-case time complexity: $\mathcal{O}(\mathrm{Elements()})$ .
Iterator invalidation: Does not invalidate any iterators.

Parameters:

[in] bucketHint Minimum number of buckets. The actual number of buckets allocated is determined by the internal hash policy.

template<class KeyType, class RecType, class KeySelectorType, class HashFuncType, class HashPolicyType, class CompType>

void Saf::Algo::Struct::HashTable< KeyType, RecType, KeySelectorType, HashFuncType, HashPolicyType, CompType >::Reinsert ( Iterator last ) [inline, protected]

Reinsert the range of elements [Begin(), last) into the buckets.

template<class KeyType, class RecType, class KeySelectorType, class HashFuncType, class HashPolicyType, class CompType>

void Saf::Algo::Struct::HashTable< KeyType, RecType, KeySelectorType, HashFuncType, HashPolicyType, CompType >::ResizeTable ( Size buckets ) [inline, protected]

Change the number of buckets.

template<class KeyType, class RecType, class KeySelectorType, class HashFuncType, class HashPolicyType, class CompType>

void Saf::Algo::Struct::HashTable< KeyType, RecType, KeySelectorType, HashFuncType, HashPolicyType, CompType >::SafeResizeBuckets ( Size buckets ) [inline, protected]

Change the number of buckets safely.

In case of out of memory exception the content of the buckets is preserved.

template<class KeyType, class RecType, class KeySelectorType, class HashFuncType, class HashPolicyType, class CompType>

MyType& Saf::Algo::Struct::HashTable< KeyType, RecType, KeySelectorType, HashFuncType, HashPolicyType, CompType >::Swap ( MyType & ht ) [inline]

Swap the content of two hash tables.

Properties:

Worst-case time complexity: $\mathcal{O}(1)$ .

template<class KeyType, class RecType, class KeySelectorType, class HashFuncType, class HashPolicyType, class CompType>

Size Saf::Algo::Struct::HashTable< KeyType, RecType, KeySelectorType, HashFuncType, HashPolicyType, CompType >::ValBucketIndex ( const RecType & val ) const [inline, protected]

Get bucket index for a given record.

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

Saf/Algo/Struct/HashTable.h

Public Types

Public Member Functions

Protected Types

Protected Member Functions

Detailed Description

template<class KeyType, class RecType, class KeySelectorType, class HashFuncType, class HashPolicyType, class CompType> class Saf::Algo::Struct::HashTable< KeyType, RecType, KeySelectorType, HashFuncType, HashPolicyType, CompType >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

template<class KeyType, class RecType, class KeySelectorType, class HashFuncType, class HashPolicyType, class CompType>
class Saf::Algo::Struct::HashTable< KeyType, RecType, KeySelectorType, HashFuncType, HashPolicyType, CompType >