HashMap<K, V>

← Back to Standard Library

Generic hash table with open addressing (linear probing).

Import

use <collections/hashmap>

Overview

HashMap@(K, V) is a hash table that provides fast key-value lookups. It features: - Open addressing: Linear probing collision resolution - Auto-resize: Grows at 0.75 load factor - Power-of-two capacity: Fast indexing via bitwise AND - Type-safe access: .get() returns Maybe@(V) for safe lookups - RAII cleanup: Automatic recursive cleanup of entries

Construction

HashMap.new() -> HashMap@(K, V)

Create empty hash map (initial capacity 16).

let HashMap@(string, i32) ages = HashMap.new()

Methods

.insert(K key, V value) -> ~

Insert or update key-value pair.

ages.insert("Arthur", 42)
ages.insert("Ford", 200)

Note: Automatically resizes at 0.75 load factor.

.get(K key) -> Maybe@(V)

Get value for key.

match ages.get("Arthur"):
    Maybe.Some(age) ->
        println("Arthur is {age}")
    Maybe.None() ->
        println("Not found")

.remove(K key) -> Maybe@(V)

Remove and return value for key.

match ages.remove("Arthur"):
    Maybe.Some(age) ->
        println("Removed age {age}")
    Maybe.None() ->
        println("Key not found")

.contains_key(K key) -> bool

Check if key exists.

if (ages.contains_key("Arthur")):
    println("Arthur exists")

.len() -> i32

Get number of entries.

println("Entries: {ages.len()}")

Iteration

A HashMap can be iterated three ways. Each returns an iterator suitable for a foreach loop. Iteration order is unspecified.

.keys() -> Iterator@(K)

Iterate over the keys.

foreach(name in ages.keys()):
    println(name)

.values() -> Iterator@(V)

Iterate over the values.

foreach(age in ages.values()):
    println(age)

.entries() -> Iterator@(Entry@(K, V))

Iterate over key-value pairs. Each Entry@(K, V) exposes .key and .value fields.

foreach(entry in ages.entries()):
    println("{entry.key} is {entry.value}")

Note

.keys(), .values(), and .entries() accept any receiver whose type resolves, including a fallible getter: foreach(k in get_map()??.keys()) works, and the map it produces is freed at scope exit. This used to require a plain variable name.

.free() -> ~

Clear all entries and reset to capacity 16 (still usable).

ages.free()
ages.insert("Zaphod", 150)  # OK

.rehash() -> ~

Rebuild the map at its current capacity, clearing out tombstones left by removals.

ages.rehash()  # Rebuild, removing tombstones

.debug() -> ~

Print internal state.

ages.debug()

A key or a value of a primitive type or a string prints as println writes it, and a string is quoted. Anything else prints as <value>.

Key Requirements

Keys must implement .hash() -> u64 method. Supported types:

• Primitives: i8, i16, i32, i64, u8, u16, u32, u64, f32, f64, bool
• string
• Structs (with hashable fields)

• Enums (with hashable variant data)

• List@(T) and Own@(T) have a hash of what they hold, but no equality test, so neither is a key today

Not supported: Nested arrays (cannot be hashed), and a HashMap@(K, V) itself. A map has no hash of its own: its buckets carry a state for each slot and the slot order is not the entry order, so a hash over them would answer two values for one set of entries.

Hash Function

The hash function is auto-derived for all types:

• Primitives: FxHash for integers, FNV-1a for strings, normalized floats
• Composites: FNV-1a combining field/element hashes
• Limitation: Nested arrays cannot be hashed

Performance

• insert(): Amortized O(1)
• get(): O(1) average case
• remove(): O(1) average case
• contains_key(): O(1) average case

Implementation Details

• Open addressing with linear probing for collision resolution
• Power-of-two capacities for fast indexing (uses bitwise AND instead of modulo)
• Automatic resize at 0.75 load factor (triggers on insertion)
• .free() recursively destroys all entries and resets to capacity 16
• Supports enum values with primitive/struct fields (automatic variant data cleanup)

Known Limitations

• Storing an owning value (a struct/enum with a dynamic-array field, List@(T), or Own@(T)) as a map value currently crashes at runtime on get/free (issue #140)
• Keys must be hashable (implement .hash() -> u64)
• .rehash() takes no arguments; it rebuilds at the current capacity (cannot resize to a chosen capacity)
• .keys()/.values()/.entries() require the receiver to be a plain variable (no chaining)

Best Practices

• Use .contains_key() before .get() if you only need an existence check
• Call .free() to reclaim memory when clearing large maps
• Use .rehash() to clear tombstones after many removals
• Prefer string keys over complex types for best performance
• Pattern match on .get() results to handle missing keys gracefully

Example Usage

use <collections/hashmap>

fn main() i32:
    let HashMap@(string, i32) scores = HashMap.new()

    # Insert entries
    scores.insert("Alice", 100)
    scores.insert("Bob", 85)
    scores.insert("Charlie", 92)

    # Lookup with pattern matching
    match scores.get("Alice"):
        Maybe.Some(score) ->
            println("Alice scored {score}")
        Maybe.None() ->
            println("Alice not found")

    # Check existence
    if (scores.contains_key("Bob")):
        println("Bob exists in map")

    # Remove entry
    match scores.remove("Charlie"):
        Maybe.Some(score) ->
            println("Removed Charlie with score {score}")
        Maybe.None() ->
            println("Charlie not in map")

    # Debug output
    println("Total entries: {scores.len()}")
    scores.debug()

    return Result.Ok(0)