# Hash Maps

> Key-value storage, and the getOrPut pattern.

```zig
const std = @import("std");
const expect = std.testing.expect;

test "string keys" {
    const gpa = std.testing.allocator;
    var map: std.StringHashMapUnmanaged(u32) = .empty;
    defer map.deinit(gpa);

    try map.put(gpa, "one", 1);
    try map.put(gpa, "two", 2);

    try expect(map.get("one").? == 1);
    try expect(map.get("three") == null);
    try expect(map.count() == 2);
}

test "auto hash for simple keys" {
    const gpa = std.testing.allocator;
    // AutoHashMap derives hashing and equality from the key type.
    var map: std.AutoHashMapUnmanaged(u32, []const u8) = .empty;
    defer map.deinit(gpa);

    try map.put(gpa, 1, "one");
    try expect(std.mem.eql(u8, map.get(1).?, "one"));
}

test "getOrPut avoids hashing twice" {
    const gpa = std.testing.allocator;
    var counts: std.StringHashMapUnmanaged(u32) = .empty;
    defer counts.deinit(gpa);

    for ([_][]const u8{ "a", "b", "a" }) |word| {
        // One lookup instead of a get followed by a put.
        const entry = try counts.getOrPut(gpa, word);
        if (!entry.found_existing) entry.value_ptr.* = 0;
        entry.value_ptr.* += 1;
    }

    try expect(counts.get("a").? == 2);
    try expect(counts.get("b").? == 1);
}

test "iterate entries" {
    const gpa = std.testing.allocator;
    var map: std.AutoHashMapUnmanaged(u32, u32) = .empty;
    defer map.deinit(gpa);

    try map.put(gpa, 1, 10);
    try map.put(gpa, 2, 20);

    var total: u32 = 0;
    var it = map.iterator();
    while (it.next()) |entry| total += entry.value_ptr.*;
    try expect(total == 30);
}

test "remove" {
    const gpa = std.testing.allocator;
    var map: std.StringHashMapUnmanaged(u32) = .empty;
    defer map.deinit(gpa);

    try map.put(gpa, "gone", 1);
    try expect(map.remove("gone"));
    try expect(map.count() == 0);
}
```

*Runnable: compiled to WebAssembly and executed by CI against Zig master. (`03-standard-library.hash-maps`)*

## Which map to pick

| Type | For |
| --- | --- |
| `AutoHashMapUnmanaged(K, V)` | keys with derivable hashing (integers, enums, simple structs) |
| `StringHashMapUnmanaged(V)` | `[]const u8` keys |
| `ArrayHashMapUnmanaged(K, V)` | when you need stable insertion order |

Like `ArrayList`, these are unmanaged: `.empty` to create, allocator passed to
each method that allocates.

`AutoHashMap` will refuse keys it cannot hash safely: slices, for instance,
because hashing the pointer is almost never what you meant. That is why string
keys get their own type.

## `getOrPut` instead of get-then-put

The counting idiom looks like this:

```zig
const entry = try counts.getOrPut(gpa, word);
if (!entry.found_existing) entry.value_ptr.* = 0;
entry.value_ptr.* += 1;
```

One hash and one lookup, rather than two. `entry.value_ptr` points into the
map, so writing through it updates the stored value in place.

Note that pointer is only valid until the next insertion: the same
invalidation rule as `ArrayList.items`.

## Keys are not copied

The map stores your key as given. For string keys that means the map holds a
slice pointing at memory it does not own; if that memory is freed or reused,
the map is corrupt. Either keep the keys alive yourself, or duplicate them on
insert and free them on removal.