|
| 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_)) |
|
| HashMap (const val &dflt, Func newfunc, float maxlf=float(defaultMaxLoad_)) |
| Constructor which allows for specifying: More...
|
|
| 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...
|
|
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.define("two",2);
hash.define("four",4);
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
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)
Thrown Exceptions
To Do
-
add this feature
-
fix this bug
-
start discussion of this possible extension
Definition at line 297 of file HashMap.h.