stdlib

stdlib_hashmap_wrappers and stdlib_hashmaps

:local:
:depth: 2

Overview of hash maps

A hash map (hash table) is a data structure that maps keys to values. It uses a hash function to compute a hash code from the key that serves as an index into a linear array of slots (buckets) from which the desired value can be extracted. Each key ideally maps to a unique slot, but most hash functions are imperfect and can map multiple keys to the same slot resulting in collisions. Hash maps differ in how they deal with such collisions. This document discusses the hash maps in the Fortran Standard Library.

Licensing

The Fortran Standard Library is distributed under the MIT License. However components of the library should be evaluated as to whether they are compatible with the MIT License. The current hash maps were inspired by an implementation of David Chase. While the code has been greatly modified from his implementation, he has give permission for the unrestricted use of his code.

The hash map modules

The Fortran Standard Library provides two modules for the implementation of simple hash maps. These maps only accept hash functions with a single argument, the key, and yield a 32 bit hash code. The modules will need to be modified if it is desired to use hash functions with a different API. The two modules are: stdlib_hashmap_wrappers, and stdlib_hashmaps corresponding to the files: stdlib_hashmap_wrappers.f90, and stdlib_hashmaps.f90

The module stdlib_hashmap_wrappers provides types and procedures for use by stdlib_hashmaps. It provides an interface to the 32 bit hash functions of the Standard Library module, stdlib_hash_32bit, and provides wrappers to some of the hash functions so that they no longer need to be supplied seeds. It also defines the key_type derived type. The key_type is used to define keys that, in turn, are used to identify the data entered into a hash map.

The module stdlib_hashmaps defines the API for a parent datatype, hashmap_type and two extensions of that hash map type: chaining_hashmap_type and open_hashmap_type.

The hashmap_type defines the Application Programmers Interface (API) for the procedures used by its two extensions. It explicitly defines five non-overridable procedures. It also defines the interfaces for eleven deferred procedures. It does not define the finalization routines for the two extension types, or one routine provided by the open_hashmap_type.

The chaining_hashmap_type uses separate chaining with linked lists to deal with hash index collisions. In separate chaining the colliding indices are handled by using linked lists with their roots at the hash index. The chaining_hashmap_type procedures are implemented in the module stdlib_hashmap_chaining corresponding to the file, stdlib_hashmap_chaining.f90.

The open_hashmap_type uses linear open addressing to deal with hash index collisions. In linear open addressing the colliding indices are handled by searching from the initial hash index in increasing steps of one (modulo the hash map size) for an open map slot. The open_hashmap_type procedures are implemented in the submodule stdlib_hashmap_open corresponding to the file stdlib_hashmap_open.f90.

The maps use powers of two for their slot sizes, so that the function, fibonacci_hash, can be used to map the hash codes to indices in the map. This is expected to be more efficient than prime number mapping using a modulo operation, and reduces the requirement that the hash function need to do a good job randomizing its lower order bits. They do require a good randomizing hash method for good performance. Both adjust the map size to reduce collisions, based on the ratio of the number of hash map probes to the number of subroutine calls. Wile the maps make extensive use of pointers internally, a private finalization subroutine avoids memory leaks. The maps can take entry keys of type key_type, and other data (also commonly known as values, as in key value pairs) in any scalar type. The maps allow the addition, removal, and lookup of entries, and the inclusion of data in addition to the entry key.

The stdlib_hashmap_wrappers module

The stdlib_hashmap_wrappers module provides data types to represent keys and associated data stored in a module, but is also, a wrapper for the stdlib_hash_32bit module. It allows direct access to the stdlib_hash_32bit procedures: fibonacci_hash, fnv_1_hasher, fnv_1a_hasher; and provides wrapper functions, seeded_nmhash32_hasher, seeded_nmhash32x_hasher, and seeded_water_hasher to the hash functions: nmhash32, nmhash32x, and water_hash, respectively. It defines an interface, hasher_fun, compatible with the hash functions that take a non-scalar key. It defines one integer constant used as a kind value,int_hash. It also defines two types, key_type and other_type, and associated procedures, for storing and manipulating keys and their associated data.

The stdlib_hashmap_wrappers’s constant, int_hash

The constant int_hash is used to define the integer kind value for the returned hash codes and variables used to access them. It currently is imported from stdlib_hash_32bit where it has the value, int32.

The stdlib_hashmap_wrappers’ module’s derived types

The stdlib_hashmap_wrappers defines key_type which is intended to be used for the search keys of hash tables. The tye is opaque. The current representation is as follows

    type :: key_type
        private
        integer(int8), allocatable :: value(:)
    end type key_type

The module also defines six procedures for those types: copy_key, equal_keys, free_key, get, set, and one operator, ==, for use by the hash maps to manipulate or inquire of components of those types.

Table of stdlib_hashmap_wrappers procedures

The stdlib_hashmap_wrappers module provides procedures in several categories: procedures to manipulate data of the key_type; and 32 bit hash functions for keys. The procedures in each category are listed below. It also provides an operator to compare two key type values for equality.

