ftlHashMap - SCM-NV/ftl GitHub Wiki

ftlHashMap is an associative container that contains key-value pairs with unique keys. Search, insertion, and removal of elements have average constant-time complexity.

Internally, the elements are not sorted in any particular order, but organized into buckets. Which bucket an element is placed into depends entirely on the hash of its key. This allows fast access to individual elements, since once the hash is computed, it refers to the exact bucket the element is placed into. The key types have to implement the ftlHash method and be comparable with the == operator. Hash functions for the basic Fortran types are predefined in the ftlHash module and can be combined to implement hash functions for any derived types.

ftlHashMap basically a Fortran reimplementation of C++'s std::unordered_map with a slightly different (and more intuitive) interface.

ftlHashMap uses the following macros for instantiation:

FTL_TEMPLATE_TYPE

The type of the values to be stored in the container, e.g. integer(int64) or MyDerivedType. Do not add the enclosing type() for derived types.

FTL_TEMPLATE_TYPE_IS_DERIVED

This needs to be defined if FTL_TEMPLATE_TYPE is a derived type.

FTL_TEMPLATE_TYPE_MODULE

The name of the module in which FTL_TEMPLATE_TYPE is defined. Specifying this is probably only necessary if FTL_TEMPLATE_TYPE is a derived type, or uses a kind defined in another module, e.g. int64 from the iso_fortran_env module.

FTL_TEMPLATE_TYPE_NAME

A convenient user-readable name for the value type, e.g. Int. This will be used in the type-name of the ftlHashMap container itself and the module in which it is available, e.g. setting this to Int will result in the type ftlHashMap[KEY]Int available in module ftlHashMap[KEY]IntModule, where [KEY] is the user-readable name of the key type.

FTL_TEMPLATE_KEYTYPE

The type of the keys used to access elements of the container, e.g. integer(int64) or MyDerivedType. Do not add the enclosing type() for derived types.

FTL_TEMPLATE_KEYTYPE_IS_DERIVED

This needs to be defined if FTL_TEMPLATE_KEYTYPE is a derived type. If the key type is derived, it must implement the ftlHash function and be comparable with the == operator.

FTL_TEMPLATE_KEYTYPE_MODULE

The name of the module in which FTL_TEMPLATE_KEYTYPE is defined. Specifying this is probably only necessary if FTL_TEMPLATE_KEYTYPE is a derived type, or uses a kind defined in another module, e.g. int64 from the iso_fortran_env module.

FTL_TEMPLATE_KEYTYPE_NAME

A convenient user-readable name for the key type, e.g. String. This will be used in the type-name of the ftlHashMap container itself and the module in which it is available, e.g. setting this to String will result in the type ftlHashMapString[VALUE] available in module ftlHashMapString[VALUE]Module, where [VALUE] is the user-readable name of the value type.

FTL_INSTANTIATE_TEMPLATE

If this macro is defined the template will be instantiated. If not, the template will not be instantiated, but some information about the ftlHashMap container (e.g. its name and the kind of iterator it provides) will be passed on to subsequent template instantiations (e.g. ftlAlgorithms).

There is a specialization of the ftlHashMap template for ftlString as the key type. It is accessed by defining FTL_TEMPLATE_KEYTYPE_IS_FTLSTRING. Its sole purpose is to add an alternative version for all methods that accept a key as input. The alternative version accepts a plain Fortran character variable as input instead of a ftlString. This in convenient when passing a string literal. Of course the normal versions accepting an ftlString are also available.

type(ftlHashMapStringInt) :: map

call map%Set(ftlString('inconvenient'), 1)
! ... is inconvenient compared to:
call map%Set('convenient', 2)
! ... but both versions are totally equivalent

If FTL_TEMPLATE_KEYTYPE_IS_FTLSTRING is defined, it is not needed to define either FTL_TEMPLATE_KEYTYPE_MODULE or FTL_TEMPLATE_KEYTYPE_IS_DERIVED. (Since we know that the keytype is exactly ftlString, we already know the module in which it is defined and that it is a derived type.) Note however, that FTL_TEMPLATE_KEYTYPE_NAME should still be defined.

