Skip to content
Tutorials Center
My learning

Topics

Lesson 17 of 36 ยท Arrays and Ranges

Associative Arrays (Hash Maps) in D

Use D's built-in hash maps: declare associative arrays, insert and look up keys safely with in and get, remove entries, iterate, count words, and choose suitable key types.

An associative array maps keys to values: names to phone numbers, words to counts, product codes to prices. In D it is a built-in type written ValueType[KeyType], implemented as a hash table, with no import and no class to instantiate. This lesson covers creating one, safe lookup with in and get, removal, iteration, the word-count idiom, and what makes a good key. D code is read-only; the C stand-ins build a tiny hash table so you can see how it works inside.

Creating and using one

D
import std.stdio;

void main()
{
    int[string] age;                  // string keys, int values
    age["Ada"] = 36;
    age["Linus"] = 28;
    age["Grace"] = 85;

    writeln(age["Ada"]);              // 36
    writeln(age.length);              // 3

    string[int] weekday = [1: "Mon", 2: "Tue", 3: "Wed"];   // literal
    writeln(weekday[2]);              // Tue
}

Assigning to a new key inserts it; assigning to an existing key overwrites. An associative array starts out as null (no memory), and the first insertion allocates it. Like slices, an associative array is a reference: copying the variable shares the same table.

Looking up safely

Reading a missing key with [] throws a RangeError. Use in, get or require:

D
import std.stdio;

void main()
{
    int[string] stock = ["apple": 3, "pear": 0];

    if (auto p = "apple" in stock)        // in returns a pointer or null
    {
        writeln("apple: ", *p);           // apple: 3
        *p += 5;                          // modify in place
    }
    writeln(stock["apple"]);              // 8

    writeln(stock.get("kiwi", -1));       // -1: default when missing
    writeln("kiwi" in stock);             // null

    stock.require("kiwi", 10);            // insert 10 if missing, return the value
    writeln(stock["kiwi"]);               // 10
}
  • key in aa returns a pointer to the value, or null. It is the fastest way to "check then use".
  • aa.get(key, default) returns a default without inserting.
  • aa.require(key, value) inserts only if missing.
  • aa.update(key, createDelegate, updateDelegate) handles both cases in one lookup.

Removing, clearing and iterating

D
stock.remove("pear");                      // returns true if it existed
foreach (key, value; stock)                // order is not defined
{
    writeln(key, " => ", value);
}
foreach (key; stock.byKey) { }             // lazy ranges
auto keys = stock.keys;                    // a copy as an array
auto vals = stock.values;
stock.clear();                             // remove everything

Never rely on the iteration order: it depends on hash values and table size. To print in order, sort the keys: foreach (k; stock.keys.sort) { ... }. byKeyValue gives pairs with .key and .value. Do not insert or remove keys while iterating with foreach.

Word counting

The classic use of an associative array is counting:

D
import std.stdio;
import std.string : split, toLower;
import std.algorithm : sort;

void main()
{
    string text = "the cat and the hat and the bat";
    int[string] count;
    foreach (word; text.toLower.split)
    {
        ++count[word];                    // missing keys start at int.init (0)
    }
    foreach (word; count.keys.sort)
    {
        writefln("%-4s %d", word, count[word]);
    }
}

This prints and 2, bat 1, cat 1, hat 1 and the 3, one per line, aligned. ++count[word] works on a missing key because a read-modify-write expression on an associative array creates the entry with the value type's default.

Keys: what works

A key type must be comparable for equality and hashable. Integers, characters, strings, enums, and structs made of those are fine. Floating-point keys are legal but dangerous, because of nan and rounding. Arrays used as keys are compared by contents. Class keys use the object's toHash and opEquals, which you can override. Avoid keys whose contents change after insertion.

You can store anything as a value, including arrays or other associative arrays: string[][string] groups; groups["fruit"] ~= "apple"; appends to the list under "fruit", creating it if needed.

A hash table in C

The built-in table hides the machinery: hash the key, pick a bucket, compare keys, handle collisions. This stand-in builds a minimal one with chaining.

C C stand-in: a tiny hash table for word counts

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

The output is and 2, bat 1, cat 1, hat 1, the 3 and dog 0 (missing, like get("dog", 0)). Each lookup hashes the word to a bucket and walks a short chain.

C C stand-in: why iteration order is undefined

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

The keys come out grouped by bucket number, not in the order they were listed. D's associative arrays behave the same way, which is why you sort the keys when you need a stable order.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How do you declare an associative array from string to int?

    The syntax is ValueType[KeyType].
  2. 2. What does "k" in aa return?

    in gives a pointer so you can test and update in one lookup.
  3. 3. What happens when you read aa["missing"] with the [] operator?

    Use in, get or require for keys that might be absent.
  4. 4. In what order does foreach visit an associative array?

    Order depends on hashing; sort the keys if you need order.

Summary

  • V[K] is a built-in hash map; copying the variable shares the table.
  • Use in, get and require for safe lookup; plain [] throws on missing keys.
  • remove, keys, values, byKey and byKeyValue manage and iterate entries; order is undefined.
  • ++count[word] is the idiomatic counting loop.

Next: Ranges and algorithms