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]
Create an array with space for prealloc elements without triggering a resize. Defaults to 6.
new ref create( prealloc: USize val = 6) : HashMap[K, V, H] ref^
The number of items in the map.
fun box size() : USize val
The available space in the map. Resize will happen when size / space >= 0.75.
fun box space() : USize val
Gets a value from the map. Raises an error if no such item exists.
fun box apply( key: box->K!) : this->V ?
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)
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 and ignores the provided function.
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, {(current, provided) => current + provided })
This changes the value associated with "test" to 6.
If we have not yet added the key "new-key" to the map and we call
m.upsert("new-key", 4, {(current, provided) => current + provided })
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
Set a value in the map. Returns the new value, allowing reuse.
fun ref insert( key: K, value: V) : V!
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
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^) ?
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
Checks whether the map contains the key k
fun box contains( k: box->K!) : Bool val
Add K, V pairs from the iterator to the map.
fun ref concat( iter: Iterator[(K^ , V^)] ref) : None val
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^
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^
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 = call) : USize val ?
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) ?
Minimise the memory used for the map.
fun ref compact() : None val
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^
Remove all entries.
fun ref clear() : None val
Return an iterator over the keys.
fun box keys() : MapKeys[K, V, H, this->HashMap[K, V, H] ref] ref^
Return an iterator over the values.
fun box values() : MapValues[K, V, H, this->HashMap[K, V, H] ref] ref^
Return an iterator over the keys and values.
fun box pairs() : MapPairs[K, V, H, this->HashMap[K, V, H] ref] ref^
Return a slot number and whether or not it's currently occupied.
fun box _search( key: box->K!) : (USize val , Bool val)
Change the available space.
fun ref _resize( len: USize val) : None val
© 2016-2018, The Pony Developers
© 2014-2015, Causality Ltd.
Licensed under the BSD 2-Clause License.
https://stdlib.ponylang.io/collections-HashMap