# hashmap

> written against zig 0.15.

zig's hash maps for key-value lookup. two flavors parallel the arraylist split: `StringHashMap` stores the allocator, `StringHashMapUnmanaged` passes it to each method.

## managed vs unmanaged

```zig
// managed — stores allocator, slightly more convenient
var map = std.StringHashMap([]const u8).init(allocator);
defer map.deinit();

try map.put("key", "value");

// unmanaged — pass allocator to each method (like ArrayList)
var map: std.StringHashMapUnmanaged([]const u8) = .empty;
defer map.deinit(allocator);

try map.put(allocator, "key", "value");
```

unmanaged is the better default for the same reasons as ArrayList — no stored allocator, statically initializable. use managed when passing as function parameter (avoids threading the allocator alongside it).

## O(1) block index

the pattern that fixed zat's 79-second MST walk: build a lookup table during CAR parse, query it during tree traversal.

```zig
pub const Car = struct {
    blocks: []const Block,
    block_index: std.StringHashMapUnmanaged([]const u8) = .empty,
};

// during parse: populate index alongside the block array
var block_index: std.StringHashMapUnmanaged([]const u8) = .empty;
while (pos < data.len) {
    // ... parse CID and content ...
    try blocks.append(allocator, .{ .cid_raw = cid_bytes, .data = content });
    try block_index.put(allocator, cid_bytes, content);
}

// during walk: O(1) lookup by CID
const data = block_index.get(cid_bytes) orelse return error.BlockNotFound;
```

the key insight: CID bytes are already unique identifiers and the block data they point to is owned by the CAR buffer (arena-allocated). no copies needed — both key and value are slices into existing memory.

before this: linear scan through 243k blocks, called once per MST node (~50k nodes). ~12 billion comparisons. after: hash lookup.

see: [zat/car.zig](https://tangled.sh/@zzstoatzz.io/zat/tree/main/src/internal/repo/car.zig) (zat is a library of atproto building blocks for zig)

## key ownership

from the stdlib: "key memory is managed by the caller. keys and values will not automatically be freed."

this means:
- keys must outlive the map
- if keys are heap-allocated, you free them — the map won't
- for string keys pointing into a long-lived buffer (like parsed data), this is free — the buffer already owns the memory

## HashMap vs ArrayHashMap

`HashMap` (and `StringHashMap`): hash-table backed. O(1) lookup, unordered iteration.

`ArrayHashMap` (and `StringArrayHashMap`): array-backed with hash index. O(1) lookup, **insertion-order** iteration, slightly more memory.

use HashMap when you only care about lookup. use ArrayHashMap when iteration order matters (e.g., rendering parameters in a URL).

## generic keys with AutoHashMap

for non-string keys, `AutoHashMap` generates hash/eql from the key type:

```zig
var map = std.AutoHashMap(u64, MyStruct).init(allocator);
defer map.deinit();

try map.put(42, my_value);
```

works for integers, enums, and types with `hash` and `eql` methods.

## sources
- zat — src/internal/repo/car.zig, 79-second MST walk fix