Associative Array with a hash table implementation. More...

#include <HashMap.h>

Public Types
enum	{ HashMapVersion }

typedef uInt(*	Func )(const key &)
	Signature of the hash functions. More...

Public Member Functions
	HashMap (const HashMap &)
	Copy constructor with copy semantics. More...

	HashMap (const val &dflt=defaultHashValue((const val *)(0)), uInt size=uInt(defaultSize_), Func newfunc=hashFunc, float maxlf=float(defaultMaxLoad_))
	Default constructor (and variation) which allows for specifying: More...

	HashMap (const val &dflt, uInt size, const HashClass< key > &newfunc, float maxlf=float(defaultMaxLoad_))

	used_ (uInt(defaultSize()))

	filled_ (0)

	defs_ (0)

	maxLoad_ (maxlf)

	blk (uInt(defaultSize()), static_cast< List< OrderedPair< key, val > > * >(0))

	func (newfunc)

	hashClass (0)

	dfltVal (dflt)

	HashMap (const val &dflt, const HashClass< key > &newfunc, float maxlf=float(defaultMaxLoad_))

HashMap< key, val > &	operator= (const HashMap< key, val > &)
	This copies the right hand side of the assignment. More...

const val &	operator() (const key &ky) const
	Retrieve values from the map, possibly for later assignment. More...

val &	operator() (const key &ky)

val &	define (const key &k, const val &v)
	Define a complete mapping. More...

void	remove (const key &k)
	Remove a user defined mapping from `k` to a value. More...

Bool	isDefined (const key &k) const
	Check to see if a user defined mapping exists for `k`. More...

const val &	defaultVal () const
	Retrieve the default value. More...

val &	defaultVal ()

void	clear ()
	Remove all user defined mapping. More...

float	maxLoad () const
	Get or set the maximum load factor. More...

void	setMaxLoad (float new_max)

uInt	totalBuckets () const
	Total number of buckets, i.e. More...

uInt	availableBuckets () const
	Number of buckets available, i.e. More...

uInt	usedBuckets () const
	Number of buckets currently populated by a bucket list. More...

uInt	allocBuckets () const
	Number of buckets which have been allocated, i.e. More...

uInt	ndefined () const
	Number of mappings which have been defined by the user. More...

float	loading () const
	Current hash table loading factor. More...

Bool	empty () const
	Have any mappings been defined by the user. More...

Block< uInt >	distribution () const
	This returns a Block which has the number of elements in each bucket of the table. More...

uInt	totalSize () const
	Total size of this HashMap minus dynamically allocated memory for key or val. More...

virtual	~HashMap ()
	dtor More...

Static Public Member Functions
static float	defaultMaxLoad ()

static uInt	defaultSize ()

Public Attributes
	__pad0__: total_(uInt(defaultSize()))
	Constructor which allows for specifying: More...

Protected Member Functions
uInt	hash (const key &k) const
	Call the hash function. More...

void	freeTable ()
	delete the contents of the hash table More...

uInt	enlarge ()
	enlarge the hash table. More...

uInt	populate (uInt to)
	populate bucket "to". More...

Private Types
enum	HashMap_Constants { defaultSize_, defaultMaxLoad_ }

Private Attributes
uInt	total_
	Total Slots. More...

uInt	used_
	Slots Being Used. More...

uInt	filled_
	Slots with At Least One Value in the Bucket. More...

uInt	defs_
	Number of Defined Mappings. More...

float	maxLoad_
	Maximum load. More...

PtrBlock< List< OrderedPair < key, val > > * >	blk

Func	func

HashClass< key > *	hashClass

val	dfltVal

Friends
class	ConstHashMapIter< key, val >

Detailed Description

template<class key, class val>
class casacore::HashMap< key, val >

Associative Array with a hash table implementation.

Intended use:

Public interface

Review Status

Date Reviewed:: yyyy/mm/dd

Prerequisite

basic concepts behind hash tables

Etymology

This is an associative array, also known as a map, and it is implemented using a hash table, so it is called HashMap.

Synopsis

This class is an implementation of an associative array. This is a common data structure which associates a key of one type with a value of the same or different type. Essentially it is an (unordered) array which is indexed by an arbitrary type of index, e.g. strings.

This class has two template type parameters. The first is the type of the key and the second is the type of the value. Thus the associative array is a mapping from the domain, any valid object of the key type, to the range, any valid object of the value type. This is a complete map which means that every element in the domain maps to one and only one element in the range. Those elements which have not been set by the user of this class map to a default value which is set at construction time.

