get and every put is constant time;ArrayList would quietly hand you a bag of dangling pointers;comptime type function, the same shape we have leaned on since the collections episodes;std.AutoHashMap comfort from episode 22 and the allocator discipline from episodes 7 and 114 (memory pools make a cameo);Learn Zig Series):Last episode closed on a cliff-hanger. Union-find, I said, only ever grows -- you can merge groups forever, but there is no split, no forget, no remove. And then I pointed at the exact opposite pressure: a cache sitting in front of a slow database or a network call, with a hard size limit, that must throw something away every time it fills up. The victim is the entry you have not touched in the longest while -- the least recently used one. That is today's structure, the LRU cache, and it is the single most common place where a hash map and a linked list are forced to get married and made to dance. But we owe a debt first: last episode left you three union-find exercises, and I promised full code, not hand-waving ;-)
Exercise 1 -- union by rank in stead of size. The claim from last episode was that either heuristic gives the near-constant bound, so let us prove it by swapping the rule. Rather than tracking a subtree's element count, rank tracks an upper bound on its height: attach the lower-rank root under the higher-rank one, and only bump a rank when two equal-rank trees merge (because that is the one case where the taller result genuinely grew a level). Everything else -- path compression in find, the count of remaining components, the "already connected" boolean -- stays exactly as it was:
const std = @import("std");
const DisjointSetRank = struct {
gpa: std.mem.Allocator,
parent: []usize,
rank: []u8,
count: usize,
fn init(gpa: std.mem.Allocator, n: usize) !DisjointSetRank {
const parent = try gpa.alloc(usize, n);
errdefer gpa.free(parent);
const rank = try gpa.alloc(u8, n);
for (parent, 0..) |*p, i| p.* = i;
@memset(rank, 0);
return .{ .gpa = gpa, .parent = parent, .rank = rank, .count = n };
}
fn deinit(self: *DisjointSetRank) void {
self.gpa.free(self.parent);
self.gpa.free(self.rank);
}
fn find(self: *DisjointSetRank, x: usize) usize {
var root = x;
while (self.parent[root] != root) root = self.parent[root];
var cur = x;
while (self.parent[cur] != root) {
const next = self.parent[cur];
self.parent[cur] = root; // path compression, unchanged
cur = next;
}
return root;
}
fn connected(self: *DisjointSetRank, a: usize, b: usize) bool {
return self.find(a) == self.find(b);
}
fn unite(self: *DisjointSetRank, a: usize, b: usize) bool {
const ra = self.find(a);
const rb = self.find(b);
if (ra == rb) return false;
if (self.rank[ra] < self.rank[rb]) {
self.parent[ra] = rb;
} else if (self.rank[ra] > self.rank[rb]) {
self.parent[rb] = ra;
} else {
self.parent[rb] = ra;
self.rank[ra] += 1; // equal ranks -> the survivor grew one level
}
self.count -= 1;
return true;
}
};
test "union by rank keeps trees shallow and tracks components" {
const gpa = std.testing.allocator;
var ds = try DisjointSetRank.init(gpa, 8);
defer ds.deinit();
try std.testing.expect(ds.unite(0, 1));
try std.testing.expect(ds.unite(2, 3));
try std.testing.expect(ds.unite(1, 3));
try std.testing.expect(!ds.unite(0, 2)); // already joined
try std.testing.expect(ds.connected(0, 3));
try std.testing.expectEqual(@as(usize, 5), ds.count);
}
Notice rank is a u8, not a usize: because rank only rises when two equal-rank trees meet, it is bounded by log2(n), so even a u8 (max 255) covers a set with more elements than any machine will ever hold. That is the kind of tight, honest sizing Zig invites you to think about. Drop this into last episode's property test in place of the size-based version and it agrees with QuickFind on all 200 random scenarios -- the two heuristics are interchangeable at the level of correctness, and differ only in constant factors.
Exercise 2 -- a rollback-able disjoint set. Some algorithms (offline dynamic connectivity, DSU-on-tree) unite and then need to undo the last union. Path compression makes that impossible to reverse cheaply -- it rewrites pointers all over the tree on every find, so there is no single change to walk back. The trick is to give up compression, lean entirely on union-by-rank to keep the trees shallow, and record just enough about each merge to reverse it: which root got a new parent, and whether the survivor's rank was bumped. Push that record on an undo stack; rollback pops it and restores both fields:
const DsuRollback = struct {
gpa: std.mem.Allocator,
parent: []usize,
rank: []u8,
history: std.ArrayList(Record),
const Record = struct { child_root: usize, parent_root: usize, rank_bumped: bool };
fn init(gpa: std.mem.Allocator, n: usize) !DsuRollback {
const parent = try gpa.alloc(usize, n);
errdefer gpa.free(parent);
const rank = try gpa.alloc(u8, n);
for (parent, 0..) |*p, i| p.* = i;
@memset(rank, 0);
return .{ .gpa = gpa, .parent = parent, .rank = rank, .history = .empty };
}
fn deinit(self: *DsuRollback) void {
self.gpa.free(self.parent);
self.gpa.free(self.rank);
self.history.deinit(self.gpa);
}
fn find(self: *const DsuRollback, x: usize) usize {
var root = x;
while (self.parent[root] != root) root = self.parent[root];
return root; // NO compression -> find is a pure read, safe to undo around
}
fn unite(self: *DsuRollback, a: usize, b: usize) !bool {
var ra = self.find(a);
var rb = self.find(b);
if (ra == rb) return false;
if (self.rank[ra] > self.rank[rb]) {
const tmp = ra;
ra = rb;
rb = tmp; // ensure ra is the lower-rank root; it hangs under rb
}
const bump = self.rank[ra] == self.rank[rb];
self.parent[ra] = rb;
if (bump) self.rank[rb] += 1;
try self.history.append(self.gpa, .{ .child_root = ra, .parent_root = rb, .rank_bumped = bump });
return true;
}
fn rollback(self: *DsuRollback) void {
const rec = self.history.pop() orelse return;
self.parent[rec.child_root] = rec.child_root; // re-orphan the child root
if (rec.rank_bumped) self.rank[rec.parent_root] -= 1;
}
};
test "rollback undoes exactly the last union" {
const gpa = std.testing.allocator;
var ds = try DsuRollback.init(gpa, 5);
defer ds.deinit();
_ = try ds.unite(0, 1);
_ = try ds.unite(2, 3);
ds.rollback(); // undo the (2,3) merge only
try std.testing.expect(ds.find(2) != ds.find(3)); // gone
try std.testing.expect(ds.find(0) == ds.find(1)); // first merge still standing
}
Because find here never mutates -- look, it takes *const DsuRollback, the exact opposite of the compressing version from last episode -- undoing is trivially just "put the two fields back". That is the deal you strike: you trade the inverse-Ackermann magic for O(log n) finds, and in return you get perfect reversibility. unite, unite, rollback leaves the structure byte-for-byte identical to having done just the first unite. Nota bene: this is why offline algorithms love it -- they can explore a branch, then unwind it cleanly.
Exercise 3 -- counting islands. Given a grid of booleans (true = land), how many separated blobs of land are there? Map each cell (r, c) to the id r * cols + c, start with a running island count equal to the number of land cells, then union each land cell with its land neighbours to the right and below -- one pass is enough, because every horizontal or vertical adjacency gets seen from its top-left member. Each merge that actually joins two different blobs drops the count by one:
const IslandDsu = struct {
gpa: std.mem.Allocator,
parent: []usize,
size: []usize,
fn init(gpa: std.mem.Allocator, n: usize) !IslandDsu {
const parent = try gpa.alloc(usize, n);
errdefer gpa.free(parent);
const size = try gpa.alloc(usize, n);
for (parent, 0..) |*p, i| p.* = i;
@memset(size, 1);
return .{ .gpa = gpa, .parent = parent, .size = size };
}
fn deinit(self: *IslandDsu) void {
self.gpa.free(self.parent);
self.gpa.free(self.size);
}
fn find(self: *IslandDsu, x: usize) usize {
var root = x;
while (self.parent[root] != root) root = self.parent[root];
var cur = x;
while (self.parent[cur] != root) {
const next = self.parent[cur];
self.parent[cur] = root;
cur = next;
}
return root;
}
fn unite(self: *IslandDsu, a: usize, b: usize) bool {
const ra = self.find(a);
const rb = self.find(b);
if (ra == rb) return false;
if (self.size[ra] < self.size[rb]) {
self.parent[ra] = rb;
self.size[rb] += self.size[ra];
} else {
self.parent[rb] = ra;
self.size[ra] += self.size[rb];
}
return true;
}
};
fn countIslands(gpa: std.mem.Allocator, grid: []const bool, rows: usize, cols: usize) !usize {
std.debug.assert(grid.len == rows * cols);
var ds = try IslandDsu.init(gpa, rows * cols);
defer ds.deinit();
var islands: usize = 0;
for (grid) |cell| {
if (cell) islands += 1;
}
for (0..rows) |r| {
for (0..cols) |c| {
const idx = r * cols + c;
if (!grid[idx]) continue;
if (c + 1 < cols and grid[idx + 1]) {
if (ds.unite(idx, idx + 1)) islands -= 1;
}
if (r + 1 < rows and grid[idx + cols]) {
if (ds.unite(idx, idx + cols)) islands -= 1;
}
}
}
return islands;
}
test "counting islands finds the separated land blobs" {
const gpa = std.testing.allocator;
const grid = [_]bool{
true, true, false, false,
true, false, false, true,
false, false, true, true,
false, true, false, false,
};
try std.testing.expectEqual(@as(usize, 3), try countIslands(gpa, &grid, 4, 4));
}
Three blobs on that little 4x4: the L-shape in the top-left corner, the three-cell hook on the right edge, and the lone cell down at the bottom -- exactly what your eye counts. This is what image processing calls blob labelling or connected-component labelling, and here it is in a dozen lines because union-find does all the grouping for us. Debt paid ;-) Now, the cache.
The interface we want is dead simple, and it is the same one behind an operating system's page cache, a browser's image cache, a database buffer pool, and half the @lru_cache-style decorators in every language:
Both operations must be O(1). That "both" is the whole difficulty. A hash map gives you O(1) get and put on its own -- but it has no notion of order, so "which key is the least recently used?" would mean scanning every entry, which is O(n). You might reach for a timestamp on each entry and scan for the minimum, like this:
const std = @import("std");
// The tempting but WRONG shape: a flat array of slots, each stamped with a "tick".
const Slot = struct { key: u32, value: u32, used: u64 };
fn evictOldest(slots: []const Slot) usize {
var oldest: usize = 0;
for (slots, 1..) |s, i| {
if (s.used < slots[oldest].used) oldest = i;
}
return oldest; // O(n) scan on EVERY eviction -- the wall we refuse to hit
}
That works, and for a cache of eight entries nobody will notice. But a real cache holds thousands or millions of entries and evicts constantly under load, and an O(n) scan on every eviction turns your fast-path cache into a slow-path liability. We saw the same "obvious but quadratic" trap with quick-find last episode. A linked list, meanwhile, gives you O(1) reordering and O(1) removal from either end -- but it has no way to find a key without walking the whole thing. So: the hash map can find but not order, the list can order but not find. Marry them.
Here is the design, and once it clicks it never leaves you. We keep a doubly linked list of nodes where each node holds a key and a value. The list is kept in recency order: the most-recently-used node sits at the head, the least-recently-used at the tail. Separately, we keep a hash map from key to a pointer to that key's node in the list. Now watch how both operations collapse to constant time:
prev/next pointers.We built doubly linked lists back in episode 106 for exactly this reason: cheap removal from the middle. And we need doubly linked, not singly, because to unlink a node given only a pointer to it, you must fix up its predecessor's next, which means you need the node's prev. Here is the node, and the whole generic cache:
fn LruCache(comptime K: type, comptime V: type) type {
return struct {
const Self = @This();
const Node = struct {
key: K,
value: V,
prev: ?*Node = null,
next: ?*Node = null,
};
gpa: std.mem.Allocator,
capacity: usize,
map: std.AutoHashMap(K, *Node),
head: ?*Node = null, // most recently used
tail: ?*Node = null, // least recently used
fn init(gpa: std.mem.Allocator, capacity: usize) Self {
std.debug.assert(capacity >= 1);
return .{
.gpa = gpa,
.capacity = capacity,
.map = std.AutoHashMap(K, *Node).init(gpa),
};
}
fn deinit(self: *Self) void {
var cur = self.head;
while (cur) |node| {
const next = node.next;
self.gpa.destroy(node);
cur = next;
}
self.map.deinit();
}
// unlink a node from the list (leaves the map alone)
fn detach(self: *Self, node: *Node) void {
if (node.prev) |p| p.next = node.next else self.head = node.next;
if (node.next) |n| n.prev = node.prev else self.tail = node.prev;
node.prev = null;
node.next = null;
}
// splice a detached node in at the head (the most-recently-used end)
fn pushFront(self: *Self, node: *Node) void {
node.prev = null;
node.next = self.head;
if (self.head) |h| h.prev = node;
self.head = node;
if (self.tail == null) self.tail = node;
}
fn get(self: *Self, key: K) ?V {
const node = self.map.get(key) orelse return null;
self.detach(node);
self.pushFront(node);
return node.value;
}
fn put(self: *Self, key: K, value: V) !void {
if (self.map.get(key)) |node| {
node.value = value;
self.detach(node);
self.pushFront(node);
return;
}
const node = try self.gpa.create(Node);
errdefer self.gpa.destroy(node);
node.* = .{ .key = key, .value = value };
try self.map.put(key, node);
self.pushFront(node);
if (self.map.count() > self.capacity) self.evictLru();
}
fn evictLru(self: *Self) void {
const victim = self.tail orelse return;
self.detach(victim);
_ = self.map.remove(victim.key);
self.gpa.destroy(victim);
}
fn len(self: *const Self) usize {
return self.map.count();
}
};
}
A few things worth pausing on. detach and pushFront are the two list primitives, and every public method is just a short composition of them -- the boring, mechanical pointer surgery lives in exactly one place each, which is how you keep this class of bug-prone code honest. In put, the errdefer self.gpa.destroy(node) guards the window between create and the map.put succeeding: if the map fails to grow, the freshly created node is destroyed and we do not leak it. And evictLru reads the victim's key before freeing the node -- because we need that key to erase the map entry, and touching freed memory is a sin Zig will happily let you commit if you get the order wrong. The capacity >= 1 assert in init rules out the degenerate zero-capacity cache that could never hold anything.
Let us make the recency logic concrete. Capacity two, three keys, and one deliberate get in the middle to flip which key is "old":
test "lru evicts the least recently used entry" {
const gpa = std.testing.allocator;
var cache = LruCache(u32, u32).init(gpa, 2);
defer cache.deinit();
try cache.put(1, 10);
try cache.put(2, 20);
// touch key 1 -> now 1 is most-recent, 2 is the LRU
try std.testing.expectEqual(@as(?u32, 10), cache.get(1));
// inserting a third key overflows capacity 2 -> evict the LRU (key 2)
try cache.put(3, 30);
try std.testing.expectEqual(@as(?u32, null), cache.get(2)); // evicted
try std.testing.expectEqual(@as(?u32, 10), cache.get(1)); // survived
try std.testing.expectEqual(@as(?u32, 30), cache.get(3)); // just added
try std.testing.expectEqual(@as(usize, 2), cache.len());
}
The single get(1) in the middle is what decides key 2's fate. Without it, keys 1 and 2 would be equally stale and 1 (the older insertion) would be the one to go. That is the entire personality of an LRU cache: access is what keeps you alive. Comment out that get line and re-run, and you will watch key 1 get evicted in stead -- a great five-second experiment to convince yourself the ordering does what you think.
Here is the load-bearing detail, and it is the exact cousin of last episode's "find is secretly a mutation" surprise. Our map stores *Node -- raw pointers into the list -- and we hand each node its own allocation with gpa.create. It is very tempting, coming from a language with a growable vector, to store the nodes inside a std.ArrayList(Node) and keep indices around in stead of pointers. Do not. The moment that ArrayList outgrows its capacity, it reallocates its backing buffer to a new address, and every pointer you were holding into the old buffer is now dangling. Zig will not stop you -- it trusts you -- and you will get a use-after-free that only triggers once the list happens to grow. Individually heap-allocated nodes have stable addresses; that stability is the whole reason the design works.
If per-node create/destroy churn worries you (and in a hot cache it legitimately might), the right answer is not to abandon stable addresses -- it is to hand out fixed-size nodes from a memory pool, which we built back in episode 114. std.heap.MemoryPool gives you exactly that: O(1) create and destroy of a single fixed type, with addresses that stay put:
const PoolNode = struct {
key: u32,
value: u32,
prev: ?*PoolNode = null,
next: ?*PoolNode = null,
};
test "a memory pool hands out fixed-size nodes with stable addresses" {
const gpa = std.testing.allocator;
var pool: std.heap.MemoryPool(PoolNode) = .empty;
defer pool.deinit(gpa);
const a = try pool.create(gpa);
const b = try pool.create(gpa);
a.* = .{ .key = 1, .value = 10 };
b.* = .{ .key = 2, .value = 20, .prev = a };
a.next = b;
// the pointer we stored in `a` still resolves after further allocations
try std.testing.expectEqual(@as(u32, 20), a.next.?.value);
pool.destroy(b);
pool.destroy(a);
}
Swapping self.gpa.create(Node)/self.gpa.destroy(node) for self.pool.create(self.gpa)/self.pool.destroy(node) is a two-line change to the cache and buys you far less allocator traffic under load, without touching a single line of the list logic. Same interface, faster engine -- the profiling-before-optimizing discipline from episode 34 will tell you whether your workload actually needs it.
The pointer surgery in detach/pushFront/evictLru is exactly the sort of code where an off-by-one in the prev/next fixups hides for months. So we do what we did for union-find: build a stupidly obvious reference implementation and let a property test hammer both with the same random operations, asserting they always agree. The reference keeps an ArrayList of entries in recency order -- front is LRU, back is MRU -- and pays O(n) for everything, which is fine because obviousness, not speed, is its whole job:
fn NaiveLru(comptime K: type, comptime V: type) type {
return struct {
const Self = @This();
const Entry = struct { key: K, value: V };
gpa: std.mem.Allocator,
capacity: usize,
items: std.ArrayList(Entry), // items[0] = LRU, last = MRU
fn init(gpa: std.mem.Allocator, capacity: usize) Self {
return .{ .gpa = gpa, .capacity = capacity, .items = .empty };
}
fn deinit(self: *Self) void {
self.items.deinit(self.gpa);
}
fn indexOf(self: *Self, key: K) ?usize {
for (self.items.items, 0..) |e, i| {
if (e.key == key) return i;
}
return null;
}
fn get(self: *Self, key: K) ?V {
const i = self.indexOf(key) orelse return null;
const e = self.items.orderedRemove(i);
self.items.appendAssumeCapacity(e); // move to MRU end (room is guaranteed)
return e.value;
}
fn put(self: *Self, key: K, value: V) !void {
if (self.indexOf(key)) |i| {
_ = self.items.orderedRemove(i);
}
try self.items.append(self.gpa, .{ .key = key, .value = value });
if (self.items.items.len > self.capacity) {
_ = self.items.orderedRemove(0); // evict the front = LRU
}
}
};
}
test "property: LRU cache agrees with the naive reference" {
const gpa = std.testing.allocator;
var prng = std.Random.DefaultPrng.init(0xCACE);
const rand = prng.random();
var round: usize = 0;
while (round < 200) : (round += 1) {
const cap = rand.intRangeAtMost(usize, 1, 8);
var fast = LruCache(u32, u32).init(gpa, cap);
defer fast.deinit();
var slow = NaiveLru(u32, u32).init(gpa, cap);
defer slow.deinit();
const ops = rand.intRangeAtMost(usize, 0, 60);
for (0..ops) |_| {
const key = rand.uintLessThan(u32, 12);
if (rand.boolean()) {
const val = rand.int(u32);
try fast.put(key, val);
try slow.put(key, val);
} else {
try std.testing.expectEqual(slow.get(key), fast.get(key));
}
}
// final sweep: both must agree about every key in the domain
for (0..12) |k| {
const key: u32 = @intCast(k);
try std.testing.expectEqual(slow.get(key), fast.get(key));
}
}
}
Two hundred rounds, capacities from one to eight, up to sixty interleaved puts and gets against a twelve-key domain -- and the pointer-juggling cache never once disagrees with the array that anyone can read at a glance. Note the subtle discipline in the final sweep: get mutates recency, so calling it on both structures in lock-step keeps their orderings identical; if the fast cache ever reordered differently, the very next comparison would catch it. Because it all runs on std.testing.allocator, a single leaked node -- one missing destroy in deinit or evictLru -- fails the round too. That is two classes of bug pinned by one test.
In C, this is the textbook "intrusive list plus hash table" and it is genuinely pleasant: a struct Node with prev/next and a key/value, a hash table mapping key to Node*, and the same detach/push-front dance. No allocator threading, no deinit, but also nobody reminding you to free the evicted node or to erase its hash entry before you free it -- the exact ordering bug our evictLru is written to avoid. Every serious C codebase has its own hand-rolled version, usually with the list pointers embedded directly in the cached struct.
In Rust, the naive LRU is one of the most famous "why won't this compile?" rites of passage in the language. A doubly linked list means every node is pointed at by two others (its neighbours) plus the map, and Rust's ownership model hates shared mutable aliasing with a passion. The honest-but-heavy fix is Rc<RefCell<Node>> everywhere, paying reference-counting and runtime borrow-checking for the privilege; the fast fix that real crates like lru actually ship is to store nodes in a Vec (an arena) and use integer indices in stead of pointers -- sidestepping the borrow checker by never holding a raw reference across a mutation. Which, notice, is the precise pattern our Zig trap warned against, made safe there only because the arena never frees individual slots and never reallocates out from under you. Same idea, opposite verdict on whether the compiler lets you.
In Go, it is almost boring, in the good way: the standard library ships container/list, a ready-made doubly linked list, and a map[K]*list.Element alongside it -- the exact marriage, handed to you. The garbage collector means no destroy, no eviction-ordering hazard, no dangling anything. You pay for it with GC pressure and pointer-chasing that the collector must trace, but for most services that is a trade worth making. Four languages, one structure, and the same load-bearing truth in every one: an LRU cache is a hash map and a doubly linked list, kept in sync so that finding and ordering are both O(1). Bam, jonguh ;-)
A time-to-live (TTL) cache. Extend LruCache so each node also stores an expiry tick, and add a getFresh(key, now) that returns null (and evicts the node) if now is past its expiry, even when the key is present. Decide deliberately: should a plain get still resurrect an expired-but-not-yet-swept entry, or not? Write a test that inserts a key, advances now past its TTL, and confirms getFresh reports a miss and shrinks len().
Swap in the memory pool. Take the LruCache above and replace the gpa.create/gpa.destroy calls with a std.heap.MemoryPool(Node) field, initialised in init and torn down in deinit. Re-run the property test unchanged -- it must still pass, and still be leak-clean on std.testing.allocator. The point is that the eviction policy and the node allocation strategy are independent axes you can vary without touching each other.
Segmented LRU (a "2Q"-lite). A pure LRU is fooled by a one-off scan that floods the cache with keys you will never see again, evicting your genuinely hot entries. Build a two-list variant: new keys enter a small "probationary" list, and only get promoted into the "protected" list on their second access. Evict from the probationary tail first. Test that a single sweep of never-repeated keys leaves a previously-promoted hot key untouched, where a plain LRU would have thrown it out.
We now have a cache that finds and orders in O(1), evicts the coldest entry the instant it runs out of room, and rests on a marriage of a hash map and a doubly linked list -- with the pointer-stability discipline that keeps that marriage from turning into a use-after-free. But notice the quiet assumption baked into every line: there is one cache, living in one process, on one machine. The moment your data outgrows a single box -- when you need a dozen cache servers, or a hundred, and every key has to land on a predictable one of them -- a fresh problem appears that no amount of clever list-splicing solves. A naive hash(key) % server_count looks fine until the day you add or lose a server, and suddenly almost every key maps somewhere new and your whole cache goes cold at once. Spreading keys across a changing set of nodes so that adding or removing one node reshuffles as few keys as possible is a genuinely elegant idea with a name, and it is where we go next ;-)
Bedankt voor het lezen -- en tot de volgende keer! ;-)
@scipio