# Hash Maps

### 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.

```zig
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:

```text
2
```

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

The values have type `T`.

```zig
std.StringHashMap(u32)
```

means:

```text
string keys, u32 values
```

Like `ArrayList`, the map needs an allocator.

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

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

```zig
defer map.deinit();
```

Insert values with `put`.

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

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

Retrieve values with `get`.

```zig
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.

```zig
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.

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

No output appears because `"orange"` is not present.

To test for existence directly:

```zig
map.contains("blue")
```

Example:

```zig
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:

```text
found
```

A hash map can also be iterated.

```zig
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:

```text
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.

```zig
entry.key_ptr
entry.value_ptr
```

Dereference them with `.*`.

```zig
entry.value_ptr.*
```

This accesses the actual stored value.

Values can also be modified through the pointer.

```zig
entry.value_ptr.* += 1;
```

A common pattern is counting frequencies.

```zig
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:

```text
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.

```zig
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.