One of the important features of this class which must be understood is the load factor. This factor indicates the average number of items in the buckets of the hash table which are currently in use. The goal is to have the hash function greatly reduce the number of item which must be searched, i.e. to have a limited number of items in each bucket. The load factor determines this. Thus a load factor of 1000 or 0 is a poor choice. The default load factor is 4 which should generally be fine. The load factor is set with setMaxLoad() and retrieved with maxLoad().

For this class to be used, three things must be defined:

a specialization of the hash() templated function for the key type or a class derived from HashClass<key>. Either of which can be used to implement the hash function for a particular type.
an equality operator ('==') for the key
a default constructor or a specialization of defaultHashValue() for the key type

The implementation of this hash map is derived from work on a proposed addition to the Standard Template Library by Javier Barreiro, Robert Fraley and David R. Musser. The information which is available includes:

each of these sources was utilized in the development of this set of classes, and in particular, the preliminary implementation was the source for the hashing algorithm used in this set of classes.

Example

#include <casacore/casa/Containers/HashMap.h>
#include <casacore/casa/BasicSL/String.h>
#include <casacore/casa/iostream.h>
main() {
HashMap<String,Int> hash;
hash("one") = 1;       // sets the value of key "one" to "1"
hash.define("two",2);      // defines a mapping from key "two" to "2"
hash("three") = 3;
hash.define("four",4);
hash("five") = 5;
hash.define("six",6);
HashMapIter<String,Int> iter(hash);
for (iter.toStart(); ! iter.atEnd(); iter++)
cout << iter.getVal() << ": " << iter.getKey() << endl;
cout << endl << "Diagnostics" << endl << 
"========================" << endl;
cout << "number defined:    " << hash.ndefined() << endl;
cout << "buckets used:      " << hash.usedBuckets() << endl;
cout << "buckets available: " << hash.availableBuckets() << endl;
cout << "buckets allocated: " << hash.allocBuckets() << endl;
cout << "loading:           " << hash.loading() << endl;
cout << "size (in bytes):   " << hash.totalSize() << endl;
}

Motivation

There are a couple of reasons why this class was built:

use of a hash table can be more efficient
there are a couple of Map classes currently:
- OrderedMap
- SimpleOrderedMap
OrderedMap is derived from a map base class, Map while SimpleOrderedMap is not. This collection of classes has resulted in confusion for the users. It is hoped that this class can in time replace these other "map" classes by satisfying the performance demands of SimpleOrderedMap while still meeting the constraints of the other map classes.

Template Type Argument Requirements (key)

equality operator (operator==)
function hashFunc() or HashClass derived class provided
default constructor or defaultHashValue() specialization provided or default value provided at time of construction

Template Type Argument Requirements (val)

copy constructor

Thrown Exceptions

AipsError

To Do

add this feature
fix this bug
start discussion of this possible extension

Definition at line 301 of file HashMap.h.

Member Typedef Documentation

template<class key, class val>

typedef uInt(* casacore::HashMap< key, val >::Func)(const key &)

Signature of the hash functions.

Definition at line 310 of file HashMap.h.

Member Enumeration Documentation

template<class key, class val>

anonymous enum

Enumerator
HashMapVersion

Definition at line 484 of file HashMap.h.

template<class key, class val>

enum casacore::HashMap::HashMap_Constants

private

Enumerator
defaultSize_
defaultMaxLoad_

Definition at line 304 of file HashMap.h.

Constructor & Destructor Documentation

template<class key, class val>

casacore::HashMap< key, val >::HashMap ( const HashMap< key, val > & )

Copy constructor with copy semantics.

template<class key, class val>

casacore::HashMap< key, val >::HashMap	(	const val &	dflt = `defaultHashValue((const val*)(0))`,
		uInt	size = `uInt(defaultSize_)`,
		Func	newfunc = `hashFunc`,
		float	maxlf = `float(defaultMaxLoad_)`
	)

inline

Default constructor (and variation) which allows for specifying:

a default value, dflt
the initial number of buckets, size
the hash function, newfunc
the maximum load factor, maxlf

This is a pair because the hash function can either be a simple function or a class derived from HashClass.

Definition at line 330 of file HashMap.h.

template<class key, class val>