Procedures to manipulate key_type data:

Procedures to hash keys to 32 bit integers:

Operator to compare two key_type values for equality

Specifications of the stdlib_hashmap_wrappers procedures

copy_key - Returns a copy of the key

Status

Experimental

Description

Returns a copy of an input of type key_type.

Syntax

call {f:subr}copy_key ( old_key, new_key )

Class

Subroutine.

Arguments

old_key: shall be a scalar expression of type key_type. It is an intent(in) argument.

new_key: shall be a scalar variable of type key_type. It is an intent(out) argument.

Example

```{literalinclude} ../../example/hashmaps/example_hashmaps_copy_key.f90 :language: fortran



#### `fibonacci_hash` - maps an integer to a smaller number of bits

##### Status

Experimental

##### Description

`fibonacci_hash` is just a re-export of the function of the same name
implemented in
[`stdlib_hash_32bit`](/stdlib/doc/specs/stdlib_hash_procedures.html).
It reduces the value of a 32 bit integer to a smaller number of bits.


#### `fnv_1_hasher`- calculates a hash code from a key

##### Status

Experimental

##### Description

Calculates a 32 bit hash code from an input of type `key_type`.

##### Syntax

`code = ` {f:func}`fnv_1_hasher` `( key )`

##### Class

Pure function

##### Argument

`key`: Shall be a scalar expression of type `key_type`.
It is an `intent(in)` argument.

##### Result character

The result is a scalar integer of kind `int32`.

##### Result value

The result is a hash code created using the FNV-1 algorithm.

##### Note

`fnv_1_hasher` is an implementation of the original FNV-1 hash code of
Glenn Fowler, Landon Curt Noll, and Phong Vo.
This code is relatively fast on short keys, and is small enough that
it will often be retained in the instruction cache if hashing is
intermittent.
As a result it should give good performance for typical hash map
applications.
This code does not pass any of the SMHasher tests, but the resulting
degradation in performance due to its larger number of collisions is
expected to be minor compared to its faster hashing rate.

##### Example

```{literalinclude} ../../example/hashmaps/example_hashmaps_fnv_1_hasher.f90
:language: fortran

fnv_1a_hasher- calculates a hash code from a key

Status

Experimental

Description

Calculates a 32 bit hash code from an input of type key_type.

Syntax

code = fnv_1a_hasher ( key )

Class

Pure function

Argument

key: Shall be a scalar expression of type key_type. It is an intent(in) argument.

Result character

The result is a scalar integer of kind int32.

Result value

The result is a hash code created using the FNV-1a algorithm.

Note

fnv_1a_hasher is an implementation of the original FNV-1A hash code of Glenn Fowler, Landon Curt Noll, and Phong Vo. This code is relatively fast on short keys, and is small enough that it will often be retained in the instruction cache if hashing is intermittent. As a result it should give good performance for typical hash map applications. This code does not pass any of the SMHasher tests, but the resulting degradation in performance due to its larger number of collisions is expected to be minor compared to its faster hashing rate.

Example

```{literalinclude} ../../example/hashmaps/example_hashmaps_fnv_1a_hasher.f90 :language: fortran


#### `free_key` - frees the memory associated with a key

##### Status

Experimental

##### Description

Deallocates the memory associated with a variable of type
`key_type`.

##### Syntax

`call ` {f:subr}`free_key` `( key )`

##### Class

Subroutine.

##### Argument

`key`: shall be a scalar variable of type `key_type`. It
is an `intent(out)` argument.

##### Example

```{literalinclude} ../../example/hashmaps/example_hashmaps_free_key.f90
:language: fortran

get - extracts the data from a derived type

Status

Experimental

Description

Extracts the data from a key_type and stores it in the variable value.

Syntax

call {f:subr}get ( key, value )

Class

Subroutine.

Argument

key: shall be a scalar expression of type key_type. It is an intent(in) argument.

value: shall be an allocatable default character string variable, or an allocatable vector variable of type integer and kind int8 or int32.

Example

```{literalinclude} ../../example/hashmaps/example_hashmaps_get.f90 :language: fortran



#### `hasher_fun`- serves as a function prototype.

##### Status

Experimental

##### Description

Serves as a prototype for hashing functions with a single, `key`,
argument of type `key_type` returning an `int32` hash value.

##### Syntax

`type(` `hasher_fun` `), pointer :: fun_pointer`

##### Class

Pure function prototype

##### Argument

`key`: Shall be a rank one array expression of type `integer(int8)`.
It is an `intent(in)` argument.

##### Result character

The result is a scalar integer of kind `int32`.

##### Result value

The result is a hash code.

##### Note

`hasher_fun` is a prototype for defining dummy arguments and function
pointers intended for use as a hash function for the hash maps.

##### Example

```{literalinclude} ../../example/hashmaps/example_hashmaps_hasher_fun.f90
:language: fortran

operator(==) - Compares two keys for equality

Status

Experimental

Description

Returns .true. if two keys are equal, and .false. otherwise.

Syntax

test = key1 == key2

Class

Pure operator.

Arguments

