{adamcoding}
← The Machine and the Market
Part II
09
Chapter 9

Lookup by Name

The problem

You have 500,000 trades across 200 instruments. "Give me every trade in BTCUSD." Scanning all 500,000 works and is slow, and it gets slower as you add trades.

You want lookup whose cost doesn't grow with the size of the collection. That's a hash table, and it's the most important data structure in programming.

Using Go's map

go
positions := map[string]float64{
	"BTCUSD": 0.5,
	"ETHUSD": 12.0,
	"EURUSD": -50000.0,
}

fmt.Println(positions["BTCUSD"])       // 0.5

positions["SOLUSD"] = 100.0            // add
delete(positions, "EURUSD")            // remove
fmt.Println(len(positions))            // 3

Missing keys return the zero value rather than an error:

go
fmt.Println(positions["DOGEUSD"])      // 0

Which is ambiguous - is the position zero, or absent? Use the two-value form:

go
qty, exists := positions["DOGEUSD"]
if !exists {
	fmt.Println("no position")
}

This "comma ok" pattern appears throughout Go. Get used to it.

How it actually works

Here's the mechanism, and understanding it explains both why maps are fast and how they can stop being fast.

A hash table is an array of buckets plus a hash function that turns a key into a bucket number.

   "BTCUSD"  ──hash──►  3948572034  ──% 8──►  bucket 2
   "ETHUSD"  ──hash──►  1029384756  ──% 8──►  bucket 4

   buckets
   0  │
   1  │
   2  │ ("BTCUSD", 0.5)
   3  │
   4  │ ("ETHUSD", 12.0)
   5  │
   6  │
   7  │

To find a key: hash it, go to that bucket, look. One step, regardless of how many items exist. That's the O(1).

The catch is collisions - two keys landing in the same bucket. Unavoidable: infinite possible keys, finite buckets. The usual fix is to store a small list in each bucket and scan it.

Collisions are cheap when rare and ruinous when common. If every key lands in one bucket, your hash table is a linked list and lookup is O(n).

Build one

The best way to understand it is to write it. Fixed size, chaining, no resizing - enough to see the machinery:

go
package main

import "fmt"

type entry struct {
	key   string
	value float64
}

type SimpleMap struct {
	buckets [][]entry
	size    int
}

func NewSimpleMap(numBuckets int) *SimpleMap {
	return &SimpleMap{buckets: make([][]entry, numBuckets)}
}

// hash is FNV-1a: simple, fast, and well-behaved on short strings.
func hash(key string) uint32 {
	var h uint32 = 2166136261
	for i := 0; i < len(key); i++ {
		h ^= uint32(key[i])
		h *= 16777619
	}
	return h
}

func (m *SimpleMap) bucketFor(key string) int {
	return int(hash(key) % uint32(len(m.buckets)))
}

func (m *SimpleMap) Set(key string, value float64) {
	i := m.bucketFor(key)
	for j, e := range m.buckets[i] {
		if e.key == key {
			m.buckets[i][j].value = value   // overwrite
			return
		}
	}
	m.buckets[i] = append(m.buckets[i], entry{key, value})
	m.size++
}

func (m *SimpleMap) Get(key string) (float64, bool) {
	i := m.bucketFor(key)
	for _, e := range m.buckets[i] {
		if e.key == key {
			return e.value, true
		}
	}
	return 0, false
}

That's a working hash table in fifty lines. Every real one adds resizing, better collision handling, and a great deal of tuning - but the idea is exactly this.

See It Work: count your collisions

Now instrument it, because the interesting part is the distribution:

go
func (m *SimpleMap) Stats() {
	used, longest, total := 0, 0, 0
	for _, b := range m.buckets {
		if len(b) > 0 {
			used++
		}
		if len(b) > longest {
			longest = len(b)
		}
		total += len(b)
	}

	fmt.Printf("items:            %d\n", m.size)
	fmt.Printf("buckets:          %d\n", len(m.buckets))
	fmt.Printf("buckets used:     %d (%.1f%%)\n",
		used, float64(used)/float64(len(m.buckets))*100)
	fmt.Printf("longest chain:    %d\n", longest)
	fmt.Printf("avg chain (used): %.2f\n", float64(total)/float64(used))

	fmt.Println("\nbucket occupancy:")
	for i, b := range m.buckets {
		if i >= 32 {
			fmt.Println("  ...")
			break
		}
		bar := ""
		for j := 0; j < len(b); j++ {
			bar += "█"
		}
		fmt.Printf("  %3d │%s\n", i, bar)
	}
}

