Jai High-Performance Hash Map

This module provides a fixed-size, compile-time configurable hash map utilizing the Robin Hood Hashing collision resolution strategy for superior performance and minimal variance in lookup times.

Data Structure

The map is defined as a template struct, allowing the size to be fixed at compile time.

Hash_Map :: struct ($K: Type, $V: Type, $C: s64 = 128) { ... }

$K: Key type (must be hashable by XXH3.hash and support == comparison: ints, enums, strings).
$V: Value type.
$C: Capacity. Must be a power of two. (e.g., 64, 128, 256).

API Reference

Function	Signature	Description
insert	(map: *Hash_Map, key: K, value: V) -> bool	Inserts or updates a key/value pair. Returns true on success, false if the map is full (and cannot swap any elements).
get	(map: Hash_Map, key: K) -> V	Retrieves a pointer to the value associated with the key. Returns null if the key is not found.
delete	(map: *Hash_Map, key: K) -> bool	Locates and marks the key's slot as DELETED (tombstone). Returns true if the key was found and deleted.
for loop	for value, key: map { ... }	Provides a clean iteration over all occupied (non-empty and non-deleted) key-value pairs in the map.

Collision Resolution: Robin Hood Hashing

The map uses Robin Hood Hashing, which aims to minimize the variance of the Probe Sequence Length (PSL). When a collision occurs, if the incoming element is "richer" (has a higher PSL) than the element already occupying the slot, the map swaps them. This ensures the longest probe sequence is kept as short as possible, improving worst-case lookup performance.

Example

#import,file "Hash_Map.jai";
#import "Basic";

main :: () {
    // Capacity fixed at 256 for this map
    map: Hash_Map(string, float, 256);

    // Insert
    assert(insert(*map, "PI", 3.14159));
    assert(insert(*map, "E", 2.71828));

    // Get
    pi_ptr := get(*map, "PI");
    if pi_ptr print("PI value: %\n", pi_ptr.*); // Prints 3.14159

    // Delete
    assert(delete(*map, "E"));

    // Iterate
    print("\nRemaining items:\n");
    for map print("Key: [%] Value: %\n", it_index, it);
}