Skip to content

HashMap[K: K, V: V, H: HashFunction[K] val]

[Source]

A quadratic probing hash map. Resize occurs at a load factor of 0.75. A resized map has 2 times the space. The hash function can be plugged in to the type to create different kinds of maps.

class ref HashMap[K: K, V: V, H: HashFunction[K] val]

Constructors

create

[Source]

Create an array with space for prealloc elements without triggering a resize. Defaults to 6.

new ref create(
  prealloc: USize val = seq)
: HashMap[K, V, H] ref^

Parameters

  • prealloc: USize val = seq

Returns


Public Functions

size

[Source]

The number of items in the map.

fun box size()
: USize val

Returns


space

[Source]

The available space in the map. Resize will happen when size / space >= 0.75.

fun box space()
: USize val

Returns


apply

[Source]

Gets a value from the map. Raises an error if no such item exists.

fun box apply(
  key: box->K!)
: this->V ?

Parameters

  • key: box->K!

Returns

  • this->V ?

update

[Source]

Sets a value in the map. Returns the old value if there was one, otherwise returns None. If there was no previous value, this may trigger a resize.

fun ref update(
  key: K,
  value: V)
: (V^ | None val)

Parameters

  • key: K
  • value: V

Returns


upsert

[Source]

Combines a provided value with the current value for the provided key using the provided function. If the provided key has not been added to the map yet, it sets its value to the provided value.

As a simple example, say we had a map with I64 values and we wanted to add 4 to the current value for key "test", which let's say is currently 2. We call

m.upsert("test", 4, {(x, y) => x - y })

This changes the value associated with "test" to -2.

If we have not yet added the key "new-key" to the map and we call

m.upsert("new-key", 4, {(x, y) => x - y })

then "new-key" is added to the map with a value of -4.

Returns the value that we set the key to

fun ref upsert(
  key: K,
  value: V,
  f: {(V, V): V^}[K, V, H] box)
: V ?

Parameters

  • key: K
  • value: V
  • f: {(V, V): V^}[K, V, H] box

Returns

  • V ?

insert

[Source]

Set a value in the map. Returns the new value, allowing reuse.

fun ref insert(
  key: K,
  value: V)
: V ?

Parameters

  • key: K
  • value: V

Returns

  • V ?

insert_if_absent

[Source]

Set a value in the map if the key doesn't already exist in the Map. Saves an extra lookup when doing a pattern like:

if not my_map.contains(my_key) then
  my_map(my_key) = my_value
end

Returns the value, the same as insert, allowing 'insert_if_absent' to be used as a drop-in replacement for insert.

fun ref insert_if_absent(
  key: K,
  value: V)
: V ?

Parameters

  • key: K
  • value: V

Returns

  • V ?

remove

[Source]

Delete a value from the map and return it. Raises an error if there was no value for the given key.

fun ref remove(
  key: box->K!)
: (K^ , V^) ?

Parameters

  • key: box->K!

Returns

  • (K^ , V^) ?

get_or_else

[Source]

Get the value associated with provided key if present. Otherwise, return the provided alternate value.

fun box get_or_else(
  key: box->K!,
  alt: this->V)
: this->V

Parameters

  • key: box->K!
  • alt: this->V

Returns

  • this->V

contains

[Source]

Checks whether the map contains the key k

fun box contains(
  k: box->K!)
: Bool val

Parameters

  • k: box->K!

Returns


concat

[Source]

Add K, V pairs from the iterator to the map.

fun ref concat(
  iter: Iterator[(K^ , V^)] ref)
: None val

Parameters

Returns


add[optional H2: HashFunction[this->K!] val]

[Source]

This with the new (key, value) mapping.

fun box add[optional H2: HashFunction[this->K!] val](
  key: this->K!,
  value: this->V!)
: HashMap[this->K!, this->V!, H2] ref^

Parameters

  • key: this->K!
  • value: this->V!

Returns

  • HashMap[this->K!, this->V!, H2] ref^

sub[optional H2: HashFunction[this->K!] val]

[Source]

This without the given key.

fun box sub[optional H2: HashFunction[this->K!] val](
  key: this->K!,
  value: this->V!)
: HashMap[this->K!, this->V!, H2] ref^

Parameters

  • key: this->K!
  • value: this->V!

Returns

  • HashMap[this->K!, this->V!, H2] ref^

next_index

[Source]

Given an index, return the next index that has a populated key and value. Raise an error if there is no next populated index.

fun box next_index(
  prev: USize val = seq)
: USize val ?

Parameters

Returns


index

[Source]

Returns the key and value at a given index. Raise an error if the index is not populated.

fun box index(
  i: USize val)
: (this->K , this->V) ?

Parameters

Returns

  • (this->K , this->V) ?

compact

[Source]

Minimise the memory used for the map.

fun ref compact()
: None val

Returns


clone[optional H2: HashFunction[this->K!] val]

[Source]

Create a clone. The key and value types may be different due to aliasing and viewpoint adaptation.

fun box clone[optional H2: HashFunction[this->K!] val]()
: HashMap[this->K!, this->V!, H2] ref^

Returns

  • HashMap[this->K!, this->V!, H2] ref^

clear

[Source]

Remove all entries.

fun ref clear()
: None val

Returns


keys

[Source]

Return an iterator over the keys.

fun box keys()
: MapKeys[K, V, H, this->HashMap[K, V, H] ref] ref^

Returns


values

[Source]

Return an iterator over the values.

fun box values()
: MapValues[K, V, H, this->HashMap[K, V, H] ref] ref^

Returns


pairs

[Source]

Return an iterator over the keys and values.

fun box pairs()
: MapPairs[K, V, H, this->HashMap[K, V, H] ref] ref^

Returns


Private Functions

[Source]

Return a slot number and whether or not it's currently occupied.

fun box _search(
  key: box->K!)
: (USize val , Bool val)

Parameters

  • key: box->K!

Returns


_resize

[Source]

Change the available space.

fun ref _resize(
  len: USize val)
: None val

Parameters

Returns