casa  5.7.0-16
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Public Types | Public Member Functions | Static Public Member Functions | Public Attributes | Protected Member Functions | Private Types | Private Attributes | Friends | List of all members
casacore::HashMap< key, val > Class Template Reference

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< uIntdistribution () 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

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:

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

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:

Template Type Argument Requirements (key)

Template Type Argument Requirements (val)

Thrown Exceptions

To Do

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 > > * > 
)
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_ ( )
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_ ( )
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
template<class key, class val>
casacore::HashMap< key, val >::hashClass ( )
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.

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

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

Definition at line 522 of file HashMap.h.

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

template<class key, class val>
uInt casacore::HashMap< key, val >::filled_
private

Slots with At Least One Value in the Bucket.

Definition at line 514 of file HashMap.h.

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

template<class key, class val>
Func casacore::HashMap< key, val >::func
private

Definition at line 520 of file HashMap.h.

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

template<class key, class val>
HashClass<key>* casacore::HashMap< key, val >::hashClass
private

Definition at line 521 of file HashMap.h.

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

template<class key, class val>
float casacore::HashMap< key, val >::maxLoad_
private

Maximum load.

Definition at line 518 of file HashMap.h.

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

template<class key, class val>
uInt casacore::HashMap< key, val >::total_
private

Total Slots.

Definition at line 510 of file HashMap.h.

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

template<class key, class val>
uInt casacore::HashMap< key, val >::used_
private

Slots Being Used.

Definition at line 512 of file HashMap.h.

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


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