# The Basic Idea

### HashMap

A `HashMap` is a data structure for storing values by key.

An array stores values by position:

```zig
items[0]
items[1]
items[2]
```

A hash map stores values by name, number, pointer, or another key:

```zig
scores.get("alice")
scores.get("bob")
scores.get("charlie")
```

The key tells the map where to find the value.

## The Basic Idea

Suppose you want to store scores for players:

```text
alice   -> 120
bob     -> 95
charlie -> 180
```

You could use two arrays:

```text
names:  ["alice", "bob", "charlie"]
scores: [120,     95,    180]
```

But then every lookup requires searching through the names.

A hash map does this more directly.

It takes the key, computes a hash, and uses that hash to find where the value should live in memory.

```text
"alice" -> hash -> bucket -> 120
```

A hash is a number computed from a key.

The hash map uses that number to decide where to store or find the value.

## Importing HashMap

`HashMap` lives in the standard library:

```zig
const std = @import("std");
```

The general form is:

```zig
std.HashMap(K, V, Context, max_load_percentage)
```

Where:

```text
K = key type
V = value type
Context = hashing and equality behavior
max_load_percentage = how full the map can become before growing
```

For many beginner programs, you will more often use a simpler wrapper such as `std.AutoHashMap`.

## AutoHashMap

`AutoHashMap` chooses normal hash and equality behavior for common key types.

Example:

```zig
std.AutoHashMap(u32, []const u8)
```

This means:

```text
key   = u32
value = []const u8
```

So the map can store entries like:

```text
1 -> "one"
2 -> "two"
3 -> "three"
```

## Creating a HashMap

Here is a complete 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.AutoHashMap(u32, []const u8).init(allocator);
    defer map.deinit();
}
```

A hash map uses heap memory, so it needs an allocator.

This is the same pattern you saw with `ArrayList`.

```zig
var map = std.AutoHashMap(u32, []const u8).init(allocator);
defer map.deinit();
```

`init` creates the map.

`deinit` frees its internal memory.

## Adding Values

Use `put` to insert a key-value pair:

```zig
try map.put(1, "one");
try map.put(2, "two");
try map.put(3, "three");
```

Full 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.AutoHashMap(u32, []const u8).init(allocator);
    defer map.deinit();

    try map.put(1, "one");
    try map.put(2, "two");
    try map.put(3, "three");
}
```

`put` uses `try` because inserting may allocate memory.

Allocation can fail, so Zig makes the failure visible.

## Getting Values

Use `get` to look up a value:

```zig
const value = map.get(2);
```

But `get` returns an optional value.

The key may not exist.

So the type is:

```zig
?[]const u8
```

That means:

```text
maybe a string, maybe null
```

Example:

```zig
if (map.get(2)) |value| {
    std.debug.print("{s}\n", .{value});
} else {
    std.debug.print("not found\n", .{});
}
```

Output:

```text
two
```

## Missing Keys

If the key is not present, `get` returns `null`.

```zig
if (map.get(99)) |value| {
    std.debug.print("{s}\n", .{value});
} else {
    std.debug.print("not found\n", .{});
}
```

Output:

```text
not found
```

This is important.

A hash map lookup can fail in a normal, expected way. Zig represents that with an optional value.

## Updating Values

If you call `put` with an existing key, the old value is replaced.

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

Now key `1` maps to:

```text
uno
```

The old value is gone from the map.

For simple values, this is fine. For owned heap memory, you must be more careful. The map does not automatically know how to free a value you replaced.

## Checking Whether a Key Exists

You can use `contains`:

```zig
if (map.contains(2)) {
    std.debug.print("key exists\n", .{});
}
```

This only checks existence. It does not give you the value.

When you need the value, use `get`.

## Removing Values

Use `remove`:

```zig
const removed = map.remove(2);
```

`remove` returns a boolean.

```text
true  = something was removed
false = key was not found
```

Example:

```zig
if (map.remove(2)) {
    std.debug.print("removed\n", .{});
} else {
    std.debug.print("not found\n", .{});
}
```

## Iterating Over a HashMap

You can loop over all entries with an iterator.

```zig
var it = map.iterator();

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

The iterator gives you pointers to entries.

That is why you see:

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

The `.*` means “load the value pointed to by this pointer.”

## Iteration Order

Hash maps do not preserve insertion order.

If you insert:

```text
1 -> one
2 -> two
3 -> three
```

The iteration order may not be:

```text
1
2
3
```

It may come out in another order.

Do not write code that depends on hash map iteration order.

If order matters, use a different structure, or store keys separately in an `ArrayList`.

## String Keys

For string keys, Zig provides `std.StringHashMap`.

Example:

```zig
var scores = std.StringHashMap(u32).init(allocator);
defer scores.deinit();

