   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.
Public Member Functions
	HashMap (const HashMap &)
	Copy constructor with copy semantics.
	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:
	HashMap (const val &dflt, uInt size, const HashClass< key > &newfunc, float maxlf=float(defaultMaxLoad_))
	HashMap (const val &dflt, Func newfunc, float maxlf=float(defaultMaxLoad_))
	Constructor which allows for specifying:
	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.
const val &	operator() (const key &ky) const
	Retrieve values from the map, possibly for later assignment.
val &	operator() (const key &ky)
val &	define (const key &k, const val &v)
	Define a complete mapping.
void	remove (const key &k)
	Remove a user defined mapping from `k` to a value.
Bool	isDefined (const key &k) const
	Check to see if a user defined mapping exists for `k`.
const val &	defaultVal () const
	Retrieve the default value.
val &	defaultVal ()
void	clear ()
	Remove all user defined mapping.
float	maxLoad () const
	Get or set the maximum load factor.
void	setMaxLoad (float new_max)
uInt	totalBuckets () const
	Total number of buckets, i.e.
uInt	availableBuckets () const
	Number of buckets available, i.e.
uInt	usedBuckets () const
	Number of buckets currently populated by a bucket list.
uInt	allocBuckets () const
	Number of buckets which have been allocated, i.e.
uInt	ndefined () const
	Number of mappings which have been defined by the user.
float	loading () const
	Current hash table loading factor.
Bool	empty () const
	Have any mappings been defined by the user.
Block< uInt >	distribution () const
	This returns a Block which has the number of elements in each bucket of the table.
uInt	totalSize () const
	Total size of this HashMap minus dynamically allocated memory for key or val.
virtual	~HashMap ()
	dtor
Static Public Member Functions
static float	defaultMaxLoad ()
static uInt	defaultSize ()
Protected Member Functions
uInt	hash (const key &k) const
	Call the hash function.
void	freeTable ()
	delete the contents of the hash table
uInt	enlarge ()
	enlarge the hash table.
uInt	populate (uInt to)
	populate bucket "to".
Private Types
enum	HashMap_Constants { defaultSize_, defaultMaxLoad_ }
Private Attributes
uInt	total_
	Total Slots.
uInt	used_
	Slots Being Used.
uInt	filled_
	Slots with At Least One Value in the Bucket.
uInt	defs_
	Number of Defined Mappings.
float	maxLoad_
	Maximum load.
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 casa::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 <casa/Containers/HashMap.h>
       #include <casa/BasicSL/String.h>
       #include <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 296 of file HashMap.h.

Member Typedef Documentation

template<class key, class val>

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

Signature of the hash functions.

Definition at line 305 of file HashMap.h.

Member Enumeration Documentation

template<class key, class val>

anonymous enum

Enumerator:

HashMapVersion

Definition at line 479 of file HashMap.h.

template<class key, class val>

enum casa::HashMap::HashMap_Constants [private]

Enumerator:

defaultSize_
defaultMaxLoad_

Definition at line 299 of file HashMap.h.

Constructor & Destructor Documentation

template<class key, class val>

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

Copy constructor with copy semantics.

template<class key, class val>

casa::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 325 of file HashMap.h.

template<class key, class val>

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

Definition at line 340 of file HashMap.h.

template<class key, class val>

casa::HashMap< key, val >::HashMap	(	const val &	dflt,
		Func	newfunc,
		float	maxlf = `float(defaultMaxLoad_)`
	)		`[inline]`

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 370 of file HashMap.h.

template<class key, class val>

casa::HashMap< key, val >::HashMap	(	const val &	dflt,
		const HashClass< key > &	newfunc,
		float	maxlf = `float(defaultMaxLoad_)`
	)		`[inline]`

Definition at line 377 of file HashMap.h.

template<class key, class val>

virtual casa::HashMap< key, val >::~HashMap ( ) [virtual]

dtor

Member Function Documentation

template<class key, class val>

uInt casa::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 458 of file HashMap.h.

References casa::HashMap< key, val >::blk, and casa::PtrBlock< T >::nelements().

template<class key, class val>

uInt casa::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 450 of file HashMap.h.

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

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

template<class key, class val>

void casa::HashMap< key, val >::clear ( ) [inline]

Remove all user defined mapping.

Definition at line 429 of file HashMap.h.

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

template<class key, class val>

static float casa::HashMap< key, val >::defaultMaxLoad ( ) [inline, static]

Definition at line 301 of file HashMap.h.

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

template<class key, class val>

static uInt casa::HashMap< key, val >::defaultSize ( ) [inline, static]

Definition at line 302 of file HashMap.h.

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

template<class key, class val>

const val& casa::HashMap< key, val >::defaultVal ( ) const [inline]