Example instantiation of a map from strings to integers using the specialization for ftlString keytypes. The resulting type ftlHashMapStringInt is available in ftlHashMapStringIntModule.

#define FTL_TEMPLATE_KEYTYPE_IS_FTLSTRING
#define FTL_TEMPLATE_KEYTYPE_NAME String
#define FTL_TEMPLATE_TYPE integer
#define FTL_TEMPLATE_TYPE_NAME Int
#define FTL_INSTANTIATE_TEMPLATE
#include <ftlHashMap.F90_template>

Constructs a new ftlHashMap container. There a two versions:

• Constructs an empty container with a specified number of buckets.

  subroutine New(self, nBuckets)
     type(ftlHashMapKeyValue), intent(out) :: self
     integer                 , intent(in)  :: nBuckets

  For best performance, the initial number of buckets should be chosen to be slightly larger than the expected number of elements to be stored in the container. If this information is not available, it should be a small number as the number of buckets will grow dynamically as more elements are stored in the container.

• Constructs an ftlHashMap as a copy of another ftlHashMap.

  subroutine New(self, other)
     type(ftlHashMapKeyValue), intent(out) :: self
     type(ftlHashMapKeyValue), intent(in)  :: self

Destructs the container. The used storage is deallocated.

subroutine Delete(self)
   type(ftlHashMapKeyValue), intent(inout) :: self

Assignment of one ftlHashMap to another is exactly the same as copy-construction, see above.

subroutine assignment(=)(self, other)
   type(ftlHashMapKeyValue), intent(out) :: self
   type(ftlHashMapKeyValue), intent(in)  :: other

Returns a random access iterator to the first element of the container.

ftlHashMapKeyValueIterator function Begin(self)
   type(ftlHashMapKeyValue), intent(in) :: self

Notice that an ftlHashMap object makes no guarantees on which specific element is considered its first element. But, in any case, the range that goes from its begin to its end covers all the elements in the container.

If the container is empty, the returned iterator will be equal to End(). Note that this method exists as both type-bound and as a free function.

Returns a random access iterator to the element following the last element of the container. This element acts as a placeholder; attempting to access it results in undefined behavior.

ftlHashMapKeyValueIterator function End(self)
   type(ftlHashMapKeyValue), intent(in) :: self

Notice that an ftlHashMap object makes no guarantees on which order its elements follow. But, in any case, the range that goes from its begin to its end covers all the elements in the container.

Note that this method exists as both type-bound and as a free function.

Returns a logical value indicating whether the map is empty, i.e. whether its size is 0.

logical function Empty(self)
   type(ftlHashMapKeyValue), intent(in) :: self

This function does not modify the content of the container in any way. To clear the contents, member function ftlHashMap%Clear() exists.

Returns the number of entries in the ftlHashMap container.

integer function Size(self)
   type(ftlHashMapKeyValue), intent(in) :: self

Sets the entry with key to value. If no entry with key exists, a new entry will be added.

subroutine Set(self, key, value)
   type(ftlHashMapKeyValue), intent(inout) :: self
   KEYTYPE                 , intent(in)    :: key
   VALUETYPE               , intent(in)    :: value

Insertion into the map is a constant time operation, except for the case where the insertion causes the maximum load factor to be exceeded. In this case all N elements of the map are rehashed, which is an O(N) operation.

Returns a pointer to the value stored for key. If no entry with key exists a null pointer is returned.

function Get(self, key)
   type(ftlHashMapKeyValue), intent(in) :: self
   KEYTYPE                 , intent(in) :: key
   TYPE, pointer                        :: Get

Getting the value to a particular key is always a constant time operation. Note that the returned pointer is currently not guaranteed to remain valid if the map is rehashed (which might happen any time an element is inserted).

Checks whether the hash map has an entry for key.

logical function Has(self, key)
   type(ftlHashMapKeyValue), intent(in) :: self
   KEYTYPE                 , intent(in) :: key

Python style for checking whether a hash map has an entry for a particular key. Absolutely equivalent to ftlHashMap%Has().

logical function operator(.in.)(lhs, rhs)
   KEYTYPE                 , intent(in) :: lhs
   type(ftlHashMapKeyValue), intent(in) :: rhs

