Hash Maps

A hash map stores key-value pairs.

Given a key, the map quickly finds the associated value.

The standard library provides several hash map types. The most commonly used is std.HashMap.

A simple example counts words.

const std = @import("std");

pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();

    const allocator = gpa.allocator();

    var map = std.StringHashMap(u32).init(allocator);
    defer map.deinit();

    try map.put("red", 1);
    try map.put("green", 2);
    try map.put("blue", 3);

    if (map.get("green")) |value| {
        std.debug.print("{d}\n", .{value});
    }
}

The output is:

std.StringHashMap(T) is a hash map whose keys are strings.

The values have type T.

std.StringHashMap(u32)

means:

string keys, u32 values

Like ArrayList, the map needs an allocator.

var map = std.StringHashMap(u32).init(allocator);

And like other allocator-backed structures, it must later be deinitialized.

defer map.deinit();

Insert values with put.

try map.put("red", 1);

If the key already exists, the old value is replaced.

Retrieve values with get.

map.get("green")

The return type is optional.

If the key exists, the value is returned.

If not, the result is null.

This makes missing keys explicit.

if (map.get("green")) |value| {
    std.debug.print("{d}\n", .{value});
}

The value is available only inside the block.

A lookup that fails does nothing.

if (map.get("orange")) |value| {
    std.debug.print("{d}\n", .{value});
}

No output appears because "orange" is not present.

To test for existence directly:

map.contains("blue")

Example:

const std = @import("std");

pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();

    const allocator = gpa.allocator();

    var map = std.StringHashMap(bool).init(allocator);
    defer map.deinit();

    try map.put("zig", true);

    if (map.contains("zig")) {
        std.debug.print("found\n", .{});
    }
}

The output is:

found

A hash map can also be iterated.

const std = @import("std");

pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();

    const allocator = gpa.allocator();

    var map = std.StringHashMap(u32).init(allocator);
    defer map.deinit();

    try map.put("a", 1);
    try map.put("b", 2);
    try map.put("c", 3);

    var it = map.iterator();

    while (it.next()) |entry| {
        std.debug.print("{s}: {d}\n", .{
            entry.key_ptr.*,
            entry.value_ptr.*,
        });
    }
}

The output is similar to:

a: 1
b: 2
c: 3

The order is not guaranteed.

Hash maps are designed for fast lookup, not stable ordering.

Each iterator entry contains pointers.

entry.key_ptr
entry.value_ptr

Dereference them with .*.

entry.value_ptr.*

This accesses the actual stored value.

Values can also be modified through the pointer.

entry.value_ptr.* += 1;

A common pattern is counting frequencies.

const std = @import("std");

pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();

    const allocator = gpa.allocator();

    const words = [_][]const u8{
        "zig",
        "c",
        "zig",
        "zig",
        "go",
    };

    var counts = std.StringHashMap(u32).init(allocator);
    defer counts.deinit();

    for (words) |word| {
        const result = try counts.getOrPut(word);

        if (!result.found_existing) {
            result.value_ptr.* = 0;
        }

        result.value_ptr.* += 1;
    }

    var it = counts.iterator();

    while (it.next()) |entry| {
        std.debug.print("{s}: {d}\n", .{
            entry.key_ptr.*,
            entry.value_ptr.*,
        });
    }
}

The output is similar to:

zig: 3
c: 1
go: 1

getOrPut is useful because it avoids searching twice.

It either returns the existing entry or inserts a new one.

The result structure contains:

Field	Meaning
`found_existing`	`true` if key already existed
`value_ptr`	Pointer to stored value

The standard library also provides other map types.

Type	Purpose
`std.StringHashMap`	String keys
`std.AutoHashMap`	Automatically hashes common key types
`std.ArrayHashMap`	Preserves insertion order
`std.BufMap`	Owns string storage internally

std.AutoHashMap is often used for integer keys.

std.AutoHashMap(u32, bool)

This creates a map from u32 to bool.

Hash maps are allocator-backed structures.

Growing the map may allocate memory.

Insertion can therefore fail.

This is why operations like put return errors.

The explicit allocation model keeps the cost visible.

Nothing grows silently behind the programmer’s back.

Exercise 14-13. Create a map from strings to integers.

Exercise 14-14. Count how many times each word appears in an array.

Exercise 14-15. Iterate through a map and print all key-value pairs.

Exercise 14-16. Replace StringHashMap with AutoHashMap using integer keys.