#HashMap
A mutable hash map based on a Robin Hood hash table.
#How It Works
Entries live in one flat power-of-two array of {psl, hash, key, value}
slots, where psl (probe sequence length) is how far the entry sits from its
ideal slot hash & (capacity - 1). Insertion keeps probe distances short by
letting a "poor" entry (large psl) evict a "rich" one (smaller psl),
which then continues looking for a home — that is the Robin Hood part.
Lookups can stop as soon as they meet a slot whose psl is smaller than the
distance probed so far, so misses are cheap too.
flowchart TD
S["set(k, v)"] --> H["idx = hash & mask, psl = 0"]
H --> C{"entries[idx]?"}
C -->|"same hash and key"| U["update value in place"]
C -->|"occupied, psl ≤ slot's psl"| N["idx = (idx + 1) & mask, psl += 1"] --> C
C -->|"empty, or occupied with psl > slot's psl"| G{"size ≥ capacity / 2?"}
G -->|"yes"| R["double capacity, rehash all, restart"] --> H
G -->|"no, slot was empty"| P["store {psl, hash, k, v}"]
G -->|"no, stealing"| E["swap: evict the richer entry,<br/>keep probing to re-place it"] --> N#Usage
#Create
You can create an empty map using HashMap([]) or construct it from entries using HashMap([...]).
///|
test {
let _map1 = @hashmap.HashMap([("a", 1), ("b", 2)])
let _map2 : @hashmap.HashMap[String, Int] = HashMap([])
}#Set & Get
You can use set() to add a key-value pair to the map, and use get() to get a value.
///|
test {
let map : @hashmap.HashMap[String, Int] = HashMap([])
map.set("a", 1)
@test.assert_eq(map.get("a"), Some(1))
@test.assert_eq(map.get_or_default("a", 0), 1)
@test.assert_eq(map.get_or_default("b", 0), 0)
map.remove("a")
@test.assert_eq(map.contains("a"), false)
}#Remove
You can use remove() to remove a key-value pair.
///|
test {
let map = @hashmap.from_array([("a", 1), ("b", 2), ("c", 3)])
map.remove("a") |> ignore
assert_false(map.contains("a"))
}#Contains
You can use contains() to check whether a key exists.
///|
test {
let map = @hashmap.from_array([("a", 1), ("b", 2), ("c", 3)])
@test.assert_eq(map.contains("a"), true)
@test.assert_eq(map.contains("d"), false)
}#Size & Capacity
You can use length() to get the number of key-value pairs in the map, or capacity() to get the current capacity.
///|
test {
let map = @hashmap.from_array([("a", 1), ("b", 2), ("c", 3)])
@test.assert_eq(map.length(), 3)
@test.assert_eq(map.capacity(), 8)
}Similarly, you can use is_empty() to check whether the map is empty.
///|
test {
let map : @hashmap.HashMap[String, Int] = HashMap([])
@test.assert_eq(map.is_empty(), true)
}#Clear
You can use clear to remove all key-value pairs from the map, but the allocated memory will not change.
///|
test {
let map = @hashmap.from_array([("a", 1), ("b", 2), ("c", 3)])
map.clear()
@test.assert_eq(map.is_empty(), true)
}#Iteration
You can use each() or eachi() to iterate through all key-value pairs.
///|
test {
let map = @hashmap.from_array([("a", 1), ("b", 2), ("c", 3)])
let arr = []
map.each((k, v) => arr.push((k, v)))
let arr2 = []
map.eachi((i, k, v) => arr2.push((i, k, v)))
}Or use iter(), keys(), or values() to get iterators:
///|
test {
let map = @hashmap.from_array([("a", 1)])
let _iter = map.iter()
let _keys = map.keys()
let _vals = map.values()
}#Get or Initialize
Use get_or_init() to get a value or initialize it if missing:
///|
test {
let map : @hashmap.HashMap[String, Int] = HashMap([])
let val = map.get_or_init("key", () => 42)
@test.assert_eq(val, 42)
@test.assert_eq(map.get("key"), Some(42))
}#Transform and Filter
Use map() to transform values and retain() to filter in place:
///|
test {
let map = @hashmap.from_array([(1, "a"), (2, "b")])
let mapped = map.map((k, _v) => k * 10)
@test.assert_eq(mapped.get(1), Some(10))
let map2 = @hashmap.from_array([("a", 1), ("b", 2), ("c", 3)])
map2.retain((_k, v) => v > 1)
@test.assert_eq(map2.contains("a"), false)
@test.assert_eq(map2.contains("b"), true)
}#Index Access
Use subscript syntax map[key] for direct access. Panics if the key is not found.
///|
test {
let map = @hashmap.from_array([("x", 10), ("y", 20)])
@test.assert_eq(map["x"], 10)
map["z"] = 30
@test.assert_eq(map["z"], 30)
}#Contains Key-Value
contains_kv() checks whether a specific key-value pair exists (not just the key).
///|
test {
let map = @hashmap.from_array([("a", 1), ("b", 2)])
@test.assert_eq(map.contains_kv("a", 1), true)
@test.assert_eq(map.contains_kv("a", 99), false)
}#Copy
copy() creates a shallow clone.
///|
test {
let map = @hashmap.from_array([("a", 1)])
let cloned = map.copy()
cloned.set("b", 2)
@test.assert_eq(map.contains("b"), false) // original unchanged
}#From Iterator
///|
test {
let map = @hashmap.from_iter(("a", 1), ("b", 2))
@test.assert_eq(map.length(), 2)
}#Merging
merge() returns a new map combining both. merge_in_place() mutates the receiver. On key conflicts, the right map's value wins.
///|
test {
let m1 = @hashmap.from_array([("a", 1)])
let m2 = @hashmap.from_array([("b", 2)])
let merged = m1.merge(m2)
@test.assert_eq(merged.get("a"), Some(1))
@test.assert_eq(merged.get("b"), Some(2))
// merge_in_place
let m3 = @hashmap.from_array([("x", 1)])
let m4 = @hashmap.from_array([("y", 2)])
m3.merge_in_place(m4)
@test.assert_eq(m3.contains("y"), true)
}HashMap
type HashMap[K, V]Mutable hash map, not thread safe.
Example
test {
let map = @hashmap.HashMap([(3, "three"), (8, "eight"), (1, "one")])
@test.assert_eq(map.get(2), None)
@test.assert_eq(map.get(3), Some("three"))
map.set(3, "updated")
@test.assert_eq(map.get(3), Some("updated"))
}fn[V : FromJson] from_json(json : Json, path : JsonPath) -> HashMap[String, V] raise JsonDecodeErrorDecodes a HashMap[String, V] from a JSON object.
Each key in the JSON object becomes a String key in the map, and each
value is decoded using V's FromJson implementation.
Example:
test {
let m : @hashmap.HashMap[String, Int] = @json.from_json({ "a": 1, "b": 2 })
debug_inspect(m.get("a"), content="Some(1)")
debug_inspect(m.get("b"), content="Some(2)")
}HashMap::HashMap
Creates a new hash map from an array of key-value pairs. Pairs with duplicate
keys will keep the latest value, overwriting the previous ones.
The optional capacity is treated as a minimum initial capacity and will be
rounded up to the smallest power of 2 that can hold the requested capacity.
Parameters:
- arr : An array of key-value tuples. Each tuple contains a hashable and comparable key of type K, and an associated value of type V.
Returns a new hash map containing all the key-value pairs from the input
array.
Example:
test {
let arr : ReadOnlyArray[(Int, String)] = [(1, "one"), (2, "two"), (1, "ONE")]
let map = @hashmap.HashMap(arr)
debug_inspect(map.get(1), content="Some(\"ONE\")")
debug_inspect(map.get(2), content="Some(\"two\")")
}HashMap::at
Retrieves the value associated with a given key in the hash map.
Parameters:
- self : The hash map to search in.
- key : The key to look up in the map.
Returns value if the key exists in the map, panic otherwise.
Example:
test {
let map = @hashmap.from_array([("key", 42)])
inspect(map["key"], content="42")
}HashMap::capacity
Returns the current capacity of the hash map, that is, the length of its
internal storage array. The map grows once it is half full, so it can hold
at most capacity / 2 key-value pairs before it reallocates.
Parameters:
- map : The hash map whose capacity is to be queried.
Returns the length of the hash map's internal storage array.
Example:
test {
let map : @hashmap.HashMap[Int, String] = HashMap([], capacity=16)
inspect(map.capacity(), content="16")
}HashMap::clear
Removes all key-value pairs from the map while retaining the allocated
capacity. After calling this method, the size of the map will be zero but the
capacity remains unchanged.
Parameters:
- self : The hash map to be cleared.
Example:
test {
let map = @hashmap.from_array([("a", 1), ("b", 2)])
map.clear()
inspect(map.length(), content="0")
debug_inspect(map.get("a"), content="None")
}HashMap::contains
Checks if a key exists in the hash map.
Parameters:
- self : The hash map to search in.
- key : The key to look for in the hash map.
Returns true if the key exists in the hash map, false otherwise.
Example:
test {
let map = @hashmap.from_array([("a", 1), ("b", 2)])
inspect(map.contains("a"), content="true")
inspect(map.contains("c"), content="false")
}HashMap::contains_kv
Checks if a map contains a specific key-value pair.
Parameters:
- map : A map of type @hashmap.HashMap[K, V] to search in.
- key : The key to look up in the map.
- value : The value to be compared with the value associated with the key.
Returns true if the map contains the specified key and its associated value
equals the given value, false otherwise.
Example:
test {
let map = @hashmap.HashMap([])
map.set("a", 1)
map.set("b", 2)
inspect(map.contains_kv("a", 1), content="true")
inspect(map.contains_kv("a", 2), content="false")
inspect(map.contains_kv("c", 3), content="false")
}HashMap::copy
Copy the map, creating a new map with the same key-value pairs.
HashMap::each
Iterates over all key-value pairs in the hash map and applies the given
function to each pair.
Parameters:
- map : The hash map to iterate over.
- action : A function that takes a key and a value as arguments and performs some action. The function should not return any value.
Example:
test {
let map = @hashmap.from_array([(1, "one"), (2, "two")])
let array = []
map.each((k, v) => array.push((k, v)))
array.sort()
debug_inspect(
array,
content=(
#|[(1, "one"), (2, "two")]
),
)
}HashMap::eachi
Iterates over all key-value pairs in the map with their index, applying the
given function to each element. The index starts from 0 and only counts
non-empty entries.
Notice that the order of iteration is not guaranteed.
Parameters:
- self : The hash map to iterate over.
- callback : A function that takes three arguments:
- An integer representing the index of the current key-value pair
- The key of the current entry
- The value of the current entry
HashMap::equal
HashMap::from_iter
Creates a new hash map from an iterator of key-value pairs.
Parameters:
- iter : An iterator that yields key-value pairs. The key type must implement both Hash and Eq traits.
Returns a new hash map containing all key-value pairs from the iterator. If
the iterator yields multiple pairs with the same key, the later value will
overwrite the earlier one.
Example:
test {
let iter = (1, "one"), (2, "two")
let map = @hashmap.from_iter(iter)
debug_inspect(map.get(1), content="Some(\"one\")")
debug_inspect(map.get(2), content="Some(\"two\")")
}HashMap::get
Retrieves the value associated with a given key in the hash map.
Parameters:
- self : The hash map to search in.
- key : The key to look up in the map.
Returns Some(value) if the key exists in the map, None otherwise.
Example:
test {
let map = @hashmap.from_array([("key", 42)])
debug_inspect(map.get("key"), content="Some(42)")
debug_inspect(map.get("nonexistent"), content="None")
}HashMap::get_from_bytes
Retrieves the value associated with a BytesView key in a hash map with
Bytes keys.
This allows efficient lookups using a BytesView (e.g. a sub-slice of a
larger byte buffer) without allocating a fresh Bytes.
Returns Some(value) if a matching key exists in the map, None otherwise.
Example:
test {
let map = @hashmap.from_array([(b"hello", 1), (b"world", 2)])
let bytes = b"prefix_hello_suffix"
let view = bytes[7:12] // view of "hello"
@debug.debug_inspect(map.get_from_bytes(view), content="Some(1)")
}HashMap::get_from_string
Retrieves the value associated with a StringView key in a hash map with
String keys.
This allows efficient lookups using a StringView (e.g. a substring of a
larger string) without allocating a fresh String.
Returns Some(value) if a matching key exists in the map, None otherwise.
Example:
test {
let map = @hashmap.from_array([("hello", 1), ("world", 2)])
let str = "say hello to everyone"
let view = str.view(start_offset=4, end_offset=9) // view of "hello"
@debug.debug_inspect(map.get_from_string(view), content="Some(1)")
}HashMap::get_or_default
Gets the value associated with a given key from the hash map. If the key
doesn't exist, returns the provided default value instead.
Parameters:
- map : The hash map to retrieve the value from.
- key : The key to look up in the map.
- default : The value to return if the key is not found in the map.
Returns the value associated with the key if it exists, otherwise returns the
default value.
Example:
test {
let map = @hashmap.from_array([("a", 1), ("b", 2)])
inspect(map.get_or_default("a", 0), content="1")
inspect(map.get_or_default("c", 0), content="0")
}HashMap::get_or_init
Gets the value associated with the given key. If the key doesn't exist in the
map, initializes it with the result of calling the provided initialization
function.
Parameters:
- self : The hash map.
- key : The key to look up in the map.
- init : A function that takes no arguments and returns a value to be associated with the key if it doesn't exist.
Returns the value associated with the key, either existing or newly
initialized.
Example:
test {
let map : @hashmap.HashMap[String, Int] = HashMap([])
let value = map.get_or_init("key", () => 42)
inspect(value, content="42")
debug_inspect(map.get("key"), content="Some(42)")
}HashMap::is_empty
Returns whether the hash map contains no key-value pairs.
Parameters:
- map : The hash map to check.
Returns true if the hash map contains no key-value pairs, false
otherwise.
Example:
test {
let map : @hashmap.HashMap[String, Int] = HashMap([])
inspect(map.is_empty(), content="true")
map.set("key", 42)
inspect(map.is_empty(), content="false")
}HashMap::iter
Returns an iterator over the key-value pairs in the map.
Parameters:
- map : The hash map to iterate over.
Returns an iterator that yields tuples of (key, value) for each entry in
the map, in unspecified order.
Example:
test {
let map = @hashmap.from_array([(1, "one"), (2, "two")])
let pairs = map.iter().to_array()
inspect(pairs.length(), content="2")
inspect(pairs.contains((1, "one")), content="true")
inspect(pairs.contains((2, "two")), content="true")
}HashMap::iter2
Returns an iterator over the key-value pairs in the map.
Parameters:
- map : The hash map to iterate over.
Returns an iterator that yields tuples of (key, value) for each entry in
the map, in unspecified order.
This is mainly used for for _, _ in .. loops.
HashMap::keys
Returns an iterator over all keys in the hash map.
Parameters:
- self : The hash map to iterate over.
Returns an iterator that yields each key in the hash map in unspecified order.
The keys are yielded in the same order as they appear in the internal storage.
Example:
test {
let map = @hashmap.from_array([(1, "one"), (2, "two"), (3, "three")])
let keys = map.keys().to_array()
inspect(keys.length(), content="3")
inspect(keys.contains(1), content="true")
inspect(keys.contains(2), content="true")
inspect(keys.contains(3), content="true")
}HashMap::length
Returns the number of key-value pairs currently stored in the hash map.
Parameters:
- self : The hash map to get the size from.
Returns the number of key-value pairs in the hash map.
Example:
test {
let map = @hashmap.from_array([("a", 1), ("b", 2), ("c", 3)])
inspect(map.length(), content="3")
}HashMap::map
Applies a function to each key-value pair in the map and
returns a new map with the results, using the original keys.
HashMap::merge
Merges two maps into a new map. Returns a new map containing all key-value
pairs from both maps. When both maps contain the same key, the value from
other takes precedence.
This is a pure operation - it does not modify either of the input maps.
Parameters:
- self : The first map.
- other : The second map whose values take precedence in case of key conflicts.
Returns a new hash map containing all entries from both maps.
Example:
test {
let map1 = @hashmap.from_array([("a", 1), ("b", 2)])
let map2 = @hashmap.from_array([("b", 3), ("c", 4)])
let merged = map1.merge(map2).to_array()
merged.sort()
@json.json_inspect(merged, content=[["a", 1], ["b", 3], ["c", 4]])
}HashMap::merge_in_place
Merges another map into this map in-place. Updates the current map by adding
all key-value pairs from other. When both maps contain the same key, the
value from other overwrites the value in this map.
This is a mutating operation - it modifies the receiver map.
Parameters:
- self : The map to be modified.
- other : The map whose entries will be added to self.
Example:
test {
let map1 = @hashmap.from_array([("a", 1), ("b", 2)])
let map2 = @hashmap.from_array([("b", 3), ("c", 4)])
map1.merge_in_place(map2)
let merged = map1.to_array()
merged.sort()
@json.json_inspect(merged, content=[["a", 1], ["b", 3], ["c", 4]])
}HashMap::new
Creates a new empty hash map with the specified initial capacity. The actual
capacity will be rounded up to the next power of 2 that is greater than or
equal to the requested capacity.
Deprecated: use HashMap([], capacity=...) instead.
HashMap::remove
Removes the entry for the specified key from the hash map. If the key exists
in the map, removes its entry and adjusts the probe sequence length (PSL) of
subsequent entries to maintain the Robin Hood hashing invariant. If the key
does not exist, the map remains unchanged.
Parameters:
- self : The hash map to remove the entry from.
- key : The key to remove from the map.
Example:
test {
let map = @hashmap.from_array([("a", 1), ("b", 2)])
map.remove("a")
debug_inspect(map.get("a"), content="None")
inspect(map.length(), content="1")
}HashMap::retain
Retains only the key-value pairs that satisfy the given predicate function.
This method modifies the hash map in-place, removing all entries for which
the predicate returns false.
Parameters:
- self : The hash map to be filtered.
- predicate : A function that takes a key and value as arguments and returns true if the key-value pair should be kept, false if it should be removed.
Example:
test {
let map = @hashmap.from_array([("a", 1), ("b", 2), ("c", 3), ("d", 4)])
map.retain((_k, v) => v % 2 == 0) // Keep only even values
inspect(map.length(), content="2")
debug_inspect(map.get("a"), content="None")
debug_inspect(map.get("b"), content="Some(2)")
debug_inspect(map.get("c"), content="None")
debug_inspect(map.get("d"), content="Some(4)")
}HashMap::set
Sets a key-value pair into the hash map. If the key already exists, updates
its value. If the hash map is near full capacity (>= 50%), automatically
grows the internal storage to accommodate more entries.
Parameters:
- map : The hash map to modify.
- key : The key to insert or update. Must implement Hash and Eq traits.
- value : The value to associate with the key.
Example:
test {
let map : @hashmap.HashMap[String, Int] = HashMap([])
map.set("key", 42)
debug_inspect(map.get("key"), content="Some(42)")
map.set("key", 24) // update existing key
debug_inspect(map.get("key"), content="Some(24)")
}HashMap::to_array
Converts the hash map into an array of key-value pairs. The order of elements
in the resulting array follows the internal storage order of the hash map.
Parameters:
- self : The hash map to be converted.
Returns an array containing tuples of key-value pairs from the hash map.
Example:
test {
let map = @hashmap.from_array([(1, "one"), (2, "two")])
let arr = map.to_array()
arr.sort()
debug_inspect(
arr,
content=(
#|[(1, "one"), (2, "two")]
),
)
}HashMap::update
Updates a value in the map based on the existing value.
This method allows you to conditionally update, insert, or remove a key-value pair
based on whether the key already exists in the map. The provided function f is
called with Some(current_value) if the key exists, or None if it doesn't.
Parameters:
- self : The map to update.
- key : The key to update.
- f : A function that takes the current value (wrapped in Option) and returns the new value (wrapped in Option). Returning None will remove the key-value pair from the map.
Behavior:
- If the key exists and f returns Some(new_value), the value is updated.
- If the key exists and f returns None, the key-value pair is removed.
- If the key doesn't exist and f returns Some(new_value), a new pair is inserted.
- If the key doesn't exist and f returns None, no operation is performed.
Example:
test {
let map : @hashmap.HashMap[String, Int] = HashMap([("a", 1), ("b", 2)])
// Update existing value
map.update("a", fn(v) {
match v {
Some(x) => Some(x + 10)
None => Some(0)
}
})
debug_inspect(map.get("a"), content="Some(11)")
// Insert new value
map.update("c", fn(v) {
match v {
Some(x) => Some(x)
None => Some(3)
}
})
debug_inspect(map.get("c"), content="Some(3)")
// Remove existing value
map.update("b", fn(_) { None })
debug_inspect(map.get("b"), content="None")
}HashMap::update_or_default
Inserts default for key if it is absent, otherwise replaces the existing
value with f(existing). The pairing of an eager default value with a
modifier function lets the canonical counter pattern read literally:
test {
let counts : @hashmap.HashMap[String, Int] = HashMap([])
counts.update_or_default("a", 1, x => x + 1)
counts.update_or_default("a", 1, x => x + 1)
counts.update_or_default("b", 1, x => x + 1)
debug_inspect(counts.get("a"), content="Some(2)")
debug_inspect(counts.get("b"), content="Some(1)")
}Note: f is not applied to default on first insertion — default is
the value stored when the key is absent. This mirrors Java's Map.merge
and Rust's Entry::and_modify(f).or_insert(default).
HashMap::values
Returns an iterator over all values in the hash map.
Parameters:
- self : The hash map to iterate over.
Returns an iterator that yields each value in the hash map in unspecified order.
The values are yielded in the same order as they appear in the internal storage.
Example:
test {
let map = @hashmap.from_array([("a", 1), ("b", 2), ("c", 3)])
let values = map.values().to_array()
inspect(values.length(), content="3")
inspect(values.contains(1), content="true")
inspect(values.contains(2), content="true")
inspect(values.contains(3), content="true")
}Install
Installed by default
corestandard library
Apache-2.0
Updated 13 days ago