Hash Tables

The Core Idea

An array gives O(1) access by integer index. A hash table extends this to any key by converting the key into an index: compute a number from the key (the hash), then reduce it to the range of an array of buckets.

Hash Functions

A hash function maps a key to a fixed-size integer. A good one is deterministic (the same key always gives the same hash), fast, and well distributed (similar keys give very different hashes, so keys spread evenly over the buckets). FNV-1a, used in the demos, mixes in one byte at a time with an XOR and spreads it across all 64 bits with a multiplication:

// fnv1a is the 64-bit FNV-1a hash (also available as hash/fnv).
func fnv1a(s string) uint64 {
	h := uint64(14695981039346656037) // offset basis
	for i := 0; i < len(s); i++ {
		h ^= uint64(s[i])  // mix in one byte
		h *= 1099511628211 // FNV prime: spread it over all bits
	}
	return h
}

// bucket index for a table of n buckets, n a power of two:
// h & (n-1) equals h % n without a division.
idx := int(fnv1a(key) & uint64(n-1))

FNV is not designed to resist attackers. If users can choose keys, they can pick keys that all collide and degrade every lookup to O(n). Go's built-in map defends against this by seeding its hash function randomly for each map.

Collisions

There are more possible keys than buckets, so different keys inevitably map to the same bucket — a collision. Collisions are normal, not an error. A hash table is defined by how it resolves them: separate chaining keeps a list per bucket; open addressing looks for another free slot in the same array.

Load Factor and Resizing

The load factor is entries ÷ buckets. As it rises, chains grow longer (chaining) or probe sequences grow longer (open addressing), and lookups slow down. Tables therefore resize — typically doubling the bucket array — when the load factor passes a threshold. Every entry must be rehashed into the new array, because its bucket depends on the array size. A resize costs O(n), but it happens only after about n inserts, so inserts remain O(1) amortized — the same argument as for slice append.

Separate Chaining

With separate chaining, each bucket holds a small collection of the entries that hashed to it. A lookup hashes the key, goes to one bucket, and scans only that bucket's chain.

Five keys in eight buckets. Two collisions produce chains of length two; a lookup for cherry hashes to bucket 3 and compares against at most two keys.

Implementation

Each bucket is a slice of entries. Put updates the key if it is already in the chain, otherwise appends it and resizes when the load factor exceeds 0.75. Get scans one chain and reports presence with the "comma ok" convention of Go maps.

type entry[V any] struct {
	key string
	val V
}

type HashMap[V any] struct {
	buckets [][]entry[V] // len(buckets) is a power of two
	count   int
}

func (m *HashMap[V]) Put(key string, val V) {
	b := int(fnv1a(key) & uint64(len(m.buckets)-1))
	for i := range m.buckets[b] {
		if m.buckets[b][i].key == key {
			m.buckets[b][i].val = val // existing key: update in place
			return
		}
	}
	m.buckets[b] = append(m.buckets[b], entry[V]{key, val})
	m.count++
	if float64(m.count)/float64(len(m.buckets)) > 0.75 {
		m.resize() // double the buckets and rehash every entry
	}
}

func (m *HashMap[V]) Get(key string) (V, bool) {
	b := int(fnv1a(key) & uint64(len(m.buckets)-1))
	for _, e := range m.buckets[b] {
		if e.key == key {
			return e.val, true
		}
	}
	var zero V
	return zero, false
}

What a Bad Hash Does

The whole O(1) guarantee rests on the hash function. The demo inserts 100,000 keys and reports the longest chain: with FNV-1a it is a handful of entries; with a "hash" that returns only the key's length, every key has the same length and all 100,000 land in one chain — each lookup becomes a linear scan. Full table with resizing, deletion, and statistics: 21_hash_table_chaining.go.

Open Addressing

Open addressing stores all entries directly in one flat array, with no per-bucket lists. It avoids an allocation per entry and reads neighboring memory on collisions, which suits CPU caches. Most high-performance hash tables, including Go's current map, use it.

Linear Probing

On a collision, try the next slot, then the next, wrapping at the end of the array, until the key or an empty slot is found. An empty slot ends the search: the key would have been placed there. Because runs of occupied slots grow quickly as the table fills, open-addressing tables keep a lower load factor than chaining tables — the demo resizes at 0.5.

Deletion with Tombstones

Deletion is the subtle part. Simply emptying a slot would cut the probe sequence of every key stored after it: a later lookup would stop at the new empty slot and wrongly report "absent". Instead, a deleted slot becomes a tombstone. Lookups skip over tombstones, inserts may reuse them, and a rehash removes them all.