try scores.put("alice", 120);
try scores.put("bob", 95);
try scores.put("charlie", 180);
```

Lookup:

```zig
if (scores.get("alice")) |score| {
    std.debug.print("alice = {}\n", .{score});
}
```

Output:

```text
alice = 120
```

`StringHashMap(V)` is usually what you want when the key is `[]const u8`.

## HashMap vs StringHashMap

Use this:

```zig
std.AutoHashMap(u32, []const u8)
```

when the key is a number.

Use this:

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

when the key is a string.

The value type can be whatever you need:

```zig
std.StringHashMap(bool)
std.StringHashMap(i64)
std.StringHashMap([]const u8)
std.StringHashMap(User)
std.StringHashMap(std.ArrayList(u8))
```

## A Practical Example: Counting Words

A common hash map use case is counting things.

Suppose we have words:

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

We want:

```text
zig  -> 3
c    -> 2
rust -> 1
```

Here is one way:

```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",
        "rust",
        "zig",
        "c",
    };

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

    for (words) |word| {
        const old_count = counts.get(word) orelse 0;
        try counts.put(word, old_count + 1);
    }

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

The important line is:

```zig
const old_count = counts.get(word) orelse 0;
```

This means:

```text
if word exists, use its count
otherwise, use 0
```

Then we store the new count:

```zig
try counts.put(word, old_count + 1);
```

## Using getOrPut

There is a better pattern for many update operations: `getOrPut`.

It looks up a key. If the key does not exist, it creates a new entry.

Example:

```zig
const result = try counts.getOrPut(word);
```

The result tells you whether the entry already existed.

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

result.value_ptr.* += 1;
```

Full example:

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

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

    result.value_ptr.* += 1;
}
```

This avoids doing a separate lookup and then a separate insert.

## Why getOrPut Uses Pointers

`getOrPut` gives access to the stored value through a pointer:

```zig
result.value_ptr.*
```

That means you can modify the value directly inside the map.

Example:

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

This changes the value stored in the map itself.

You are not modifying a copy.

## Memory Ownership of Keys and Values

This is one of the most important parts of using hash maps in Zig.

The map stores keys and values, but it does not automatically know whether they own memory.

Consider this:

```zig
try map.put("name", "alice");
```

This is fine because `"name"` and `"alice"` are string literals. They live for the whole program.

But this is different:

```zig
const name = try allocator.dupe(u8, "alice");
try map.put(name, 123);
```

Now `name` is heap memory.

When you remove it from the map or destroy the map, you may need to free it yourself.

`deinit()` frees the hash map’s internal table. It does not automatically free heap memory owned by each key or value.

## Freeing Owned Keys

If your map owns string keys, you must free them before `deinit`.

Example pattern:

```zig
var it = map.iterator();

while (it.next()) |entry| {
    allocator.free(entry.key_ptr.*);
}

map.deinit();
```

This matters for programs that duplicate strings, parse files, or build dynamic data structures.

Zig does not guess ownership for you.

## Pointers Can Become Invalid

Like `ArrayList`, a hash map may resize.

When it grows, entries may move.

So this is dangerous:

```zig
const result = try map.getOrPut("alice");
const ptr = result.value_ptr;

try map.put("bob", 95);

// ptr may no longer be valid if the map resized
ptr.* = 123;
```

Do not keep pointers into a hash map across operations that may resize the map.

Use them immediately.

## Load Factor

A hash map has a capacity, like an `ArrayList`.

But instead of tracking only length, it also cares about how full the table is.

When the map gets too full, collisions become more likely.

A collision happens when two keys want to use the same place in the table.

The map handles collisions internally, but too many collisions make lookups slower.

So the map grows before it becomes completely full.

That is what `max_load_percentage` controls in the lower-level `std.HashMap` type.

As a beginner, you rarely need to tune it.

## HashMap Performance

Hash maps are fast for lookup, insertion, and removal.

Usually, these operations are close to constant time.

That means looking up one key in a map with 10,000 entries is not much slower than looking up one key in a map with 100 entries.

But this depends on good hashing and enough capacity.

For most normal programs, `AutoHashMap` and `StringHashMap` are enough.

## HashMap vs ArrayList

Use an `ArrayList` when you care about position:

```text
item 0
item 1
item 2
```

Use a `HashMap` when you care about lookup by key:

```text
username -> user
file path -> file info
token text -> token count
id -> object
```

A simple comparison:

| Structure | Best for | Lookup style |
|---|---|---|
| `ArrayList` | Ordered list of items | By index |
| `HashMap` | Key-value storage | By key |
| `StringHashMap` | String keys | By string |

## Common Beginner Mistakes

The first common mistake is assuming iteration order is stable. It is not.

The second mistake is forgetting that `put` can replace an existing value. If the old value owns memory, you may need to free it first.

The third mistake is keeping pointers into the map after inserting more items.

The fourth mistake is assuming `deinit()` frees everything. It frees the map’s internal storage, but not necessarily memory owned by keys or values.

## A Useful Mental Model

Think of a hash map as a fast lookup table.

```text
key -> value
```

Examples:

```text
"id-001" -> User
"main.zig" -> File
"while" -> TokenKind.keyword_while
42 -> Object
```

The key must be hashable and comparable.

The value can be almost anything.

The map owns its internal table. Your program must still decide who owns the data stored inside the table.

## Summary

A `HashMap` stores values by key.

In Zig, the most common beginner choices are:

```zig
std.AutoHashMap(K, V)
```

for ordinary key types, and:

```zig
std.StringHashMap(V)
```

for string keys.

Hash maps are useful for counting, indexing, caching, grouping, and fast lookup.

The main rules are simple:

initialize with an allocator, use `try` when inserting, handle missing keys with optionals, do not depend on iteration order, and clean up owned memory explicitly.