Hash Maps in Zig

After Using Array List in Zig, the next data structure that I reach for is the hash map. The Zig standard library has several of them and the names can be confusing, so I will start with the one you need most of the time, std.StringHashMap and use it to count words.

const std = @import("std");

pub fn main(init: std.process.Init) !void {
    const allocator = init.gpa;

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

    const text = "the quick brown fox jumps over the lazy dog the end";
    var words = std.mem.tokenizeScalar(u8, text, ' ');
    while (words.next()) |word| {
        const entry = try counts.getOrPut(word);
        if (entry.found_existing) {
            entry.value_ptr.* += 1;
        } else {
            entry.value_ptr.* = 1;
        }
    }

    std.debug.print("Distinct words: {d}\n", .{counts.count()});

    if (counts.get("the")) |n| {
        std.debug.print("\"the\" appears {d} times\n", .{n});
    }
    if (counts.get("cat")) |n| {
        std.debug.print("\"cat\" appears {d} times\n", .{n});
    } else {
        std.debug.print("\"cat\" is not in the map\n", .{});
    }

    try counts.put("fox", 100);
    std.debug.print("\"fox\" is now {d}\n", .{counts.get("fox").?});

    const removed = counts.remove("end");
    std.debug.print("Removed \"end\": {}\n", .{removed});
    std.debug.print("Contains \"end\": {}\n", .{counts.contains("end")});

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

The std.StringHashMap(u32) type is a hash map with string keys and u32 values. The init(allocator) call creates an empty map and stores the allocator inside it, so you do not have to pass it to every call. Nothing is allocated until the first insert. The defer counts.deinit() line frees everything when main() returns. If your keys are integers, enums or plain structs, use std.AutoHashMap(K, V) instead. It has the same functions.

The tokenizeScalar() function splits the text on spaces and next() returns one word at a time. The getOrPut() function looks a word up and inserts it in a single step. It returns a struct whose found_existing field tells you whether the key was already there and whose value_ptr field points to the value inside the map. If the word exists, we increment through the pointer. If not, the slot has been created but its value is undefined, so we have to set it. Using one getOrPut() instead of a get() followed by a put() is the usual way to count things in Zig.

The count() function returns the number of keys. The get() function returns an optional, so the if (counts.get("the")) |n| block runs only when the key exists and the else branch handles the missing one. The put() function inserts a key or overwrites its value when it is already there. The .? after get("fox") says that the value cannot be null, which is safe right after the put(). The remove() function returns true when the key was there and false otherwise and the contains() function answers the question without touching anything.

The iterator() function visits every entry and entry.key_ptr.* and entry.value_ptr.* give the key and the value. The order of the output is not the order of insertion and it can change between Zig versions. If you need insertion order, use std.StringArrayHashMapUnmanaged, which keeps the entries in an array.

Be careful with one thing. The map stores the key slice, not a copy of it. In this program the keys point into text, which is a string literal that lives as long as the program. If your keys come from a line buffer that you reuse for the next line, copy each key with allocator.dupe(u8, word) before inserting it and free the keys before calling deinit().

There is also std.StringHashMapUnmanaged. Like ArrayList, it does not store an allocator and expects one as the first argument of put(), getOrPut() and deinit(). Its initial value is .empty. The operations are the same and it is the better choice for a struct that holds many maps sharing one allocator.

Save the code as hashmap.zig and try it:

$ zig version
0.17.0
$ zig run hashmap.zig
Distinct words: 9
"the" appears 3 times
"cat" is not in the map
"fox" is now 100
Removed "end": true
Contains "end": false
dog: 1
the: 3
jumps: 1
brown: 1
quick: 1
fox: 100
lazy: 1
over: 1

Happy coding in Zig!

Want to learn Zig? Look at my book Systems Programming with Zig.