This class implements an association between keys and values. More...

#include <HashMap.h>

Classes
struct	Entry
	Type definition for each cells in the bucket chain. More...

class	iterator
	Iterator support for class HashMap. More...

Public Member Functions
	HashMap ()

virtual	~HashMap ()

	HashMap (const HashMap &src)
	This copy constructor is to make a deep copy of HashMap. More...

HashMap &	operator= (const HashMap &src)
	This operator= are defined assign from one map to another. More...

void	clear ()
	Removes all entries from this map. More...

int	size () const

bool	isEmpty () const

void	put (const KeyType &key, const ValueType &value)
	Associates `key` with `value` in this map. More...

ValueType	get (const KeyType &key) const

bool	containsKey (const KeyType &key) const

void	remove (const KeyType &key)
	removes any entry for `key` from this map. More...

ValueType &	operator[] (const KeyType &key)
	Selects the value associated with `key`. More...

ValueType	operator[] (const KeyType &key) const

iterator	begin () const

iterator	end () const

Private Member Functions
void	createBuckets (int nBuckets)
	Creates vector of buckets to have nBuckets entries, each NULL. More...

void	deleteBuckets (std::vector< Entry * > &buckets)
	Deletes all the cells in the linked lists contained in vector. More...

void	expandAndRehash ()
	Increases the buckets in the map and then rehashes all existing entries. More...

Entry *	findEntry (int bucket, const KeyType &key) const
	Finds a cell in the chain for the specified bucket that matches key. More...

Entry *	findEntry (int bucket, const KeyType &key, Entry *&parent) const

void	deepCopy (const HashMap &src)
	Creates deep copy of src HashMap. More...

Private Attributes
std::vector< Entry * >	buckets
	Vector of pointer to Entry. More...

int	nBuckets
	Total number of buckets. More...

int	numEntries
	Total number of entries. More...

Detailed Description

template<typename KeyType, typename ValueType>
class HashMap< KeyType, ValueType >

This class implements an association between keys and values.

It stores a set of key-value pairs and uses a hash table as its underlying representation.

Definition at line 14 of file HashMap.h.

Constructor & Destructor Documentation

◆ HashMap() [1/2]

template<typename KeyType , typename ValueType >

HashMap< KeyType, ValueType >::HashMap

Definition at line 258 of file HashMap.h.

◆ ~HashMap()

template<typename KeyType , typename ValueType >

HashMap< KeyType, ValueType >::~HashMap

virtual

Definition at line 263 of file HashMap.h.

◆ HashMap() [2/2]

template<typename KeyType , typename ValueType >

HashMap< KeyType, ValueType >::HashMap ( const HashMap< KeyType, ValueType > & src )

This copy constructor is to make a deep copy of HashMap.

Definition at line 268 of file HashMap.h.

Member Function Documentation

◆ begin()

template<typename KeyType , typename ValueType >

iterator HashMap< KeyType, ValueType >::begin ( ) const

inline

Definition at line 182 of file HashMap.h.

◆ clear()

template<typename KeyType , typename ValueType >

void HashMap< KeyType, ValueType >::clear

Removes all entries from this map.

Definition at line 326 of file HashMap.h.

◆ containsKey()

template<typename KeyType , typename ValueType >

bool HashMap< KeyType, ValueType >::containsKey ( const KeyType & key ) const

Returns: true if there is an entry for key in this map.

Definition at line 304 of file HashMap.h.

◆ createBuckets()

template<typename KeyType , typename ValueType >

void HashMap< KeyType, ValueType >::createBuckets ( int nBuckets )

private

Creates vector of buckets to have nBuckets entries, each NULL.

Definition at line 196 of file HashMap.h.

◆ deepCopy()

template<typename KeyType , typename ValueType >

void HashMap< KeyType, ValueType >::deepCopy ( const HashMap< KeyType, ValueType > & src )

private

Creates deep copy of src HashMap.

Definition at line 248 of file HashMap.h.

◆ deleteBuckets()

template<typename KeyType , typename ValueType >

void HashMap< KeyType, ValueType >::deleteBuckets ( std::vector< Entry * > & buckets )

private

Deletes all the cells in the linked lists contained in vector.

Definition at line 204 of file HashMap.h.

◆ end()

template<typename KeyType , typename ValueType >

iterator HashMap< KeyType, ValueType >::end ( ) const

inline

Definition at line 186 of file HashMap.h.

◆ expandAndRehash()

template<typename KeyType , typename ValueType >

