Hash Tables — Programuoki

Theory

transit: choosing an index

transit — the Vilnius public-transport journey planner — faces the question you just answered: how to index 1,531 stops. It answered twice, for two different questions, and one of those answers is wrong in Lithuanian — deliberately, permanently, with tests that stop anyone fixing it.

The headline: bytes are not letters

Remember lesson 7 of the structured-programming course? len("ąžuolas") = 9 with 7 letters in it. That was that course's centrepiece gotcha. Here is what happens when the same mistake reaches a search index.

Stop search has to satisfy three requirements:

typing "zirmunu"  must find "Žirmūnų"   (nobody types diacritics into a search box)
typing "žirmūnų"  must find "Žirmūnų"   (but if they do, it must still work)
typing "ŽIRMŪNŲ"  must find "Žirmūnų"   (case-insensitive in both directions)

The first attempt is the familiar C-style loop over bytes:

func foldBytes(s string) string {
	b := []byte(s)
	for i := 0; i < len(b); i++ {
		if b[i] >= 'A' && b[i] <= 'Z' {
			b[i] += 'a' - 'A'
		}
	}
	return string(b)
}

And here is what it produces:

"Ž"  bytes C5 BD  runes 1  len 2
"ž"  bytes C5 BE  runes 1  len 2

"Katedros"  foldBytes -> "katedros"     Fold -> "katedros"
"Žirmūnų"   foldBytes -> "Žirmūnų"      Fold -> "zirmunu"
"ŽIRMŪNŲ"   foldBytes -> "ŽirmŪnŲ"      Fold -> "zirmunu"

Look at "ŽirmŪnŲ". The Latin letters lowercased and the Lithuanian ones did not. Not because a case was forgotten, but because Ž is not a byte: it is C5 BD, and ž is C5 BE. They differ only in the second byte, so b[i] >= 'A' && b[i] <= 'Z' can never connect them — not with a patch, not with an extra condition.

The second failure is the same fact in a different place. A trie branches per byte:

"Žirmūnų": 10 bytes, 7 runes -> a byte trie is 10 levels deep, a rune trie 7
the node at depth 1 holds byte 0xC5, which is not a letter anyone typed

Three extra levels, and every third node is half of a UTF-8 sequence. Not a letter. Not something a user could have typed.

On English data both versions behave identically — which is exactly why the bug survives testing. "Katedros" goes through either function correctly. A student types "žirmūnai" in Lithuanian and gets nothing.

The fix is to iterate runes, because for _, r := range s decodes UTF-8:

for _, r := range s {          // rune iteration
	r = unicode.ToLower(r) // Unicode-aware: 'Ž' -> 'ž', not a no-op
	if f, ok := ltFold[r]; ok {
		r = f
	}
	b.WriteRune(r)
}

How `transit` stops anyone "fixing" it

The broken version stays in the repository forever, because it is the first half of the lesson. But it cannot leak into the running server by accident: it lives in search_bytetrie_demo_test.go, and Go compiles _test.go files only under go test. The server, the CLI and any future diagnostics cannot so much as mention it — the build would fail.

That is a compile-time guarantee rather than a naming convention or a code-review rule.

And two tests demand that it stays broken:

$ go test ./internal/store/ -run 'TestByteTrieFailsOnRealFeed|TestFoldBytesIsBrokenOnLithuanian' -v
=== RUN   TestFoldBytesIsBrokenOnLithuanian
--- PASS: TestFoldBytesIsBrokenOnLithuanian (0.00s)
=== RUN   TestByteTrieFailsOnRealFeed
    search_realfeed_test.go:99: byte trie nodes=4850, rune trie nodes=4173
--- PASS: TestByteTrieFailsOnRealFeed (13.31s)

The same shape as lesson 7's selection sort and lesson 8's quicksort: the defect is pinned down by a test so that it stays visible.

Where the hash table actually won

Now the structure itself. What is a hash table worth against a linear list of stops? In isolation (our capture, docs/reference/transit-benchmarks.md):

one stop lookup, n = 1,531	our capture
linear	1.22 µs
hash	7.02 ns
ratio	174×

174× looks conclusive. And it is not enough, which the transit repository says itself: 1.22 µs and 7 ns are both zero to a human. On a single lookup the difference is imperceptible.

The argument is elsewhere. While the feed is loading, every stop_time event has to resolve its stop — about 207,000 lookups during one boot. There the difference shows:

full feed load	our capture (3 runs)
linear index	1549 ms
hash index	1200 ms
delta	~350 ms

A third of a second on every server start. transit's README states 468 ms; on our machine it came out ~25% lower, and the spread across three runs is 165 ms, so there is no point reaching for a figure more precise than "about a third of a second".

The structure was justified not by the isolated ratio but by where it is used.

A different index for a different question

There is a second structure: a trie, answering a different question. A hash table knows "is there a stop called this"; a trie knows "which stops start with these letters" — which is what a search box does while someone is typing.

You will not build one. But it is worth seeing how the decision not to use it gets made.

On a single autocomplete query the trie wins clearly — from 7.9× (3 characters) to 22× (8 characters). But a user does not issue one query: they type, and every keystroke is a new query. Over the whole "zirmunai" session (8 keystrokes):

"zirmunai" session	`transit`'s machine	our machine
linear	130 µs	~135 µs
rune trie	250 µs	~42 µs
winner	linear	trie, by ~3.2×

The answer inverted. On their machine the trie lost the session by ~120 µs; on ours it won by ~93 µs. What differs is not the magnitude but the direction.

And the verdict is the same on both, because the argument was never the ratio:

there the trie costs ~120 µs, here it saves ~93 µs;
both numbers are a tenth of a millisecond;
a typing session takes a human on the order of ~160 ms, and in a deployed app there is a network round trip on top;
so the entire dispute is happening three orders of magnitude below the thing it is competing with.

Meanwhile the trie costs 777 KB against 113 KB of memory (6.9×) and 3.1× as long to build. That is a real bill for a number nobody can feel on either machine.

The right structure for that question — and still not worth it at this size.

Compare this with lesson 6

In lesson 6 the measurement also depended on the machine: the crossover between linear and binary search moves. But there it changes the decision, because the measurement is taken right at the boundary.

Here the measurement moves too — it inverts outright — and the decision does not change, because the difference is three orders away from any boundary.

Telling those two apart is the skill:

Do not ask "does my number match somebody else's". Ask "is my number near a decision boundary". If it is, measure on your own machine. If it is not, someone else's measurement can disagree with yours entirely and change nothing.