Skip to content
Kavachकवच

Maps

Also known as: dictionary dict hashmap hash table object key value lookup unordered_map record store

● Beginner5 minBefore this: Lists, If LetSpec 2.2

A map stores values under keys: ["asha": 31] keeps 31 under the key "asha".

fn main() {
    let ages: [String: Int] = [:]
    ages["asha"] = 31
    ages["omar"] = 27

    print(ages["asha"] ?? 0)   // 31 — missing key → your fallback

    for (name, age) in ages {     // insertion order, always
        print("{name} is {age}")
    }

    ages.remove("omar")
    print(ages.len())              // 1
}

The program ran and printed:

kavach run ages.kav

31asha is 31omar is 271
ages.kav: Kavach code, then what running it prints
  • [String: Int] is a map from text keys to whole-number values; [:] is an empty one.
  • Reading a key gives an optional: the key may not be there, so ?? 0 says what to use then.
  • A loop visits the entries in the order they were added, every time.

Other languages call this a dictionary, a hash map or an object.

One page for each form

Making a map →Reading a value →Adding and changing →Looping over a map →

Try it yourself

Count how many times each word appears in ["a", "b", "a"].
Show the answer

Start with let counts: [String: Int] = [:]; for each word, counts[w] = (counts[w] ?? 0) + 1. It ends as ["a": 2, "b": 1].

What Kavach does for you

  • Maps can't be attacked through their keys

    Map hashing is seeded fresh for every run, so nobody can send keys built to make your maps slow.

    hash-maps.md

Go deeper the why, for readers who want it

Past the caches, each hop into memory costs about 70 ns whatever you compute there. The design question is not the hash, it is how many hops one lookup touches:

Kavachhash → 16-byte bucket. Done.
C++ std::unordered_maphash → bucket array → chase the node pointer…

Kavach keeps keys and values side by side in one flat table and probes it linearly at most half full, so a lookup is about 1.5 probes, each a quarter of a cache line. The hash is seeded for every run, so hostile keys can't force collisions.

C++'s std::unordered_map promises that erasing never moves other entries, which forces one heap node per entry: one more hop. Kavach promised insertion order and no aliasing instead. Check both:

ours @v0.2 · table.rs:188 bucket_of()theirs @gcc-13 · hashtable.h _M_find_before_node()

dict — 20M random reads from a 2M-entry map · WSL Ubuntu 24.04 · i7-13700HX · kavach build (LLVM) · g++ 13 -O2 · Python 3.12 · best of 9 (Python best of 3)

Kavach272 ms · finished 1st
C++ -O2613 ms · 2.3× behind
Python 3.129,195 ms · 34× behind
Verify itgit clone https://github.com/Mithlesh04/kavach && cd kavach sh scripts/run-benchmarks.sh "" benchmarks/lookups
benchmark source (all languages)raw numbers & machinemethodologywhere Kavach loses