PLCore::HashMap< KeyType, ValueType, Hasher, Comparer, Grower > Class Template Reference

Hash map template. More...

#include <HashMap.h>

Inheritance diagram for PLCore::HashMap< KeyType, ValueType, Hasher, Comparer, Grower >:

List of all members.

Public Member Functions
	HashMap (uint32 nNumOfSlots=199)
	Constructor.
	HashMap (const HashMap< KeyType, ValueType, Hasher, Comparer, Grower > &cSource)
	Copy constructor.
virtual	~HashMap ()
	Destructor.
Map< KeyType, ValueType > &	operator= (const HashMap< KeyType, ValueType, Hasher, Comparer, Grower > &cSource)
	Copy operator.
uint32	GetNumOfSlots () const
	Returns the current number of slots.
void	GetStatistics (uint32 &nNumOfCollisions, uint32 &nNumOfFreeSlotsLists) const
	Returns some statistics.
virtual Iterator< ValueType >	GetIterator (uint32 nIndex=0) const override
	Returns an iterator operating on the derived data structure.
virtual ConstIterator< ValueType >	GetConstIterator (uint32 nIndex=0) const override
	Returns a constant iterator operating on the derived data structure.
virtual Iterator< ValueType >	GetEndIterator () const override
	Returns an iterator operating on the derived data structure and starting at the end.
virtual ConstIterator< ValueType >	GetConstEndIterator () const override
	Returns a constant iterator operating on the derived data structure and starting at the end.
virtual void	Clear () override
	Clears the map.
virtual bool	IsEmpty () const override
	Checks whether the map is complete empty.
virtual uint32	GetNumOfElements () const override
	Returns the number of elements/entries.
virtual bool	Add (const KeyType &Key, const ValueType &Value) override
	Adds/puts a new element to the map.
virtual bool	Replace (const KeyType &Key, const ValueType &NewValue) override
	Replaces the value of a map element.
virtual bool	Set (const KeyType &Key, const ValueType &Value) override
	Sets (adds or replaces) the value of a map element.
virtual bool	Remove (const KeyType &Key) override
	Removes an element from the map.
virtual uint32	RemoveValue (const ValueType &Value) override
	Removes all elements with a certain value from the map.
virtual const ValueType &	Get (const KeyType &Key) const override
	Returns the value of a given key.
virtual ValueType &	Get (const KeyType &Key) override
	Returns the value of a given key.
virtual Iterator< KeyType >	GetKeyIterator (uint32 nIndex=0) const override
	Returns a key iterator operating on the derived data structure.
virtual ConstIterator< KeyType >	GetConstKeyIterator (uint32 nIndex=0) const override
	Returns a constant key iterator operating on the derived data structure.
virtual Iterator< KeyType >	GetEndKeyIterator () const override
	Returns a key iterator operating on the derived data structure and starting at the end.
virtual ConstIterator< KeyType >	GetConstEndKeyIterator () const override
	Returns a constant key iterator operating on the derived data structure and starting at the end.

---

Detailed Description

template<class KeyType, class ValueType, class Hasher = HashFunction, class Comparer = CompareFunction, class Grower = GrowFunction>
class PLCore::HashMap< KeyType, ValueType, Hasher, Comparer, Grower >

Hash map template.

Remarks:

The hash map is using a hashing function to calculate indices to elements. If there are too many elements in the map which will produce more collisions, a grow function decides when to grow the hash map and how much. There are some ways to avoid collisions: 1. The hash map size should be a prime number: It can be mathematically proven that the probability of collisions is less if we let the hash function perform % on a prime number rather than on a non-prime number. 2. Spreading the values: For example, let the hash function be smart enough to distribute its return values as evenly as possible. How to determine the best algorithm for the hash function depends on the hash map usage. 3. Increasing the array's size: The more "free slots" in the hash map, the less probability of collisions. So, to avoid collisions, use a clever grow function. But try to avoid to grow the hash map frequently because that's not performant.

Note:

• Collisions are solved by using a linked list per slot

---

Constructor & Destructor Documentation

template<class KeyType , class ValueType , class Hasher , class Comparer , class Grower >

PLCore::HashMap< KeyType, ValueType, Hasher, Comparer, Grower >::HashMap

(

uint32

nNumOfSlots = 199

)

Constructor.

Parameters:

[in]

nNumOfSlots

Initial number of slots (must be >= 1, should be a prime number)

template<class KeyType, class ValueType, class Hasher, class Comparer, class Grower>

PLCore::HashMap< KeyType, ValueType, Hasher, Comparer, Grower >::HashMap

(

const HashMap< KeyType, ValueType, Hasher, Comparer, Grower > &

cSource

)

Copy constructor.

Parameters:

[in]

cSource

Source to copy from

template<class KeyType , class ValueType , class Hasher , class Comparer , class Grower >

PLCore::HashMap< KeyType, ValueType, Hasher, Comparer, Grower >::~HashMap

(

)

[virtual]

Destructor.

---

Member Function Documentation

template<class KeyType, class ValueType, class Hasher, class Comparer, class Grower>