casacore::HashMap< key, val >::HashMap	(	const val &	dflt,
		uInt	size,
		const HashClass< key > &	newfunc,
		float	maxlf = `float(defaultMaxLoad_)`
	)

inline

Definition at line 345 of file HashMap.h.

template<class key, class val>

casacore::HashMap< key, val >::HashMap	(	const val &	dflt,
		const HashClass< key > &	newfunc,
		float	maxlf = `float(defaultMaxLoad_)`
	)

inline

Definition at line 382 of file HashMap.h.

template<class key, class val>

virtual casacore::HashMap< key, val >::~HashMap ( )

virtual

dtor

Member Function Documentation

template<class key, class val>

uInt casacore::HashMap< key, val >::allocBuckets ( ) const

inline

Number of buckets which have been allocated, i.e.

the total number which have currently been allocated. This is the number of buckets created. It may be bigger than totalBuckets() because more memory can be allocated than the hashing mechanism needs.

Definition at line 463 of file HashMap.h.

References casacore::HashMap< key, val >::blk.

template<class key, class val>

uInt casacore::HashMap< key, val >::availableBuckets ( ) const

inline

Number of buckets available, i.e.

those which the hashing mechanism allows itself to use. This may be smaller than totalBuckets() because the hashing mechanism can restrict itself to some subset of the buckets available.

Definition at line 455 of file HashMap.h.

References casacore::HashMap< key, val >::used_.

Referenced by casacore::HashMap< key, val >::hash(), and casacore::HashMap< key, val >::loading().

template<class key, class val>

casacore::HashMap< key, val >::blk	(	uInt(defaultSize())	,
		static_cast< List< OrderedPair< key, val > > * >	0
	)

template<class key, class val>

void casacore::HashMap< key, val >::clear ( )

inline

Remove all user defined mapping.

Definition at line 434 of file HashMap.h.

References casacore::HashMap< key, val >::freeTable().

template<class key, class val>

static float casacore::HashMap< key, val >::defaultMaxLoad ( )

inlinestatic

Definition at line 306 of file HashMap.h.

References casacore::HashMap< key, val >::defaultMaxLoad_.

template<class key, class val>

static uInt casacore::HashMap< key, val >::defaultSize ( )

inlinestatic

Definition at line 307 of file HashMap.h.

References casacore::HashMap< key, val >::defaultSize_.

template<class key, class val>

const val& casacore::HashMap< key, val >::defaultVal ( ) const

inline

Retrieve the default value.

Definition at line 427 of file HashMap.h.

References casacore::HashMap< key, val >::dfltVal.

template<class key, class val>

val& casacore::HashMap< key, val >::defaultVal ( )

inline

Definition at line 428 of file HashMap.h.

References casacore::HashMap< key, val >::dfltVal.

template<class key, class val>

val& casacore::HashMap< key, val >::define	(	const key &	k,
		const val &	v
	)

Define a complete mapping.

template<class key, class val>

casacore::HashMap< key, val >::defs_ ( 0 )

template<class key, class val>

casacore::HashMap< key, val >::dfltVal ( dflt )

inline

Definition at line 379 of file HashMap.h.

template<class key, class val>

Block<uInt> casacore::HashMap< key, val >::distribution ( ) const

This returns a Block which has the number of elements in each bucket of the table.

template<class key, class val>

Bool casacore::HashMap< key, val >::empty ( ) const

inline

Have any mappings been defined by the user.

Definition at line 471 of file HashMap.h.

References casacore::False, casacore::HashMap< key, val >::ndefined(), and casacore::True.

template<class key, class val>

uInt casacore::HashMap< key, val >::enlarge ( )

protected

enlarge the hash table.

Returns the bucket which is being moved...

template<class key, class val>

casacore::HashMap< key, val >::filled_ ( 0 )

template<class key, class val>

void casacore::HashMap< key, val >::freeTable ( )

protected

delete the contents of the hash table

Referenced by casacore::HashMap< key, val >::clear().

template<class key, class val>

casacore::HashMap< key, val >::func ( newfunc )

template<class key, class val>

uInt casacore::HashMap< key, val >::hash ( const key & k ) const

inlineprotected

Call the hash function.

Definition at line 488 of file HashMap.h.

References casacore::HashMap< key, val >::availableBuckets(), casacore::HashMap< key, val >::func, casacore::HashMap< key, val >::hashClass, and casacore::HashMap< key, val >::totalBuckets().

