module hashmap
module lib/hashmap.mu
import "hashmap"hashmap provides a hash map (associative array) implemented purely in mu.
The motivation is self-hosting: every host backs the {} map type with a native implementation. Expressing the same data structure in mu shows the language does not depend on a native map to represent associative data. That path was not taken -- both frontends carry a hash-indexed native map today, because the compiler's own maps are hot enough to want one -- so this module is the alternative rather than the plan, and a worked example of what mu can build out of lists and arithmetic alone.
A map is a two-element list [buckets, count]:
- buckets is a list of bucket lists; each bucket holds [key, value] entries.
- count is the number of live entries.
Bucket counts are always powers of two, so a bucket index is a cheap mask of the key's hash (hash & (nbuckets - 1)), which stays in range even when the hash is negative because masking keeps only the low bits.
Keys may be strings, integers, or booleans; they are compared with ==. Everything here uses only lists, arithmetic, and ord — no {} literal and no map builtin — so the module is a candidate replacement for the native map.
Functions
bucket_index#
bucket_index maps a hash onto [0, nbuckets) given a power-of-two nbuckets.
Source lib/hashmap.mu:50
fn bucket_index(hash, nbuckets) {
return hash & (nbuckets - 1)
}contains#
contains reports whether key is present in the map.
Source lib/hashmap.mu:150
fn contains(m, key) {
buckets := m[0]
idx := bucket_index(hash_key(key), len(buckets))
return find_in_bucket(buckets[idx], key) >= 0
}each#
each calls f(key, value) for every entry. Order is unspecified.
Source lib/hashmap.mu:225
fn each(m, f) {
es := entries(m)
i := 0
while i < len(es) {
f(es[i][0], es[i][1])
i = i + 1
}
}entries#
entries returns every [key, value] pair. Order is unspecified.
Source lib/hashmap.mu:184
fn entries(m) {
out := []
buckets := m[0]
i := 0
while i < len(buckets) {
bucket := buckets[i]
j := 0
while j < len(bucket) {
append(out, bucket[j])
j = j + 1
}
i = i + 1
}
return out
}find_in_bucket#
find_in_bucket returns the index of key within bucket, or -1 when absent.
Source lib/hashmap.mu:66
fn find_in_bucket(bucket, key) {
i := 0
while i < len(bucket) {
if bucket[i][0] == key {
return i
}
i = i + 1
}
return -1
}from#
from builds a map from a list of [key, value] pairs.
Source lib/hashmap.mu:83
fn from(pairs) {
m := new()
i := 0
while i < len(pairs) {
set(m, pairs[i][0], pairs[i][1])
i = i + 1
}
return m
}get#
get returns the value stored under key, or nil when key is absent.
Source lib/hashmap.mu:145
fn get(m, key) {
return get_or(m, key, nil)
}get_or#
get_or returns the value stored under key, or fallback when key is absent.
Source lib/hashmap.mu:133
fn get_or(m, key, fallback) {
buckets := m[0]
idx := bucket_index(hash_key(key), len(buckets))
bucket := buckets[idx]
pos := find_in_bucket(bucket, key)
if pos >= 0 {
return bucket[pos][1]
}
return fallback
}hash_key#
hash_key returns a (possibly negative) integer hash for key.
Source lib/hashmap.mu:23
fn hash_key(key) {
t := type(key)
if t == "INTEGER" {
return key
}
if t == "BOOLEAN" {
if key {
return 1231
}
return 1237
}
if t == "STRING" {
// FNV-1a over the bytes; 64-bit multiply wraps, which is intended.
h := 2166136261
i := 0
n := len(key)
while i < n {
h = (h ^ ord(key[i])) * 16777619
i = i + 1
}
return h
}
// Unsupported key types collapse to bucket 0 but still compare by ==.
return 0
}keys#
keys returns every key. Order is unspecified.
Source lib/hashmap.mu:201
fn keys(m) {
out := []
es := entries(m)
i := 0
while i < len(es) {
append(out, es[i][0])
i = i + 1
}
return out
}make_buckets#
make_buckets returns a list of n empty buckets.
Source lib/hashmap.mu:55
fn make_buckets(n) {
buckets := []
i := 0
while i < n {
append(buckets, [])
i = i + 1
}
return buckets
}new#
new returns an empty map with an initial capacity of eight buckets.
Source lib/hashmap.mu:78
fn new() {
return [make_buckets(8), 0]
}remove#
remove deletes key from the map and reports whether it was present.
Source lib/hashmap.mu:157
fn remove(m, key) {
buckets := m[0]
idx := bucket_index(hash_key(key), len(buckets))
bucket := buckets[idx]
pos := find_in_bucket(bucket, key)
if pos < 0 {
return false
}
rebuilt := []
i := 0
while i < len(bucket) {
if i != pos {
append(rebuilt, bucket[i])
}
i = i + 1
}
buckets[idx] = rebuilt
m[1] = m[1] - 1
return true
}resize#
resize rehashes every entry into a fresh table of new_capacity buckets.
Source lib/hashmap.mu:94
fn resize(m, new_capacity) {
old := m[0]
fresh := make_buckets(new_capacity)
i := 0
while i < len(old) {
bucket := old[i]
j := 0
while j < len(bucket) {
entry := bucket[j]
idx := bucket_index(hash_key(entry[0]), new_capacity)
append(fresh[idx], entry)
j = j + 1
}
i = i + 1
}
m[0] = fresh
return m
}set#
set inserts or updates key => value and returns the map. It grows the table once the load factor passes 0.75 to keep buckets short.
Source lib/hashmap.mu:115
fn set(m, key, value) {
buckets := m[0]
idx := bucket_index(hash_key(key), len(buckets))
bucket := buckets[idx]
pos := find_in_bucket(bucket, key)
if pos >= 0 {
bucket[pos][1] = value
return m
}
append(bucket, [key, value])
m[1] = m[1] + 1
if m[1] * 4 >= len(buckets) * 3 {
resize(m, len(buckets) * 2)
}
return m
}size#
size returns the number of entries in the map.
Source lib/hashmap.mu:179
fn size(m) {
return m[1]
}values#
values returns every value. Order matches keys.
Source lib/hashmap.mu:213
fn values(m) {
out := []
es := entries(m)
i := 0
while i < len(es) {
append(out, es[i][1])
i = i + 1
}
return out
}