hashmap

Hash map mapping i64 keys to i64 values. Uses open addressing with linear probing and power-of-2 capacity. Automatic rehashing at 70% load factor. No external dependencies.

Also provides string-keyed convenience functions (map_puts, map_gets, map_hass) that hash byte buffers with djb2 and use the hash as the integer key.

Memory Layout

Each map is a pointer to a 5-word header (&i64):

Usage

import hashmap

fn main() {
    let m = map_new(64)

    // Integer keys
    map_put(m, 42, 100)
    map_put(m, 99, 200)
    print(map_get(m, 42))       // 100
    print(map_has(m, 99))       // 1

    // String keys
    map_puts(m, "name", 4, 1001)
    map_puts(m, "age", 3, 30)
    print(map_gets(m, "name", 4))   // 1001
    print(map_hass(m, "age", 3))    // 1

    // Delete
    map_del(m, 42)
    print(map_has(m, 42))       // 0
    print(map_len(m))           // 3
}

Function Reference

Detailed API

map_new

fn map_new(cap: i64) -> &i64

Create a new hash map with the given capacity. Capacity is rounded up to the next power of 2, with a minimum of 16. The map is initially empty.

let m = map_new(100)
print(map_len(m))   // 0

Returns: Pointer to a new map header.

map_put

fn map_put(m: &i64, key: i64, val: i64)

Insert or update a key-value pair. If the key already exists, its value is replaced. If the load factor exceeds 70%, the map is automatically rehashed to double capacity.

let m = map_new(16)
map_put(m, 1, 100)
map_put(m, 2, 200)
map_put(m, 1, 150)       // update key 1
print(map_get(m, 1))     // 150
print(map_len(m))        // 2

map_get

fn map_get(m: &i64, key: i64) -> i64

Look up the value associated with key. Returns 0 if the key is not found.

let m = map_new(16)
map_put(m, 42, 999)
print(map_get(m, 42))    // 999
print(map_get(m, 99))    // 0 (not found)

Returns: The value for key, or 0 if not present.

Note: Since 0 is also a valid value, use map_has to distinguish between “key not found” and “value is 0”.

map_has

fn map_has(m: &i64, key: i64) -> i64

Check whether a key exists in the map.

let m = map_new(16)
map_put(m, 42, 0)
print(map_has(m, 42))    // 1
print(map_has(m, 99))    // 0

Returns: 1 if key exists, 0 otherwise.

map_del

fn map_del(m: &i64, key: i64) -> i64

Delete a key from the map. The slot is marked as a tombstone to preserve probe chains.

let m = map_new(16)
map_put(m, 42, 100)
print(map_del(m, 42))    // 1 (deleted)
print(map_del(m, 42))    // 0 (not found)
print(map_has(m, 42))    // 0

Returns: 1 if the key was found and deleted, 0 if not found.

map_len

fn map_len(m: &i64) -> i64

Get the number of entries currently stored in the map.

let m = map_new(16)
map_put(m, 1, 10)
map_put(m, 2, 20)
print(map_len(m))         // 2

map_puts

fn map_puts(m: &i64, key: &i8, klen: i64, val: i64)

Insert or update using a string key. The string is hashed with djb2 and the resulting hash is used as the integer key.

let m = map_new(64)
map_puts(m, "host", 4, 8080)
map_puts(m, "port", 4, 443)
print(map_gets(m, "host", 4))   // 8080

Note: Hash collisions between different strings are possible since only the hash value is stored, not the original key.

map_gets

fn map_gets(m: &i64, key: &i8, klen: i64) -> i64

String-keyed lookup. Returns 0 if not found.

let m = map_new(64)
map_puts(m, "count", 5, 42)
print(map_gets(m, "count", 5))   // 42

map_hass

fn map_hass(m: &i64, key: &i8, klen: i64) -> i64

String-keyed existence check.

let m = map_new(64)
map_puts(m, "key", 3, 1)
print(map_hass(m, "key", 3))     // 1
print(map_hass(m, "other", 5))   // 0

hash_i64

fn hash_i64(key: i64) -> i64

Hash an integer key using Knuth’s multiplicative hashing method (key * 2654435769).

str_hash

fn str_hash(s: &i8, len: i64) -> i64

Hash a byte buffer using the djb2 algorithm. Starting from 5381, each byte is folded in as h = h * 33 + c.

let h = str_hash("hello", 5)
print(h)   // deterministic hash value

map_round_pow2

fn map_round_pow2(n: i64) -> i64

Internal: Round an integer up to the next power of 2, with a minimum of 16. Used to ensure optimal hash table distribution and efficient masking.

map_pages_for

fn map_pages_for(n: i64) -> i64

Internal: Calculate the number of 4KB memory pages required to store the keys, values, and state arrays for a map with capacity n.

map_find_slot

fn map_find_slot(m: &i64, key: i64) -> i64

Internal: Find the index of the slot for key using linear probing. Returns the index of the slot containing the key, or the first available empty/tombstone slot.

map_rehash

fn map_rehash(m: &i64)

Internal: Double the capacity of the map and re-insert all existing entries. Called automatically when the load factor exceeds 70%.

Internal Functions