template<class key, class val>

casacore::HashMap< key, val >::hashClass ( 0 )

template<class key, class val>

Bool casacore::HashMap< key, val >::isDefined ( const key & k ) const

Check to see if a user defined mapping exists for k.

This does not modify the map.

template<class key, class val>

float casacore::HashMap< key, val >::loading ( ) const

inline

Current hash table loading factor.

Definition at line 469 of file HashMap.h.

References casacore::HashMap< key, val >::availableBuckets(), and casacore::HashMap< key, val >::ndefined().

template<class key, class val>

float casacore::HashMap< key, val >::maxLoad ( ) const

inline

Get or set the maximum load factor.

Definition at line 439 of file HashMap.h.

References casacore::HashMap< key, val >::maxLoad_.

template<class key, class val>

casacore::HashMap< key, val >::maxLoad_ ( maxlf )

template<class key, class val>

uInt casacore::HashMap< key, val >::ndefined ( ) const

inline

Number of mappings which have been defined by the user.

Definition at line 466 of file HashMap.h.

References casacore::HashMap< key, val >::defs_.

Referenced by casacore::HashMap< key, val >::empty(), and casacore::HashMap< key, val >::loading().

template<class key, class val>

const val& casacore::HashMap< key, val >::operator() ( const key & ky ) const

Retrieve values from the map, possibly for later assignment.

It is important to realize that for the non-const version accessing the key causes an entry to be created in the map if it didn't already exist. The "value" for this new entry is the default value. "isDefined()" should be used if this behavior is not desired.

template<class key, class val>

val& casacore::HashMap< key, val >::operator() ( const key & ky )

template<class key, class val>

HashMap<key,val>& casacore::HashMap< key, val >::operator= ( const HashMap< key, val > & )

This copies the right hand side of the assignment.

Assignment is done with copy semantics. This means that all the state is copied.

template<class key, class val>

uInt casacore::HashMap< key, val >::populate ( uInt to )

protected

populate bucket "to".

Returns the bucket which is being moved...

template<class key, class val>

void casacore::HashMap< key, val >::remove ( const key & k )

Remove a user defined mapping from k to a value.

After this, the value which k maps to reverts to the default value.

template<class key, class val>

void casacore::HashMap< key, val >::setMaxLoad ( float new_max )

inline

Definition at line 440 of file HashMap.h.

References casacore::HashMap< key, val >::maxLoad_.

template<class key, class val>

uInt casacore::HashMap< key, val >::totalBuckets ( ) const

inline

Total number of buckets, i.e.

the number the hashing mechanism thinks it has. This is the total number of buckets used for calculations in the hashing mechanism. This may be smaller than allocBuckets() because more underlying storage may be allocated than the hashing mechanism needs.

Definition at line 449 of file HashMap.h.

References casacore::HashMap< key, val >::total_.

Referenced by casacore::HashMap< key, val >::hash().

template<class key, class val>

uInt casacore::HashMap< key, val >::totalSize ( ) const

Total size of this HashMap minus dynamically allocated memory for key or val.

template<class key, class val>

casacore::HashMap< key, val >::used_ ( uInt(defaultSize()) )

template<class key, class val>

uInt casacore::HashMap< key, val >::usedBuckets ( ) const

inline

Number of buckets currently populated by a bucket list.

Definition at line 457 of file HashMap.h.

References casacore::HashMap< key, val >::filled_.

Friends And Related Function Documentation

template<class key, class val>

friend class ConstHashMapIter< key, val >

friend

Definition at line 302 of file HashMap.h.

Member Data Documentation

template<class key, class val>

casacore::HashMap< key, val >::__pad0__

Constructor which allows for specifying:

default value, dflt
hash function, newfunc
maximum load factor, maxlf

This is provided because often the user will not be interested in specifying the initial number of buckets since the number is increased as needed to maintain the max load factor.

This is a pair because the hash function can either be a simple function or a class derived from HashClass.

Definition at line 376 of file HashMap.h.

template<class key, class val>

PtrBlock<List<OrderedPair<key,val> >*> casacore::HashMap< key, val >::blk

private

Definition at line 519 of file HashMap.h.

Referenced by casacore::HashMap< key, val >::allocBuckets().

template<class key, class val>

uInt casacore::HashMap< key, val >::defs_

private

Number of Defined Mappings.

Definition at line 516 of file HashMap.h.