Map< KeyType, ValueType > & PLCore::HashMap< KeyType, ValueType, Hasher, Comparer, Grower >::operator=

(

const HashMap< KeyType, ValueType, Hasher, Comparer, Grower > &

cSource

)

Copy operator.

Parameters:

[in]

cSource

'HashMap' to copy from

Returns:

Reference to this instance

template<class KeyType , class ValueType , class Hasher , class Comparer , class Grower >

uint32 PLCore::HashMap< KeyType, ValueType, Hasher, Comparer, Grower >::GetNumOfSlots

(

)

const

Returns the current number of slots.

Returns:

Current number of slots

template<class KeyType , class ValueType , class Hasher , class Comparer , class Grower >

void PLCore::HashMap< KeyType, ValueType, Hasher, Comparer, Grower >::GetStatistics	(	uint32 &	nNumOfCollisions,
		uint32 &	nNumOfFreeSlotsLists
	)		const

Returns some statistics.

Parameters:

[out]	nNumOfCollisions	Will receive the number of collisions
[out]	nNumOfFreeSlotsLists	Will receive the number of free slots lists

Note:

• If there are a lot of collisions and also a lot of free slots lists you should try to use a more efficient hash function

template<class KeyType , class ValueType , class Hasher , class Comparer , class Grower >

Iterator< ValueType > PLCore::HashMap< KeyType, ValueType, Hasher, Comparer, Grower >::GetIterator

(

uint32

nIndex = 0

)

const [override, virtual]

Returns an iterator operating on the derived data structure.

Parameters:

[in]

nIndex

Start index, if >= 'total number of elements' the index is set to the last valid index

Returns:

Iterator operating on the derived

Implements PLCore::Iterable< ValueType >.

template<class KeyType , class ValueType , class Hasher , class Comparer , class Grower >

ConstIterator< ValueType > PLCore::HashMap< KeyType, ValueType, Hasher, Comparer, Grower >::GetConstIterator

(

uint32

nIndex = 0

)

const [override, virtual]

Returns a constant iterator operating on the derived data structure.

Parameters:

[in]

nIndex

Start index, if >= 'total number of elements' the index is set to the last valid index

Returns:

Constant iterator operating on the derived

Implements PLCore::Iterable< ValueType >.

template<class KeyType , class ValueType , class Hasher , class Comparer , class Grower >

Iterator< ValueType > PLCore::HashMap< KeyType, ValueType, Hasher, Comparer, Grower >::GetEndIterator

(

)

const [override, virtual]

Returns an iterator operating on the derived data structure and starting at the end.

Returns:

Iterator operating on the derived,

Remarks:

Use this function to get an iterator if you want to iterate in reversed order starting at the end last element.

Implements PLCore::Iterable< ValueType >.

template<class KeyType , class ValueType , class Hasher , class Comparer , class Grower >

ConstIterator< ValueType > PLCore::HashMap< KeyType, ValueType, Hasher, Comparer, Grower >::GetConstEndIterator

(

)

const [override, virtual]

Returns a constant iterator operating on the derived data structure and starting at the end.

Returns:

Constant iterator operating on the derived,

Remarks:

Use this function to get a constant iterator if you want to iterate in reversed order starting at the end last element.

Implements PLCore::Iterable< ValueType >.

template<class KeyType , class ValueType , class Hasher , class Comparer , class Grower >

void PLCore::HashMap< KeyType, ValueType, Hasher, Comparer, Grower >::Clear

(

)

[override, virtual]

Clears the map.

Implements PLCore::Map< KeyType, ValueType >.

template<class KeyType , class ValueType , class Hasher , class Comparer , class Grower >

bool PLCore::HashMap< KeyType, ValueType, Hasher, Comparer, Grower >::IsEmpty

(

)

const [override, virtual]

Checks whether the map is complete empty.

Returns:

'true' if the map is empty, else 'false'

Implements PLCore::Map< KeyType, ValueType >.

template<class KeyType , class ValueType , class Hasher , class Comparer , class Grower >

uint32 PLCore::HashMap< KeyType, ValueType, Hasher, Comparer, Grower >::GetNumOfElements

(

)

const [override, virtual]

Returns the number of elements/entries.

Returns:

Number of container elements/entries

Implements PLCore::Map< KeyType, ValueType >.

template<class KeyType, class ValueType, class Hasher , class Comparer , class Grower >

bool PLCore::HashMap< KeyType, ValueType, Hasher, Comparer, Grower >::Add	(	const KeyType &	Key,
		const ValueType &	Value
	)		[override, virtual]

Adds/puts a new element to the map.

Parameters:

[in]	Key	The key of the new element
[in]	Value	The value of the new element

Returns:

'true' if all went fine, else 'false'

Note:

• You have to check by yourself whether there's already such a key within the map

See also:

• Set()

Implements PLCore::Map< KeyType, ValueType >.

template<class KeyType, class ValueType, class Hasher , class Comparer , class Grower >

bool PLCore::HashMap< KeyType, ValueType, Hasher, Comparer, Grower >::Replace	(	const KeyType &	Key,
		const ValueType &	NewValue
	)		[override, virtual]

