Chapter 5 — Hash Tables

A hash table maps keys to values with expected O(1) lookup, insert, and delete. The trick: a hash function turns a key into an integer, which is reduced (modulo the bucket count) into an index, and an entry is stored at that bucket.

The two big design decisions are:

1. Hash function — must distribute keys uniformly over [0, m).
2. Collision resolution — what to do when two keys land in the same bucket. Two main approaches: - Separate chaining — each bucket stores a linked list (or another small structure) of entries. - Open addressing — collisions probe to other buckets (linear / quadratic / double hashing). Used by Go's built-in map.

The built-in map

m := map[string]int{}
m["a"] = 1
v, ok := m["x"]
delete(m, "a")
for k, v := range m { ... }   // iteration order is RANDOMIZED

Properties of Go's map:

• Implemented with open addressing using buckets of 8 entries each.
• Iteration order is intentionally randomized to discourage code that depends on it.
• Reading a non-existent key returns the zero value (and ok=false with the comma-ok form).
• nil map can be read but panics on write; always create with {} or make.
• Not safe for concurrent writes; use sync.Mutex or sync.Map.

You should use map for all real work. The hashmap package in this chapter is a from-scratch separate-chaining implementation that is only for learning what the built-in does under the hood.

What we implement

hashmap.HashMap[K comparable, V any] with:

• Separate chaining (singly linked lists per bucket).
• A simple FNV-1a-like hash for string keys; for arbitrary comparable keys we fall back to fmt.Sprint and hash that — slow, but correct and educational.
• Automatic resize: when the load factor (n / buckets) exceeds 0.75 we double the bucket count and rehash.

Complexity

Run the tests

go test ./part2-dsa/ds/hashmap