These hash functions map the key type to any integer. This
integer is then used by
The hash function maps the key type to any integer. This
integer is then used by
class IntHash : public HashClass<Int> {
public:
uInt hash(const Int &v) const { return (uInt) v; }
uInt hash(const Int &v) { return (uInt) v; }
HashClass<Int> *clone() const { return new IntHash; }
IntHash() : HashClass<Int>() { }
};
This function maps elements of key type to any integer.
This integer is then used by
This function is used to make a deep copy. This means that the copy, which this function returns, contains all derived information.
- defaultSize_ = 131
- defaultMaxLoad_ = 4
- HashMapVersion = 1
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.
#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;
}
Signature of the hash functions
Copy constructor with copy semantics
Default constructor (and variation) which allows for specifying:
This is a pair because the hash function can either be a simple function or a class derived from HashClass.
Constructor which allows for specifying:
This is a pair because the hash function can either be a simple function or a class derived from HashClass.
This copies the right hand side of the assignment. Assignment is done with copy semantics. This means that all the state is copied.
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.
Define a complete mapping.
Remove a user defined mapping from k to a value. After this, the value which k maps to reverts to the default value.
Check to see if a user defined mapping exists for k. This does not modify the map.
Retrieve the default value.
Remove all user defined mapping.
Get or set the maximum load factor.
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.
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.
Number of buckets currently populated by a bucket list.
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.
Number of mappings which have been defined by the user.
Current hash table loading factor.
Have any mappings been defined by the user.
This returns a Block which has the number of elements in each bucket of the table.
dtor
delete the contents of the hash table
enlarge the hash table. Returns the bucket which is being moved...
populate bucket "to". Returns the bucket which is being moved...