Replaces the value of a map element.

Parameters:

[in]	Key	The key of the element
[in]	NewValue	The new value of the element

Returns:

'true' if all went fine, else 'false' (key not found?)

See also:

• Set()

Implements PLCore::Map< KeyType, ValueType >.

template<class KeyType, class ValueType, class Hasher , class Comparer , class Grower >

bool PLCore::HashMap< KeyType, ValueType, Hasher, Comparer, Grower >::Set	(	const KeyType &	Key,
		const ValueType &	Value
	)		[override, virtual]

Sets (adds or replaces) the value of a map element.

Parameters:

[in]	Key	The key of the element
[in]	Value	The set value of the element

Returns:

'false' if a new element was added, 'true' if the value was replaced

Remarks:

This function is a combination of the add and replace function and 'just' assigns a value to a given key without taking care of whether or not there's already an element with the given key inside the map.

See also:

• Add()
• Replace()

Implements PLCore::Map< KeyType, ValueType >.

template<class KeyType, class ValueType , class Hasher , class Comparer , class Grower >

bool PLCore::HashMap< KeyType, ValueType, Hasher, Comparer, Grower >::Remove

(

const KeyType &

Key

)

[override, virtual]

Removes an element from the map.

Parameters:

[in]

Key

Key of the element which should be removed

Returns:

'true' if all went fine, else 'false'

Implements PLCore::Map< KeyType, ValueType >.

template<class KeyType , class ValueType, class Hasher , class Comparer , class Grower >

uint32 PLCore::HashMap< KeyType, ValueType, Hasher, Comparer, Grower >::RemoveValue

(

const ValueType &

Value

)

[override, virtual]

Removes all elements with a certain value from the map.

Parameters:

[in]

Value

Value to look for

Returns:

Number of removed elements

Note:

• For performance reasons, try to use the Remove(<Key>) function whenever possible!

Implements PLCore::Map< KeyType, ValueType >.

template<class KeyType, class ValueType , class Hasher , class Comparer , class Grower >

const ValueType & PLCore::HashMap< KeyType, ValueType, Hasher, Comparer, Grower >::Get

(

const KeyType &

Key

)

const [override, virtual]

Returns the value of a given key.

Parameters:

[in]

Key

Key to use

Returns:

Reference of the value of the given key, reference to the 'Null'-object on error

Implements PLCore::Map< KeyType, ValueType >.

template<class KeyType, class ValueType , class Hasher , class Comparer , class Grower >

ValueType & PLCore::HashMap< KeyType, ValueType, Hasher, Comparer, Grower >::Get

(

const KeyType &

Key

)

[override, virtual]

Returns the value of a given key.

Parameters:

[in]

Key

Key to use

Returns:

Reference of the value of the given key, reference to the 'Null'-object on error

Implements PLCore::Map< KeyType, ValueType >.

template<class KeyType , class ValueType , class Hasher , class Comparer , class Grower >

Iterator< KeyType > PLCore::HashMap< KeyType, ValueType, Hasher, Comparer, Grower >::GetKeyIterator

(

uint32

nIndex = 0

)

const [override, virtual]

Returns a key iterator operating on the derived data structure.

Parameters:

[in]

nIndex

Start index, if >= 'total number of elements' the index is set to the last valid index

Returns:

Key iterator operating on the derived

Implements PLCore::Map< KeyType, ValueType >.

template<class KeyType , class ValueType , class Hasher , class Comparer , class Grower >

ConstIterator< KeyType > PLCore::HashMap< KeyType, ValueType, Hasher, Comparer, Grower >::GetConstKeyIterator

(

uint32

nIndex = 0

)

const [override, virtual]

Returns a constant key iterator operating on the derived data structure.

Parameters:

[in]

nIndex

Start index, if >= 'total number of elements' the index is set to the last valid index

Returns:

Constant key iterator operating on the derived

Implements PLCore::Map< KeyType, ValueType >.

template<class KeyType , class ValueType , class Hasher , class Comparer , class Grower >

Iterator< KeyType > PLCore::HashMap< KeyType, ValueType, Hasher, Comparer, Grower >::GetEndKeyIterator

(

)

const [override, virtual]

Returns a key iterator operating on the derived data structure and starting at the end.

Returns:

Key iterator operating on the derived,

Remarks:

Use this function to get a key iterator if you want to iterate in reversed order starting at the end last element.

Implements PLCore::Map< KeyType, ValueType >.

template<class KeyType , class ValueType , class Hasher , class Comparer , class Grower >

ConstIterator< KeyType > PLCore::HashMap< KeyType, ValueType, Hasher, Comparer, Grower >::GetConstEndKeyIterator

(

)

const [override, virtual]

Returns a constant key iterator operating on the derived data structure and starting at the end.

Returns:

Constant key iterator operating on the derived,

Remarks:

Use this function to get a constant key iterator if you want to iterate in reversed order starting at the end last element.

Implements PLCore::Map< KeyType, ValueType >.

---

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

• HashMap.h
• HashMap.inl