key1: shall be a scalar expression of type key_type. It is an intent(in) argument.

key2: shall be a scalar expression of type key_type. It is an intent(in) argument.

Result character

The result is a value of type default logical.

Result value

The result is .true. if the keys are equal, otherwise .falss..

Example
```{literalinclude} ../../example/hashmaps/example_hashmaps_equal_keys.f90
:language: fortran



#### `seeded_nmhash32_hasher`- calculates a hash code from a key

##### Status

Experimental

##### Description

Calculates a 32 bit hash code from an input of type `key_type`.

##### Syntax

`code = ` `seeded_nmhash32_hasher` `( key )`

##### Class

Pure function

##### Argument

`key`: Shall be a scalar expression of type `key_type`.
It is an `intent(in)` argument.

##### Result character

The result is a scalar integer of kind `int32`.

##### Result value

The result is a hash code created using the `nmhash32` algorithm.

##### Note

`seeded_nmhash32_hasher` is a wrapper to the `NMHASH32_HASH` of the
module `stdlib_hash_32bit`, which supplies a fixed seed
to the wrapped function. `NMHASH32` is an implementation of the
`nmhash32` hash code of James Z. M. Gao.
This code has good, but not great, performance on long keys, poorer
performance on short keys.
As a result it should give fair performance for typical hash map
applications.
This code passes the SMHasher tests.

##### Example

```{literalinclude} ../../example/hashmaps/example_hashmaps_seeded_nmhash32_hasher.f90
:language: fortran

seeded_nmhash32x_hasher- calculates a hash code from a key

Status

Experimental

Description

Calculates a 32 bit hash code from an input of type key_type.

Syntax

code = seeded_nmhash32x_hasher ( key )

Class

Pure function

Argument

key: Shall be a scalar expression of type key_type. It is an intent(in) argument.

Result character

The result is a scalar integer of kind int32.

Result value

The result is a hash code created using the nmhash32x algorithm.

Note

seeded_nmhash32x_hasher is a wrapper to the nmhash32x_hash of the module stdlib_hash_32bit, which supplies a fixed seed to the wrapped function. nmhash32x is an implementation of the nmhash32x hash code of James Z. M. Gao. This code has good, but not great, performance on long keys, poorer performance on short keys. As a result it should give fair performance for typical hash map applications. This code passes the SMHasher tests.

Example

```{literalinclude} ../../example/hashmaps/example_hashmaps_seeded_nmhash32x_hasher.f90 :language: fortran



#### `seeded_water_hasher`- calculates a hash code from a key

##### Status

Experimental

##### Description

Calculates a 32 bit hash code from an input of type `key_type`.

##### Syntax

`code = ` `seeded_water_hasher` `( key )`

##### Class

Pure function

##### Argument

`key`: Shall be a scalar expression of type `key_type`.
It is an `intent(in)` argument.

##### Result character

The result is a scalar integer of kind `int32`.

##### Result value

The result is a hash code created using the `waterhash` algorithm.

##### Note

`seeded_water_hasher` is a wrapper to the `water_hash` of the
module `stdlib_hash_32bit`, which supplies a fixed seed
to the wrapped function. `water_hash` is an implementation of the
`waterhash` hash code of Tommy Ettinger.
This code has excellent performance on long keys, and good performance
on short keys.
As a result it should give reasonable performance for typical hash
table applications.
This code passes the SMHasher tests.

##### Example

```{literalinclude} ../../example/hashmaps/example_hashmaps_seeded_water_hasher.f90
:language: fortran

set - places the data in a derived type

Status

Experimental

Description

Places the data from value in a key_type.

Syntax

call {f:subr}set ( key, value )

Class

Subroutine.

Argument

key: shall be a scalar variable of type key_type. It is an intent(out) argument.

value: shall be a default character string scalar expression, or a vector expression of type integerand kind int8 or int32. It is an intent(in) argument.

Note

Values of types other than a scalar default character or and int8 or int32 vector can be used as the basis of a key by transferring the value to an int8 vector.

Example