Retrieve the default value.

Definition at line 422 of file HashMap.h.

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

template<class key, class val>

val& casa::HashMap< key, val >::defaultVal ( ) [inline]

Definition at line 423 of file HashMap.h.

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

template<class key, class val>

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

Define a complete mapping.

template<class key, class val>

Block<uInt> casa::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 casa::HashMap< key, val >::empty ( ) const [inline]

Have any mappings been defined by the user.

Definition at line 466 of file HashMap.h.

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

template<class key, class val>

uInt casa::HashMap< key, val >::enlarge ( ) [protected]

enlarge the hash table.

Returns the bucket which is being moved...

template<class key, class val>

void casa::HashMap< key, val >::freeTable ( ) [protected]

delete the contents of the hash table

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

template<class key, class val>

uInt casa::HashMap< key, val >::hash ( const key & k ) const [inline, protected]

Call the hash function.

Definition at line 483 of file HashMap.h.

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

template<class key, class val>

Bool casa::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 casa::HashMap< key, val >::loading ( ) const [inline]

Current hash table loading factor.

Definition at line 464 of file HashMap.h.

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

template<class key, class val>

float casa::HashMap< key, val >::maxLoad ( ) const [inline]

Get or set the maximum load factor.

Definition at line 434 of file HashMap.h.

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

template<class key, class val>

uInt casa::HashMap< key, val >::ndefined ( ) const [inline]

Number of mappings which have been defined by the user.

Definition at line 461 of file HashMap.h.

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

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

template<class key, class val>

const val& casa::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& casa::HashMap< key, val >::operator() ( const key & ky )

template<class key, class val>

HashMap<key,val>& casa::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 casa::HashMap< key, val >::populate ( uInt to ) [protected]

populate bucket "to".

Returns the bucket which is being moved...

template<class key, class val>

void casa::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 casa::HashMap< key, val >::setMaxLoad ( float new_max ) [inline]

Definition at line 435 of file HashMap.h.

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

template<class key, class val>

uInt casa::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 444 of file HashMap.h.

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

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

template<class key, class val>

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

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

template<class key, class val>

uInt casa::HashMap< key, val >::usedBuckets ( ) const [inline]

Number of buckets currently populated by a bucket list.

Definition at line 452 of file HashMap.h.

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

Friends And Related Function Documentation

template<class key, class val>

friend class ConstHashMapIter< key, val > [friend]

Definition at line 297 of file HashMap.h.

Member Data Documentation

template<class key, class val>

PtrBlock<List<OrderedPair<key,val> >*> casa::HashMap< key, val >::blk [private]

Definition at line 514 of file HashMap.h.

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

template<class key, class val>

uInt casa::HashMap< key, val >::defs_ [private]

Number of Defined Mappings.

Definition at line 511 of file HashMap.h.

Referenced by casa::HashMap< key, val >::ndefined().

template<class key, class val>

val casa::HashMap< key, val >::dfltVal [private]

Definition at line 517 of file HashMap.h.

Referenced by casa::HashMap< key, val >::defaultVal().

template<class key, class val>

uInt casa::HashMap< key, val >::filled_ [private]

Slots with At Least One Value in the Bucket.

Definition at line 509 of file HashMap.h.

Referenced by casa::HashMap< key, val >::usedBuckets().

template<class key, class val>

Func casa::HashMap< key, val >::func [private]

Definition at line 515 of file HashMap.h.

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

template<class key, class val>

HashClass<key>* casa::HashMap< key, val >::hashClass [private]

Definition at line 516 of file HashMap.h.

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

template<class key, class val>

float casa::HashMap< key, val >::maxLoad_ [private]

Maximum load.

Definition at line 513 of file HashMap.h.

Referenced by casa::HashMap< key, val >::maxLoad(), and casa::HashMap< key, val >::setMaxLoad().

template<class key, class val>

uInt casa::HashMap< key, val >::total_ [private]

Total Slots.

Definition at line 505 of file HashMap.h.

Referenced by casa::HashMap< key, val >::totalBuckets().

template<class key, class val>

uInt casa::HashMap< key, val >::used_ [private]

Slots Being Used.

Definition at line 507 of file HashMap.h.

Referenced by casa::HashMap< key, val >::availableBuckets().

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

casacore/casa/Containers/HashMap.h

Public Types

Public Member Functions

Static Public Member Functions

Protected Member Functions

Private Types

Private Attributes

Friends

Detailed Description

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

Intended use:

Review Status

Prerequisite

Etymology

Synopsis

Example

Motivation

Template Type Argument Requirements (key)

Template Type Argument Requirements (val)

Thrown Exceptions

To Do

Member Typedef Documentation

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation

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