const (
	empty     slotState = iota // never used: ends a probe sequence
	full                       // holds a live key
	tombstone                  // deleted: probing continues past it
)

func (s *HashSet) Remove(key string) bool {
	i, found := s.find(key)
	if !found {
		return false
	}
	s.slots[i] = slot{state: tombstone} // NOT empty: keeps chains intact
	s.live--
	s.dead++
	return true
}

The demo deletes a key in the middle of a probe chain and verifies that every other key is still found, then runs 50,000 inserts and 25,000 deletes and measures the average probes per lookup: 22_open_addressing.go.

How Go Maps Work

Since Go 1.24 the built-in map is based on Swiss tables, an open-addressing design. Slots are arranged in groups of eight, and each group has a control word holding a few bits of each slot's hash. A lookup compares the key's hash bits against all eight control bytes at once and examines only the slots that match, so most probes touch a single group. Large maps are split into several tables that grow independently, which keeps the cost of any single resize bounded. The rules for using maps did not change: keys must be comparable, iteration order is unspecified, and maps are not safe for concurrent writes.

Hashing Patterns

Once you can ask "have I seen this?" or "how many times?" in O(1), many problems that seem to need nested loops become single passes. Recognizing the pattern is the skill. All of these, with examples: 23_hashing_patterns.go.

Counting

map[K]int answers frequency questions: word counts, majority elements, anagram checks. Two strings are anagrams if every character count matches — count up for one string and down for the other; every count must end at zero. When keys are bytes, a [256]int array is a faster "map" with no hashing at all.

Seen Sets

map[K]struct{} is Go's set type; the empty struct occupies no memory. It answers "is this a duplicate?", "what is the first repeat?", and "which values are in both inputs?" — build the set from one input and probe it with the other, in O(n + m) instead of O(n · m).

Grouping by Canonical Key

To group items that are "equivalent", compute a canonical key that is identical for every member of a group and use it as the map key. For anagrams, the letter-count array [26]byte works: arrays are comparable in Go, so they can be map keys directly — slices cannot.

func groupAnagrams(words []string) map[[26]byte][]string {
	groups := map[[26]byte][]string{}
	for _, w := range words {
		var key [26]byte // letter counts: equal for all anagrams
		for _, c := range w {
			key[c-'a']++ // assumes lowercase ASCII input
		}
		groups[key] = append(groups[key], w)
	}
	return groups
}

Membership Tricks

The longest run of consecutive integers in an unsorted slice seems to require sorting. With a set, start counting only at numbers whose predecessor is absent — the start of a run — and extend while the next number is present. Each number is visited at most twice, so the algorithm is O(n) rather than O(n log n).

Common Pitfalls

Go maps are easy to use; most bugs come from their few firm rules.

Concurrent Writes

A map written by one goroutine while another reads or writes it can crash the program with fatal error: concurrent map writes — a fatal error, not a recoverable panic. Protect shared maps with a sync.Mutex or sync.RWMutex, or use sync.Map for its specific read-mostly use cases. The race detector (go run -race) finds these bugs in testing.

Updating Struct Values in a Map

m[k].Count++ does not compile when the map holds struct values ("cannot assign to struct field m[k].Count in map"): map elements are not addressable, because the map may move them during growth. Read the value, modify it, and store it back — or store pointers, map[K]*T.

Floating-Point Keys

NaN != NaN, so every insertion with a NaN key creates a new entry that can never be looked up. Rounding errors also make 0.1 + 0.2 a different key from 0.3. Avoid float keys; round to an integer unit (cents, milliseconds) first.

Practice Lab

Before each exercise, name the pattern: count, seen set, index, group, or membership.

Run the Demos

1. In 21_hash_table_chaining.go, raise maxLoad to 4.0 and then 16.0. How do the longest chain and the number of resizes change?
2. In 22_open_addressing.go, make Remove set the slot to empty instead of tombstone. The dense-table check now reports lost keys — trace one of them through its probe sequence.

Exercises

1. Isomorphic strings. Decide whether characters of s can be replaced to get t, with a consistent one-to-one mapping (egg/add yes, foo/bar no). You will need two maps.
2. Longest subarray with sum k. Combine prefix sums with a map from prefix value to its first index.
3. Generic chaining map. Make HashMap generic in its key type with a hash func(K) uint64 parameter, and test it with struct keys.
4. Count distinct in windows. For every window of size k, report the number of distinct values in O(n) total, using a count map that grows and shrinks with the window.

Next lesson: Binary Trees & BST.