```{literalinclude} ../../example/hashmaps/example_hashmaps_set.f90 :language: fortran



## The `stdlib_hashmaps` module

The `stdlib_hashmaps` module defines three public data types,
associated procedures and constants that implement two simple hash map
types using separate chaining hashing and open addressing hashing. The
derived type `hashmap_type` is the parent type to its two
extensions: `chaining_hashmap_type` and `open_hashmap_type`.
The extension types provide 
procedures to manipulate the structure of a hash map object:
`init`, `map_entry`, `rehash`, `remove`, and
`set_other_data`. They also provide procedures to inquire about
entries in the hash map: `get_other_data`, and
`key_test`. Finally they provide procedures to inquire about the
overall structure and performance of the hash map object:`calls`,
`entries`, `get_other_data`, `loading`, `slots`, and
`total_depth`. The module also defines a number of public constants:
`probe_factor`, `load_factor`, `map_probe_factor`, `default_bits`,
`max_bits`, `int_calls`, `int_depth`, `int_index`,
`int_probes`, `success`, `alloc_fault`, and `array_size_error`.

Generic key interfaces for `key_test`, `map_entry`, `get_other_data`,
`remove`, and `set_other_data` are povided so that the supported types
of `int8` arrays, `int32` arrays and `character` scalars can be used in the
key field as well as the base `key` type.  So for `key_test`,
`key_key_test` specifies key type for the key field, `int8_key_test` is `int8`
for the key field and so on.  Procedures other than `key_key_test` will call
the `set` function to generate a key type and pass to `key_key_test`.         

### The `stdlib_hashmaps` module's public constants

The module defines several categories of public constants. Some are
used to parameterize the empirical slot expansion code. Others
parameterize the slots table size. Some are used to define
integer kind values for different applications. Finally, some are used
to report errors or success.

The constants `probe_factor`, and `map_probe_factor` are used to
parameterize the slot expansion code used to determine when in a
in a procedure call the number 
of slots need to be increased to decrease the search path for an
entry. The constant `probe_factor` is used to determine when
the ratio of the number of map probes to map calls is too large and 
the slots need expansion. The constant `map_probe_factor` is used to
determine when inserting a new entry the ratio of the number of map
probes to map calls is too large and the slots need expansion.

The constants `default_bits`, and
`max_bits` are used to parameterize the table's slots size. The
`default_bits` constant defines the default initial number of slots
with a current value of 6 resulting in an initial `2**6 == 64`
slots. This may optionally be overridden on hash map creation. The
`max_bits` parameter sets the maximum table size as `2**max_bits` with
a default value for `max_bits` of 30. The table will not work for a
slots size greater than `2**30`.

The constants `int_calls`, `int_depth`, `int_index`, and `int_probes`
are used to define integer kind values for various contexts. The
number of calls are reported and stored in entities of kind
`int_calls`. Currently `int_calls` has the value of `int64`. The
total depth, the number of inquiries needed to access all elements
of the table, is reported and stored in entities of kind
`int_depth`. Currently `int_depth` has the value of `int64`. The
number of entries in the table, is reported and stored in entities of
kind `int_index`. Currently `int_index` has the value of `int32`.
The number of probes, hash map enquiries, are reported and stored in
entities of kind `int_probes`. Currently `int_probes` has the value of
`int64`.

The constant `load_factor` is only used by the `open_hashmap_type`. It
specifies the maximum fraction of the available slots that may be
filled before expansion occurs. The current `load_factor = 0.5625` so
the current implementation of `open_hashmap_type` can only hold a
little more than `2**29` entries.

Finally the error codes `success`, `alloc_fault`, and
`array_size_error` are used to report the error status of certain
procedure calls. The `succes` code indicates that no problems were
found. The `alloc_fault` code indicates that a memory allocation
failed. Finally the `array_size_error` indicates that on table
creation `slots_bits` is less than `default_bits` or
greater than `max_bits`.

### The `stdlib_hashmaps` module's derived types

The `stdlib_hashmaps` module defines three public derived types and
seven private types used in the implementation of the public
types. The public types are the abstract `hashmap_type` and its
extensions: `chaining_hashmap_type` and `open_hashmap_type`. The three
private derived types, `chaining_map_entry_type`,
`chaining_map_entry_ptr`, and `chaining_map_entry_pool` are used in
the implementation of the `chaining_hashmap_type` public type. The
four private derived types, `open_map_entry_type`,
`open_map_entry_list`, `open_map_entry_ptr`, and `open_map_entry_pool`
are used in the implementation of the `open_hashmap_type` public
type. Each of these types are described below. 

#### The `hashmap_type` abstract type

The `hashmap_type` abstract type serves as the parent type for the two
types `chaining_hashmap_type` and `open_hashmap_type`. It defines
eight private components:

* `call_count` - the number of procedure calls on the map;

* `nbits` - the number of bits used to address the slots; 

* `num_entries` - the number of entries in the map;

* `num_free` - the number of entries in the free list of removed 
  entries;

* `probe_count` - the number of map probes since the last resizing or
  initialization;

* `total_probes` - the number of probes of the map up to the last
  resizing or initialization; and

* `hasher` - a pointer to the hash function used by the map.

* `initialized` - track if map has been initialized

It also defines five non-overridable procedures:

* `calls` - returns the number of procedure calls on the map;

* `entries` - returns the number of entries in the map;

* `map_probes` - returns the number of map probes since
  initialization;

* `num_slots` - returns the number of slots in the map; and

* `slots_bits` - returns the number of bits used to address the slots;

and ten deferred procedures:

* `get_all_keys` - gets all the keys contained in a map;

* `get_other_data` - gets the value associated with a key;

* `init` - initializes the hash map;

* `key_test` - returns a logical flag indicating whether the key is 
  defined in the map. 

* `loading` - returns the ratio of the number of entries to the number
  of slots;

* `map_entry` - inserts a key and optionally a corresponding value into
 the map;

* `rehash` - rehashes the map with the provided hash function;

* `remove` - removes the entry associated wit the key;

* `set_other_data` - replaces the value associated with a key;

* `total_depth` - returns the number of probes needed to address all
  the entries in the map;

The type's definition is below:

```fortran
    type, abstract :: hashmap_type

        private
        integer(int_calls) :: call_count = 0
        integer(int_calls) :: probe_count = 0
        integer(int_calls) :: total_probes = 0
        integer(int_index) :: num_entries = 0
        integer(int_index) :: num_free = 0
        integer(int32)     :: nbits = default_bits
        procedure(hasher_fun), pointer, nopass :: hasher => fnv_1_hasher

    contains
    
        procedure, non_overridable, pass(map) :: calls
        procedure, non_overridable, pass(map) :: entries
        procedure, non_overridable, pass(map) :: map_probes
        procedure, non_overridable, pass(map) :: num_slots
        procedure, non_overridable, pass(map) :: slots_bits
        procedure(get_all_keys), deferred, pass(map)        :: get_all_keys
        procedure(init_map), deferred, pass(map)            :: init
        procedure(loading), deferred, pass(map)             :: loading
        procedure(rehash_map), deferred, pass(map)          :: rehash
        procedure(total_depth), deferred, pass(map)         :: total_depth
    
        !! Generic interfaces for key types.
        procedure(key_key_test), deferred, pass(map) :: key_key_test
        procedure, non_overridable, pass(map) :: int8_key_test
        procedure, non_overridable, pass(map) :: int32_key_test
        procedure, non_overridable, pass(map) :: char_key_test
        
        procedure(key_map_entry), deferred, pass(map) :: key_map_entry
        procedure, non_overridable, pass(map) :: int8_map_entry
        procedure, non_overridable, pass(map) :: int32_map_entry
        procedure, non_overridable, pass(map) :: char_map_entry
        
        procedure(key_get_other_data), deferred, pass(map)  :: key_get_other_data
        procedure, non_overridable, pass(map) :: int8_get_other_data
        procedure, non_overridable, pass(map) :: int32_get_other_data
        procedure, non_overridable, pass(map) :: char_get_other_data
        
        procedure(key_remove_entry), deferred, pass(map) :: key_remove_entry
        procedure, non_overridable, pass(map) :: int8_remove_entry
        procedure, non_overridable, pass(map) :: int32_remove_entry
        procedure, non_overridable, pass(map) :: char_remove_entry
        
        procedure(key_set_other_data), deferred, pass(map)  :: key_set_other_data
        procedure, non_overridable, pass(map) :: int8_set_other_data
        procedure, non_overridable, pass(map) :: int32_set_other_data
        procedure, non_overridable, pass(map) :: char_set_other_data
        
        generic, public :: key_test => key_key_test, int8_key_test, int32_key_test, char_key_test
        generic, public :: map_entry => key_map_entry, int8_map_entry, int32_map_entry, char_map_entry
        generic, public :: get_other_data => key_get_other_data, int8_get_other_data, int32_get_other_data, char_get_other_data
        generic, public :: remove => key_remove_entry, int8_remove_entry, int32_remove_entry, char_remove_entry
        generic, public :: set_other_data => key_set_other_data, int8_set_other_data, int32_set_other_data, char_set_other_data
        
    end type hashmap_type

