hashmap

The hashmap module provides a high-performance generic hash table implementation using the Swiss table algorithm. It maps keys of type K to values of type V with excellent cache locality and lookup performance.

Swiss tables use control bytes (metadata) to quickly skip over empty slots and find matching entries without loading the actual key-value data, improving cache efficiency.

import "conjure/hashmap" as hm

var scores = hm.new[i32, i32]()
defer scores.free()

scores.set(1, 100)
scores.set(2, 85)

var ptr = scores.getPtr(1)
if ptr != null {
    io.println("Score: #{*ptr}")  // 100
}

#Creating Hash Maps

Create a new hash map with default capacity (16 entries):

import "conjure/hashmap" as hm

var map = hm.new[string, i32]()
defer map.free()

Or specify initial capacity if you know approximately how many entries you’ll store:

var largeMap = hm.new[i32, i32](1000)
defer hm.free(&largeMap)

Always use defer hm.free(&map) to ensure memory is cleaned up.

#Setting and Getting Values

Insert or update a key-value pair:

hm.set(&map, "answer", 42)
hm.set(&map, "answer", 100)  // Updates existing value

Safely retrieve values using getPtr:

var ptr = hm.getPtr(&map, "answer")
if ptr != null {
    io.println("Value: #{*ptr}")
} else {
    io.println("Key not found")
}

Check if a key exists:

if hm.has(&map, "answer") {
    io.println("Key exists!")
}

#Removing Entries

Remove a single entry:

var removed = hm.remove(&map, "key")
if removed {
    io.println("Entry removed")
}

Clear all entries while keeping allocated capacity:

hm.clear(&map)  // map.len is now 0

#Supported Key Types

The following types work well as hash map keys:

• Integers: i8, i16, i32, i64, u8, u16, u32, u64, usize
• Floats: f32, f64 (use with caution due to precision issues)
• Booleans: bool
• Strings: string
• Custom types: Via byte-wise hashing (limited support)

#Example: Word Frequency Counter

import "conjure/hashmap" as hm

func countWords(text string) {
    var counts = hm.new[string, i32]()
    defer hm.free(&counts)

    // Split and count words (simplified)
    var words = strings.split(text, " ")
    for word in words {
        var ptr = hm.getPtr(&counts, word)
        if ptr != null {
            *ptr += 1  // Increment count
        } else {
            hm.set(&counts, word, 1)  // First occurrence
        }
    }

    // Print results
    // (iteration support coming in future version)
}

#Example: Caching Results

import "conjure/hashmap" as hm

var cache = hm.new[i32, i32]()
defer hm.free(&cache)

func fibonacci(n i32) i32 {
    // Check cache first
    var cached = hm.getPtr(&cache, n)
    if cached != null {
        return *cached
    }

    // Compute and cache
    var result i32 = 0
    if n <= 1 {
        result = n
    } else {
        result = fibonacci(n - 1) + fibonacci(n - 2)
    }

    hm.set(&cache, n, result)
    return result
}

#Performance

HashMap operations have the following time complexity:

* Worst case for set is O(n) only when resizing occurs. Amortized over many insertions, it’s O(1).

#Best Practices

Always free your maps using defer:

import "conjure/hashmap" as hm

var map = hm.new[string, i32]()
defer hm.free(&map)

Use safe lookups with getPtr instead of checking existence first:

// Good - single lookup
var ptr = hm.getPtr(&map, key)
if ptr != null {
    process(*ptr)
}

// Less efficient - double lookup
if hm.has(&map, key) {
    var ptr = hm.getPtr(&map, key)
    process(*ptr)
}

Pre-allocate when size is known to avoid resizing overhead:

var map = hm.new[i32, i32](expectedSize)

Clear instead of recreating when reusing a map:

var frameData = hm.new[string, i32]()
defer hm.free(&frameData)

while gameRunning {
    hm.clear(&frameData)  // Reuse for next frame
    // ... populate and use frameData ...
}

#Implementation Details

The HashMap uses the Swiss table algorithm:

1. Control bytes: Each slot has a metadata byte storing:

   • Whether the slot is empty, deleted, or occupied
   • The top 7 bits of the hash (H2) for quick filtering

2. Linear probing: Collisions are resolved by probing linearly to find the next available slot

3. Automatic resizing: When load factor exceeds 75%, capacity doubles and all entries are rehashed

4. Byte-wise hashing: Uses FNV-1a 64-bit hash for all key types

5. Power-of-2 capacity: Always maintains capacity as a power of 2 for fast modulo using bitwise AND

#Limitations

• No iteration: Current version doesn’t support iterating over entries (planned for future)
• No custom hash functions: Uses byte-wise hashing for all types (trait support planned)
• No shrinking: Maps grow automatically but don’t shrink when entries are removed
• Not thread-safe: Use external synchronization for concurrent access

#See Also

• hash - Hash functions used internally
• list - Dynamic array implementation
• memory - Low-level memory management