Feed it a few hundred symbols and look at the histogram. With a decent hash you'll see chains of one or two and a fairly even spread.

Now break it deliberately:

go
func badHash(key string) uint32 {
	return uint32(len(key))       // hashes on length alone
}

Swap it in and re-run. Every six-character symbol lands in the same bucket. Your histogram grows one enormous bar, the longest chain jumps into the hundreds, and lookups become a linear scan.

You've just demonstrated why hash quality matters, and you've seen the failure rather than been told about it. This is also, incidentally, a real attack: feed a server keys chosen to collide and its hash tables degrade to lists. Go's real map defends against it by randomising its hash seed at startup.

See It Work: map versus scan

go
func BenchmarkMapLookup(b *testing.B) {
	m := make(map[string]float64)
	for i := 0; i < 100000; i++ {
		m[fmt.Sprintf("SYM%06d", i)] = float64(i)
	}
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		_ = m["SYM099999"]
	}
}

func BenchmarkSliceScan(b *testing.B) {
	type kv struct {
		k string
		v float64
	}
	var s []kv
	for i := 0; i < 100000; i++ {
		s = append(s, kv{fmt.Sprintf("SYM%06d", i), float64(i)})
	}
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		for _, e := range s {
			if e.k == "SYM099999" {
				break
			}
		}
	}
}

b.ResetTimer() excludes the setup. Expect a difference of several thousand times. Then re-run both with 1,000 items instead of 100,000: the map barely changes, the scan gets a hundred times faster. The map's flat line as n grows is the entire value proposition.

The gotcha: iteration order is random

go
m := map[string]int{"a": 1, "b": 2, "c": 3}
for k, v := range m {
	fmt.Println(k, v)
}

Run that several times. The order changes every run.

This is deliberate. Go randomises it so you cannot accidentally write code that depends on an order the implementation never promised. It's a kindness that feels like an insult the first time.

When you need order, sort the keys:

go
import "sort"

keys := make([]string, 0, len(m))
for k := range m {
	keys = append(keys, k)
}
sort.Strings(keys)

for _, k := range keys {
	fmt.Println(k, m[k])
}

Maps of slices

Extremely common in trading code:

go
tradesBySymbol := make(map[string][]Trade)
tradesBySymbol["BTCUSD"] = append(tradesBySymbol["BTCUSD"], t)

That works even when the key doesn't exist, because a missing key gives you a nil slice, and appending to a nil slice is legal. One of Go's better small design decisions.

Exercises

9.1 Build map[string]float64 of positions from a slice of trades, netting long and short. Print the result in sorted symbol order.

9.2 Add Delete(key string) to SimpleMap. Careful - removing from the middle of a bucket's slice needs thought.

9.3 Run Stats() with 1,000 symbols across 16, 128 and 1,024 buckets. Tabulate the longest chain in each. What's the relationship between bucket count and chain length?

9.4 Implement badHash and compare the histogram and benchmark against FNV-1a. Quantify how much slower lookups become.

9.5 Add automatic resizing: when average chain length exceeds 2, double the bucket count and rehash everything. Instrument it to print when a resize happens, then confirm chains stay short as you insert 100,000 items.

9.6 Harder. Use a map to deduplicate ticks. Given a slice of (timestamp, price) pairs where some timestamps repeat, keep only the last price for each timestamp and return the result sorted by time. What's the complexity of your solution?

Solutions

9.1

go
positions := make(map[string]float64)
for _, t := range trades {
	positions[t.Symbol] += t.Quantity * float64(t.Side)
}

+= on a missing key works because the zero value is 0.

9.2

go
func (m *SimpleMap) Delete(key string) {
	i := m.bucketFor(key)
	for j, e := range m.buckets[i] {
		if e.key == key {
			m.buckets[i] = append(m.buckets[i][:j], m.buckets[i][j+1:]...)
			m.size--
			return
		}
	}
}

That append(s[:j], s[j+1:]...) idiom removes element j by copying the tail over it.

9.3 Longest chain shrinks roughly in proportion to bucket count until buckets outnumber items. The ratio of items to buckets is called the load factor, and keeping it near 1 is what keeps hash tables fast.

9.4 With badHash on same-length symbols, expect lookups thousands of times slower - you've turned O(1) into O(n).

9.5 Resizes at roughly 32, 64, 128 items and so on. Note that each resize is O(n), but they halve in frequency as the table grows, so the amortised cost stays constant - the same argument as slice growth in Chapter 7.

9.6 O(n) to build the map, O(k log k) to sort the unique timestamps, so O(n + k log k). Better than sorting all n and scanning when duplicates are common.