void HashMap< KeyType, ValueType >::expandAndRehash

private

Increases the buckets in the map and then rehashes all existing entries.

This operation is used when the load factor (i.e. the number of cells per bucket) has increased enough such that the get() and put() operation are no longer of complexity of O(1).

Definition at line 217 of file HashMap.h.

◆ findEntry() [1/2]

template<typename KeyType , typename ValueType >

HashMap< KeyType, ValueType >::Entry * HashMap< KeyType, ValueType >::findEntry	(	int	bucket,
		const KeyType &	key
	)		const

private

Finds a cell in the chain for the specified bucket that matches key.

Returns: pointer to the cell containing the matching key or NULL.

Definition at line 230 of file HashMap.h.

◆ findEntry() [2/2]

template<typename KeyType , typename ValueType >

HashMap< KeyType, ValueType >::Entry * HashMap< KeyType, ValueType >::findEntry	(	int	bucket,
		const KeyType &	key,
		Entry *&	parent
	)		const

private

Parameters

parent cell preceding the matching cell.

See also: remove()

Definition at line 237 of file HashMap.h.

◆ get()

template<typename KeyType , typename ValueType >

ValueType HashMap< KeyType, ValueType >::get ( const KeyType & key ) const

Returns: the value associated with key in this map.; the default value for ValueType, if key is not found

Definition at line 297 of file HashMap.h.

◆ isEmpty()

template<typename KeyType , typename ValueType >

bool HashMap< KeyType, ValueType >::isEmpty

Returns: true if this map contains no entries.

Definition at line 287 of file HashMap.h.

◆ operator=()

template<typename KeyType , typename ValueType >

HashMap< KeyType, ValueType > & HashMap< KeyType, ValueType >::operator= ( const HashMap< KeyType, ValueType > & src )

This operator= are defined assign from one map to another.

Definition at line 273 of file HashMap.h.

◆ operator[]() [1/2]

template<typename KeyType , typename ValueType >

ValueType & HashMap< KeyType, ValueType >::operator[] ( const KeyType & key )

Selects the value associated with key.

Returns: a reference to its associated value.

If key is not present in the map, a new entry is created whose value is set to the default for the value type.

Definition at line 332 of file HashMap.h.

◆ operator[]() [2/2]

template<typename KeyType , typename ValueType >

ValueType HashMap< KeyType, ValueType >::operator[] ( const KeyType & key ) const

Definition at line 351 of file HashMap.h.

◆ put()

template<typename KeyType , typename ValueType >

void HashMap< KeyType, ValueType >::put	(	const KeyType &	key,
		const ValueType &	value
	)

Associates key with value in this map.

Definition at line 292 of file HashMap.h.

◆ remove()

template<typename KeyType , typename ValueType >

void HashMap< KeyType, ValueType >::remove ( const KeyType & key )

removes any entry for key from this map.

If the given key is not found, has no effect.

Definition at line 309 of file HashMap.h.

◆ size()

template<typename KeyType , typename ValueType >

int HashMap< KeyType, ValueType >::size

Returns: the number of entries in this map.

Definition at line 282 of file HashMap.h.

Member Data Documentation

◆ buckets

template<typename KeyType , typename ValueType >

std::vector<Entry*> HashMap< KeyType, ValueType >::buckets

private

Vector of pointer to Entry.

Definition at line 24 of file HashMap.h.

◆ nBuckets

template<typename KeyType , typename ValueType >

int HashMap< KeyType, ValueType >::nBuckets

private

Total number of buckets.

Definition at line 25 of file HashMap.h.

◆ numEntries

template<typename KeyType , typename ValueType >

int HashMap< KeyType, ValueType >::numEntries

private

Total number of entries.

Definition at line 26 of file HashMap.h.

Classes

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

template<typename KeyType, typename ValueType> class HashMap< KeyType, ValueType >

Constructor & Destructor Documentation

◆ HashMap() [1/2]

◆ ~HashMap()

◆ HashMap() [2/2]

Member Function Documentation

◆ begin()

◆ clear()

◆ containsKey()

◆ createBuckets()

◆ deepCopy()

◆ deleteBuckets()

◆ end()

◆ expandAndRehash()

◆ findEntry() [1/2]

◆ findEntry() [2/2]

◆ get()

◆ isEmpty()

◆ operator=()

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ put()

◆ remove()

◆ size()

Member Data Documentation

◆ buckets

◆ nBuckets

◆ numEntries

template<typename KeyType, typename ValueType>
class HashMap< KeyType, ValueType >