Hash map

A vector answers "what is at position 3?". Often that is the wrong question. A shop wants to know how many pears are in stock; a phone book, which number belongs to a name; a cache, whether this request was answered before. Each looks a value up by a key — whatever suits: a number, an id, a name.

A HashMap<K, V> stores values under keys of type K and finds them again fast. It works out a number from the key — its hash — and goes straight to the slot that number points at. So a lookup costs about the same whether the map holds ten entries or ten million.

Making a map

Along with the allocator, a hash map is given two functions:

var stock = HashMap<char8[..], int32>(allocator, HashSlice, EqualsSlice);

Hashing finds the likely slot; equality confirms that the key found there really is the one wanted. Both are needed because two different keys can hash to the same number. The Collections package provides the pair for text keys, and others — HashInt32 and EqualsInt32, HashChar8 and EqualsChar8 and more — for the common key types. They are passed as callbacks: plain function names, not calls.

flowchart LR
    k["key: pears"] --> h["HashSlice"]
    h --> slot["the slot that<br/>hash points at"]
    slot --> eq{"EqualsSlice:<br/>is it this key?"}
    eq -- "yes" --> v["its value: 4"]
    eq -- "no entry there" --> none["none"]

Inserting and looking up

Insert adds an entry. It may need more room, and so can fail; ? hands that failure to Main:

stock.Insert("apples", 12)?;
stock.Insert("pears", 4)?;
stock.Insert("plums", 30)?;

Get returns an optional, int32?, because the key may not be there. A match handles both answers:

match stock.Get("pears") {
    count? => PrintLine("pears          {}", count),
    none => PrintLine("pears          not stocked")
}

Pears are in stock, so this prints 4; the same match on "kiwis" prints not stocked.

One entry per key

A key appears at most once. Inserting it again replaces its value, and the map does not grow. Replace does the same and also hands back the value it displaced:

stock.Insert("apples", 15)?;
let previous = stock.Replace("apples", 20)?;

Apples are now 20, previous holds the 15 they replaced, and the map still has three entries. previous is an optional — a key that was not there yet displaced nothing.

Removing and checking

Remove takes the entry out and returns its value, or none if there was no such key. ContainsKey asks without changing anything:

PrintLine("removed plums  {}", stock.Remove("plums") ?? 0);
PrintLine("has plums      {}", stock.ContainsKey("plums"));

No order

What a hash map does not keep is order. A for loop over it visits the entries in whatever arrangement the hashing produced, which may differ from one run to the next. When order matters — an alphabetical listing, the earliest entry — the tree map keeps it.

The program

The whole lesson is one package in the Examples repository. Its comments explain every step.

// A vector answers "what is at position 3". A hash map answers "what is stored under this key",
// where the key is whatever suits — a number, an id, a name.
//
// It finds an entry by computing a number from the key, its hash, and going straight to the slot
// that number points at. So a lookup costs about the same whether the map holds ten entries or
// ten million.
import Allocator::{ Allocator, SystemAllocator };
import Collections::{ CollectionError, EqualsSlice, HashMap, HashSlice };
import Io::PrintLine;

func Main() -> ! CollectionError {
    var system = SystemAllocator();
    let allocator: Allocator = system;

    // Along with the allocator come two functions: one to hash a key, one to tell whether two
    // keys are equal. Hashing finds the likely slot; equality confirms that the key found there
    // really is the one wanted, since two different keys can hash to the same number. The
    // package provides both for text keys.
    var stock = HashMap<char8[..], int32>(allocator, HashSlice, EqualsSlice);

    // Inserting may need more room, and so can fail; `?` hands that failure to `Main`.
    stock.Insert("apples", 12)?;
    stock.Insert("pears", 4)?;
    stock.Insert("plums", 30)?;
    PrintLine("entries        {}", stock.Length());

    // `Get` returns an optional, `int32?`, because the key may not be there.
    match stock.Get("pears") {
        count? => PrintLine("pears          {}", count),
        none => PrintLine("pears          not stocked")
    }
    match stock.Get("kiwis") {
        count? => PrintLine("kiwis          {}", count),
        none => PrintLine("kiwis          not stocked")
    }

    // A key appears at most once. Inserting it again replaces its value, and the map does not
    // grow. `Replace` does the same and also hands back the value it displaced.
    stock.Insert("apples", 15)?;
    let previous = stock.Replace("apples", 20)?;
    PrintLine("apples         {} (was {}), {} entries", stock.Get("apples") ?? 0, previous ?? 0,
        stock.Length());

    // `Remove` takes the entry out and returns its value, or `none` if there was no such key.
    PrintLine("removed plums  {}", stock.Remove("plums") ?? 0);
    PrintLine("has plums      {}", stock.ContainsKey("plums"));
    PrintLine("entries        {}", stock.Length());

    // What a hash map does not keep is order. A `for` loop over it visits the entries in
    // whatever arrangement the hashing produced, which may differ from one run to the next.
    // When order matters, the TreeMap lesson's map keeps it.
}

Besides Io, its Rux.toml lists Allocator and Collections under [Dependencies].

Run it

cd Examples/Collections/HashMap
rux run

entries        3
pears          4
kiwis          not stocked
apples         20 (was 15), 3 entries
removed plums  30
has plums      false
entries        2

Common mistakes

Try it yourself

1. Add a fourth fruit, then print every entry with for entry in stock, using entry.key and entry.value.
2. Count the letters of "banana" in a HashMap<char8, int32>, made with HashChar8 and EqualsChar8: for each letter, insert (counts.Get(c) ?? 0) + 1.
3. Sell three apples: read the count, check there are enough, and store the new count.

Learn more

• Hash set — a hash map with only the keys
• Tree map — a map that keeps its keys in order
• Callback — passing a function as an argument
• Word count — a checkpoint project that counts words in a hash map