Searches the container for an element with key and returns an iterator to it if found, otherwise it returns an iterator to ftlHashMap%End() (the element past the end of the container).

type(ftlHashMapKeyValueIterator) function Find(self, key)
   type(ftlHashMapKeyValue), intent(in) :: self
   KEYTYPE                 , intent(in) :: key

Removes entries from the ftlHashMap container, reducing the size of the container by the number of removed elements.

• Remove the entry with a particular key. This has no effect if the map contains no such entry.

  subroutine Erase(self, key)
     type(ftlHashMapKeyValue), intent(inout) :: self
     KEYTYPE                 , intent(in)    :: key

• Remove the entry pointed to be a particular iterator.

  subroutine Erase(self, it)
     type(ftlHashMapKeyValue)        , intent(inout) :: self
     type(ftlHashMapKeyValueIterator), intent(in)    :: it

• Removes all entries in the (half open) range delimited by the iterators [first,last).

  subroutine Erase(self, first, last)
     type(ftlHashMapKeyValue)        , intent(inout) :: self
     type(ftlHashMapKeyValueIterator), intent(in)    :: first, last

Removes all entries from the map, leaving it with a size of zero.

subroutine Clear(self)
   type(ftlHashMapKeyValue), intent(inout) :: self

Returns the number of buckets in the ftlHashMap container.

The number of buckets influences directly the load factor of the container's hash table (and thus the probability of collision). The container automatically increases the number of buckets to keep the load factor below a specific threshold (its maxLoadFactor), causing a rehash each time the number of buckets needs to be increased.

integer function BucketCount(self)
   type(ftlHashMapKeyValue), intent(in) :: self

Returns the number of elements in bucket n.

The number of elements in a bucket influences the time it takes to access a particular element in the bucket. The container automatically increases the number of buckets to keep the load factor (which is the average bucket size) below its maxLoadFactor.

integer function BucketSize(self, n)
   type(ftlHashMapKeyValue), intent(in) :: self
   integer                 , intent(in) :: n

Returns the bucket number where the element with key is (or would be) located. Buckets are numbered from 1 to BucketCount.

integer function Bucket(self, key)
   type(ftlHashMapKeyValue), intent(in) :: self
   KEYTYPE                 , intent(in) :: key

Returns the current load factor in the ftlHashMap container, that is the ratio between the number of elements in the container (its size) and the number of buckets.

real function LoadFactor(self)
   type(ftlHashMapKeyValue), intent(in) :: self

The load factor influences the probability of collision in the hash table (i.e., the probability of two elements being located in the same bucket). The container automatically increases the number of buckets to keep the load factor below a specific threshold (its maxLoadFactor), causing a rehash each time an expansion is needed.

To retrieve or change this threshold, use member functions GetMaxLoadFactor and SetMaxLoadFactor:

Sets/Gets the maximum load factor (number of elements per bucket). The container automatically increases the number of buckets if the load factor exceeds this threshold.

subroutine SetMaxLoadFactor(self, ml)
   type(ftlHashMapKeyValue), intent(inout) :: self
   real                    , intent(in)    :: ml

real function GetMaxLoadFactor(self)
   type(ftlHashMapKeyValue), intent(in) :: self

Sets the number of buckets in the container to n, forcing a rehash of the elements in the container.

subroutine Rehash(self, nBuckets)
   type(ftlHashMapKeyValue), intent(inout) :: self
   integer                 , intent(in)    :: nBuckets

A rehash is the reconstruction of the hash table: All the elements in the container are rearranged according to their hash value into the new set of buckets. This may alter the order of iteration of elements within the container.

Rehashes are automatically performed by the container whenever its load factor is going to surpass its maxLoadFactor in an operation.

Notice that this function expects the number of buckets as argument. A similar function exists, ftlHashMap%Reserve(), that expects the number of elements in the container as argument.

Sets the number of buckets in the container (bucketCount) to the most appropriate to contain at least n elements.

subroutine Reserve(self, n)
   type(ftlHashMapKeyValue), intent(inout) :: self
   integer                 , intent(in)    :: n

If n is greater than the current bucketCount multiplied by the maxLoadFactor, the container's bucketCount is increased and a rehash is forced.

If n is lower than that, the function has no effect.