Data.HashMap.Mutable.Linear.Internal

When to trigger a resize.

A high load factor usually is not desirable because it makes operations do more probes. A very low one is also not desirable since there're some operations which take time relative to the capacity.

This should be between (0, 1)

The value 0.75 is what Java uses: https://docs.oracle.com/javase/10/docs/api/java/util/HashMap.html

When resizing, the capacity will be multiplied by this amount.

This should be greater than one.

A mutable hashmap with a linear interface.

An array of Robin values

Each cell is Nothing if empty and is a RobinVal with the correct PSL otherwise.

Robin values are triples of the key, value and PSL (the probe sequence length).

A probe sequence length

At minimum, we need to store hashable and identifiable keys

The results of searching for where to insert a key.

PSL's on the constructors are the probes spent from the query, this might be different than PSL's of the cell at the returned index (in case of IndexToSwap constructor).

Run a computation with an empty HashMap with given capacity.

Create an empty HashMap, using another as a uniqueness proof.

Run a computation with an HashMap containing given key-value pairs.

The most general modification function; which can insert, update or delete a value of the key, while collecting an effect in the form of an arbitrary Functor.

A general modification function; which can insert, update or delete a value of the key. See alterF, for an even more general function.

Insert a key value pair to a HashMap. It overwrites the previous value if it exists.

Delete a key from a HashMap. Does nothing if the key does not exist.

insert (in the provided order) the given key-value pairs to the hashmap.

A version of fmap which can throw out the elements.

Complexity: O(capacity hm)

Same as mapMaybe, but also has access to the keys.

Complexity: O(capacity hm)

Complexity: O(capacity hm)

Union of two maps using the provided function on conflicts.

Complexity: O(min(capacity hm1, capacity hm2)

A right-biased union.

Complexity: O(min(capacity hm1, capacity hm2)

Intersection of two maps with the provided combine function.

Complexity: O(min(capacity hm1, capacity hm2)

Reduce the HashMap capacity to decrease wasted memory. Returns a semantically identical HashMap.

This is only useful after a lot of deletes.

Complexity: O(capacity hm)

Number of key-value pairs inside the HashMap

Maximum number of elements the HashMap can store without resizing. However, for performance reasons, the HashMap might be before full.

Use shrinkToFit to reduce the wasted space.

Look up a value from a HashMap.

Check if the given key exists.

Converts a HashMap to a lazy list.

Given a key, psl of the probe so far, current unread index, and a full hashmap, return a probe result: the place the key already exists, a place to swap from, or an unfilled cell to write over.

Try to insert at a given index with a given PSL. So the probing starts from the given index (with the given PSL).

Shift all cells with PSLs > 0 in a continuous segment following the deleted cell, backwards by one and decrement their PSLs.

Makes sure that the map is not exceeding its utilization threshold (constMaxUtilization), resizes (constGrowthFactor) if necessary.

Resizes the HashMap to given capacity.

Invariant: Given capacity should be greater than the size, this is not checked.