The chaining_map_entry_type derived type

Entities of the type chaining_map_entry_type are used to define a linked list structure that stores the key, its other data, the hash of the key, and the resulting index into the inverse table. The type’s definition is below:

    type :: chaining_map_entry_type  ! Chaining hash map entry type
        private
        integer(int_hash)   :: hash_val ! Full hash value
        type(key_type)      :: key ! The entry's key
        class(*), allocatable  :: other ! Other entry data
        integer(int_index)  :: index ! Index into inverse table
        type(chaining_map_entry_type), pointer :: &
            next => null() ! Next bucket
    end type chaining_map_entry_type

Currently the int_hash and int_index have the value of int32.

The chaining_map_entry_ptr derived type

The type chaining_map_entry_ptr is used to define the elements of the hash map that are either empty or link to the linked lists containing the elements of the table. The type’s definition is below:

    type chaining_map_entry_ptr ! Wrapper for a pointer to a chaining
                                ! map entry type object
        type(chaining_map_entry_type), pointer :: target => null()
    end type chaining_map_entry_ptr

The chaining_map_entry_pool derived type

The type chaining_map_entry_pool is used to implement a pool of allocated chaining_map_entry_type elements to save on allocation costs. The type’s definition is below:

    type :: chaining_map_entry_pool
    ! Type implementing a pool of allocated
    ! `chaining_map_entry_type` objects
        private
    ! Index of next bucket
        integer(int_index)                          :: next = 0
        type(chaining_map_entry_type), allocatable :: more_map_entries(:)
        type(chaining_map_entry_pool), pointer      :: lastpool => null()
    end type chaining_map_entry_pool

The chaining_hashmap_type derived type

The chaining_hashmap_type derived type extends the hashmap_type to implements a separate chaining hash map. In addition to the components of the hashmap_type it provides the four components:

