Associative arrays

A table of values by key

An associative array maps a key to a value. The declaration reads value type first, then the key type in brackets: int[string] stock; holds integers, looked up by string. stock["tea"] = 3 stores a value and stock["tea"] reads it back; stock.length counts the keys.

A key that has never been stored starts at the default for its value type, which is 0 for an int. The compound assignment stock["cake"] += 1 creates the entry at zero and then adds, which is why it works on a key the program has never seen. Counting occurrences becomes a single line inside a loop.

The key type can be almost anything with a hash: a string, an int, a struct whose fields are hashable. The value type can be a struct too, which is how a small database is built in memory — a name mapped to a record, with the key doing the work a search loop would otherwise do.

Asking without creating

A plain read of a key that is not there does not give zero: stock["fig"] on a missing key stops the program with a range violation. A lookup has to be asked for honestly. "cake" in stock gives a pointer to the value, or null when the key is absent, and that can be tested directly in an if.

When a default is more convenient than a test, stock.get("fig", 0) returns the stored value when the key is present and the fallback when it is not, and it leaves the table unchanged. The pointer from in can also be dereferenced to read the value, which is worth doing once the answer is already known to be yes.

Keys have no order until you sort them

The order in which a loop over an associative array visits its keys is arbitrary and can differ between two runs of the same program. Anything printed in that order is not reproducible, and a report that changes its line order between runs is a report nobody trusts.

The fix is to take the keys, which is an ordinary array, and sort it. stock.keys gives the array and stock.keys.sort sorts it with std.algorithm, so the loop can walk the keys in alphabetical order and print the same lines every time.

What a hash buys you

An associative array hashes each key into a number, uses that number to pick a bucket, and stores the value there. A lookup hashes the key once and goes almost straight to the answer, so its cost does not grow with the number of entries the way a linear search would.

The hash also explains the iteration order. Keys that hash near each other land near each other, and the table grows and rehashes as entries are added, so the order is a detail of the implementation rather than a property of your data. Two runs of the same binary can print the same table in different orders.

A hash is not a promise of constant time. Two different keys can land in the same bucket, and the table then compares keys until it finds the right one; a bad hash function puts everything in one bucket and turns every lookup into a scan. The standard library hashes strings and numbers well, which is why the cost stays flat in practice.

Counting, testing, defaulting

Three operations look similar and behave differently. table[key] = v inserts or overwrites. key in table answers with a pointer to the value, or null, and never inserts. table.get(key, fallback) answers with the stored value or the fallback, and never inserts either. Only the first one changes the table.

table[key] read on a missing key is not a default: it stops the program. table[key] += 1 is different again, because the compound assignment creates the entry at the type default and then adds. That is why a counting loop can start with an empty table and never test for the key.

Two keys, printed in order

import std.stdio;
import std.algorithm;

void main() {
    string[string] capital;
    capital["fr"] = "paris";
    capital["jp"] = "tokyo";
    foreach (code; capital.keys.sort) {
        writeln(code, " -> ", capital[code]);
    }
}

Try these next

• Change the text to a sentence with a repeated word and watch one count grow while the kind count stays put.
• Ask for a word that is absent with get and a fallback, then with in, and compare the two answers.
• Print the table by value instead of by key, and explain why the order is not the one you want.