It also implements all of the deferred procedures of the hashmap_type and a finalizer for its maps. The type’s definition is as follows:

    type, extends(hashmap_type) :: chaining_hashmap_type
        private
        type(chaining_map_entry_pool), pointer    :: cache => null()
        type(chaining_map_entry_type), pointer    :: free_list => null()
        type(chaining_map_entry_ptr), allocatable :: inverse(:)
        type(chaining_map_entry_ptr), allocatable :: slots(:)
    contains
        procedure :: get_all_keys => get_all_chaining_keys
        procedure :: key_get_other_data => get_other_chaining_data
        procedure :: init => init_chaining_map
        procedure :: loading => chaining_loading
        procedure :: key_map_entry => map_chain_entry
        procedure :: rehash => rehash_chaining_map
        procedure :: key_remove_entry => remove_chaining_entry
        procedure :: key_set_other_data => set_other_chaining_data
        procedure :: total_depth => total_chaining_depth
        procedure :: key_key_test => chaining_key_test
        final     :: free_chaining_map
    end type chaining_hashmap_type

The open_map_entry_type derived type

Entities of the type open_map_entry_type are used to define a linked list structure that stores the key, its other data, the hash of the key, and the resulting index into the inverse table. The type’s definition is below:

    type :: open_map_entry_type  ! Open hash map entry type
        private
        integer(int_hash)  :: hash_val ! Full hash value
        type(key_type)     :: key ! The entry's key
        class(*), allocatable  :: other ! Other entry data
        integer(int_index) :: index ! Index into inverse table
    end type open_map_entry_type

Currently int_hash and int_index have the value of int32.

The open_map_entry_ptr derived type

The type open_map_entry_ptr is used to define the elements of the hash map that are either empty or link to the linked lists containing the elements of the table. The type’s definition is below:

    type open_map_entry_ptr ! Wrapper for a pointer to a open
                            ! map entry type object
        type(open_map_entry_type), pointer :: target => null()
    end type open_map_entry_ptr

The open_hashmap_type derived type

The open_hashmap_type derived type extends the hashmap_type to implement an open addressing hash map. In addition to the components of the hashmap_type it provides the four components:

It also implements all of the deferred procedures of the hashmap_type and a finalizer for its maps. The type’s definition is as follows:

    type, extends(hashmap_type) :: open_hashmap_type
        private
        integer(int_index) :: index_mask = 2_int_index**default_bits-1
        type(open_map_entry_pool), pointer    :: cache => null()
        type(open_map_entry_list), pointer    :: free_list => null()
        type(open_map_entry_ptr), allocatable  :: inverse(:)
        integer(int_index), allocatable        :: slots(:)
    contains
        procedure :: get_all_keys => get_all_open_keys
        procedure :: key_get_other_data => get_other_open_data
        procedure :: init => init_open_map
        procedure :: loading => open_loading
        procedure :: key_map_entry => map_open_entry
        procedure :: rehash => rehash_open_map
        procedure :: key_remove_entry => remove_open_entry
        procedure :: key_set_other_data => set_other_open_data
        procedure :: total_depth => total_open_depth
        procedure :: key_key_test => open_key_test
        final     :: free_open_map
    end type open_hashmap_type

Table of stdlib_hashmap procedures

The stdlib_hashmap module provides procedures in several categories: a procedure to initialize the map; a procedure to modify the structure of a map; procedures to modify the content of a map; procedures to report on the content of a map; and procedures to report on the structure of the map. The procedures in each category are listed below.

Procedure to initialize a chaining hash map:

Procedure to modify the structure of a map:

Procedures to modify the content of a map:

Procedures to report the content of a map:

Procedures to report on the structure of the map:

Specifications of the stdlib_hashmaps procedures

calls - Returns the number of calls on the hash map

Status

Experimental

Description

Returns the number of procedure calls on a hash map.

Syntax

value = map % calls(bound) ()

Class

Pure function

Argument

map (pass) - shall be an expression of class hashmap_type. It is an intent(in) argument.

Result character

The result will be an integer of kind int_calls.

Result value

The result will be the number of procedure calls on the hash map.

Example

```{literalinclude} ../../example/hashmaps/example_hashmaps_calls.f90 :language: fortran



#### `entries` - Returns the number of entries in the hash map

##### Status

Experimental

##### Description

Returns the number of entries in a hash map.

##### Syntax

`value = map % ` `entries(bound)` `()`

##### Class

Pure function

##### Argument

`map` (pass)  - shall be an expression of class `hashmap_type`.
It is an `intent(in)` argument.

##### Result character

The result will be an integer of kind `int_index`.

##### Result value

The result will be the number of entries in the hash map.

##### Example

```{literalinclude} ../../example/hashmaps/example_hashmaps_entries.f90
:language: fortran

get_all_keys - Returns all the keys contained in a map

Status

Experimental

Description

Returns all the keys contained in a map.

Syntax

call map % get_all_keys(bound) ( all_keys )

Class

Subroutine

Arguments

map (pass): shall be a scalar variable of class chaining_hashmap_type or open_hashmap_type. It is an intent(in) argument. It will be the hash map used to store and access the other data.

all_keys: shall be a rank-1 allocatable array of type key_type. It is an intent(out) argument.

Example

```{literalinclude} ../../example/hashmaps/example_hashmaps_get_all_keys.f90 :language: fortran



#### `get_other_data` - Returns other data associated with the `key`

##### Status

Experimental

##### Description

Returns the value associated with the `key`,

##### Syntax

`value = map % ` `get_other_data(bound)` `( key, other [, exists] )`

##### Class

Subroutine

##### Arguments

`map` (pass): shall be a scalar variable of class
  `chaining_hashmap_type` or `open_hashmap_type`. It is an
  `intent(inout)` argument. It will be 
  the hash map used to store and access the other data.

`key`: shall be a of type `key_type` scalar, `character` scalar, `int8` array
or `int32` array. It is an `intent(in)` argument.

`other`: shall be a allocatable unlimited polymorphic scalar.  
(class(*), allocatable)  It is an `intent(out)` argument.
It is the value associated with the `key`.

`exists` (optional): shall be a variable of type logical. It is an
`intent(out)` argument. If `.true.` an entry with the given `key`
exists in the map and `other` is defined. If `.false.` `other` is
undefined.

##### Example

 The following is an example of the retrieval of other data
  associated with a `key`:

```{literalinclude} ../../example/hashmaps/example_hashmaps_get_other_data.f90
:language: fortran

init - initializes a hash map

Status

Experimental

Description

Initializes a hashmap_type object.

Syntax

call map % init(bound) ( [hasher, slots_bits, status ] )

Class

Subroutine

Arguments

map (pass): shall be a scalar variable of class chaining_hashmap_type or open_hashmap_type. It is an intent(out) argument. It will be a hash map used to store and access the entries.

hasher: (optional): shall be a procedure with interface hash_fun. It is an intent(in) argument. It is the procedure to be used to generate the hashes for the table from the keys of the entries. Defaults to fnv_1_hasher if not provided.

slots_bits (optional): shall be a scalar default integer expression. It is an intent(in) argument. The initial number of slots in the table will be 2**slots_bits.

status (optional): shall be a scalar integer variable of kind int32. It is an intent(out) argument. On return if present it shall have an error code value.

Example

```{literalinclude} ../../example/hashmaps/example_hashmaps_init.f90 :language: fortran



#### `key_test` - indicates whether `key` is present

##### Status

Experimental

##### Description

Returns a logical flag indicating whether `key` is present for an
entry in the map.

##### Syntax

`call map % ` `key_test(bound)` `( key, present )`

##### Class

Subroutine.

##### Arguments

`map` (pass): shall be a scalar variable of class
`chaining_hashmap_type` or `open_hashmap_type`. 
It is an `intent(inout)` argument. It is the hash map whose entries
are examined.

`key`: shall be a of type `key_type` scalar, `character` scalar, `int8` array
or `int32` array. It is an `intent(in)` argument. It is a `key` whose 
presence in the `map` is being examined.

`present`: shall be a scalar variable of type `logical`.
It is an `intent(out)` argument. It is a logical flag where
`.true.` indicates that an entry with that `key` is present in the
`map` and `.false.` indicates that no such entry is present.

##### Example

```{literalinclude} ../../example/hashmaps/example_hashmaps_key_test.f90
:language: fortran

loading - Returns the ratio of entries to slots

Status

Experimental

Description

Returns the ratio of the number of entries relative to the number of slots in the hash map.

Syntax

value = map % loading(bound) ( )

Class

Pure function

Argument

map (pass) - shall be an expression of class chaining_hashmap_type or open_hashmap_type. It is an intent(in) argument.

Result character

The result will be a default real.

Result value

The result will be the ratio of the number of entries relative to the number of slots in the hash map.

Example

```{literalinclude} ../../example/hashmaps/example_hashmaps_loading.f90 :language: fortran



#### `map_entry` - inserts an entry into the hash map

##### Status

Experimental

##### Description

Inserts an entry into the hash map if it is not already present.

##### Syntax

`call map % ` `map_entry(bound)` `( key[, other, conflict ] )`

##### Class

Subroutine

##### Arguments

`map` (pass): shall be a scalar variable of class
`chaining_hashmap_type` or `open_hashmap_type`. It
is an `intent(inout)` argument. It is the hash map to receive the
entry.

`key`: shall be a of type `key_type` scalar, `character` scalar, `int8` array
or `int32` array. It is an `intent(in)` argument. It is the key for the entry
to be placed in the table.

`other` (optional): shall be a scalar of any type, including derived types.
It is an `intent(in)` argument. If present it is the value to be
associated with the `key`.

`conflict` (optional): shall be a scalar variable of type
`logical`. It is an `intent(out)` argument. If present, a `.true.`
value indicates that an entry with the value of `key` already exists
and the entry was not entered into the map, a `.false.` value indicates
that `key` was not present in the map and the entry was added to the
map. 

* If `key` is already present in `map` and the `conflict` argument has been
provided then the presence of `other` is ignored. If `conflict` has not 
been provided then it routine will error stop.  

##### Example

```{literalinclude} ../../example/hashmaps/example_hashmaps_map_entry.f90
:language: fortran

map_probes - returns the number of hash map probes

Status

Experimental

Description

Returns the total number of table probes on the hash map.

Syntax

result = map % map_probes(bound) ( )

Class

Pure function

Argument

map (pass): shall be a scalar expression of class hashmap_type. It is an intent(in) argument. It is the hash map of interest.

Result character

The result is a scalar integer of kind int_probes.

Result value

The result is the number of probes of map since initialization or rehashing.

Example

```{literalinclude} ../../example/hashmaps/example_hashmaps_probes.f90 :language: fortran



#### `num_slots` - returns the number of hash map slots.

##### Status

Experimental

##### Description

Returns the total number of slots on a hash map

##### Syntax

`result = map % ` `num_slots(bound)` `( )`

##### Class

Pure function

##### Argument

`map`: shall be a scalar expression of class
`hashmap_type`. It is an `intent(in)` argument. It is the
hash map of interest.

##### Result character

The result is a scalar integer of kind `int_index`.

##### Result value

The result is the number of slots in `map`.

##### Example

```{literalinclude} ../../example/hashmaps/example_hashmaps_num_slots.f90
:language: fortran

rehash - changes the hashing function

Status

Experimental

Description

Changes the hashing function for the map entries to that of hasher.

Syntax

call map % rehash(bound) ( hasher )

Class

Subroutine

Arguments

map (pass): shall be a scalar variable of class chaining_hashmap_type or open_hashmap_type. It is an intent(inout) argument. It is the hash map whose hashing method is to be changed.

hasher: shall be a function of interface hasher_fun. It is the hash method to be used by map.

Example

```{literalinclude} ../../example/hashmaps/example_hashmaps_rehash.f90 :language: fortran



#### `remove` - removes an entry from the hash map

##### Status

Experimental

##### Description

Removes an entry from the hash map, `map`.

##### Syntax

`call map % ` `remove(bound)` `( key[, existed ])`

##### Class

Subroutine

##### Arguments

`map` (pass): shall be a scalar variable of class
`chaining_hashmap_type` or `open_hashmap_type`. 
It is an `intent(inout)` argument. It is the hash map with the element 
to be removed.

`key`: shall be a of type `key_type` scalar, `character` scalar, `int8` array
or `int32` array. It is an `intent(in)` argument. It is the `key` identifying 
the entry to be removed.

`existed` (optional): shall be a scalar variable of type default
logical. It is an `intent(out)` argument. If present with the value
`.true.` the entry existed in the map before removal, if `.false.` the
entry was not present to be removed and the map is unchanged. If
absent, the procedure returns with no entry with the given key.

##### Example

```{literalinclude} ../../example/hashmaps/example_hashmaps_remove.f90
:language: fortran

set_other_data - replaces the other data for an entry

Status

Experimental

Description

Replaces the other data in the map for the entry with the key value, key.

Syntax

call map % set_other_data(bound) ( key, other[, exists] )

Class

Subroutine

Arguments

map (pass): shall be a scalar variable of class chaining_hashmap_type or open_hashmap_type. It is an intent(inout) argument. It will be a hash map used to store and access the entry’s data.

key: shall be a of type key_type scalar, character scalar, int8 array or int32 array. It is an intent(in) argument. It is the key to the entry whose other data is to be replaced.

other (optional): shall be a scalar of any type, including derived types. It is an intent(in) argument. If present it is the value to be associated with the key.

exists (optional): shall be a scalar variable of type logical. It is an intent(out) argument. If present with the value .true. an entry with that key existed in the map and its other data was replaced. If exists is .false. the key did not exist and nothing was done.

Example

```{literalinclude} ../../example/hashmaps/example_hashmaps_set_other_data.f90 :language: fortran



#### `slots_bits` - returns the number of bits used to address the hash map slots 

##### Status

Experimental

##### Description

Returns the total number of bits used to address the hash map slots.

##### Syntax

`result = map % ` `slots_bits(bound)` `( )`

##### Class

Pure function

##### Argument

`map` (pass): shall be a scalar expression of class
`hashmap_type`. It is an `intent(in)` argument. It is the
hash map of interest.

##### Result character

The result is a scalar integer of kind `int_index`.

##### Result value

The result is the number of bits used in addressing the slots in `map`.

##### Example

```{literalinclude} ../../example/hashmaps/example_hashmaps_slots_bits.f90
:language: fortran

total_depth - returns the total depth of the hash map entries

Status

Experimental

Description

Returns the total number of one’s based offsets of slot entries from their slot index for a hash map

Syntax

result = map % total_depth ( )

Class

Pure function

Argument

map (pass): shall be a scalar expression of class hashmap_type. It is an intent(in) argument. It is the hash map of interest.

Result character

The result is a scalar integer of kind int_depth.

Result value

The result is the total number of one’s based offsets of slot entries from their slot index the map.

Example

{literalinclude} ../../example/hashmaps/example_hashmaps_total_depth.f90 :language: fortran

This site is open source. Improve this page.