Data Structures & Algorithms · Module 06 of 10

Hashing

Hash tables, collisions, and load factors — then the map-powered patterns that turn O(n²) into O(n).

Build: Hash map with chaining + resize
Solve: Two Sum, group anagrams, top-k, subarray sums

The finish line — what go test shows once every exercise in this module passes

$ go test -v ./06-hashing/ | grep '^--- ' --- PASS: TestHashMapPutGet (0.00s) --- PASS: TestHashMapResize (0.00s) --- PASS: TestHashMapDelete (0.00s) --- PASS: TestTwoSum (0.00s) --- PASS: TestGroupAnagrams (0.00s) --- PASS: TestTopKFrequent (0.00s) --- PASS: TestLongestConsecutive (0.00s) --- PASS: TestSubarraySumK (0.00s) --- PASS: TestFirstUniqueRune (0.00s)

Module 6 · tests 9

WHY

Why it matters.

A hash table answers "have I seen this key, and what's stored with it?" in O(1) on average. That single ability is behind a huge share of fast algorithms: replace an inner loop that searches with a map lookup, and an O(n²) solution becomes O(n). Caches, symbol tables, database indexes, deduplication, and counting all run on hashing.

IDEAS

The core ideas.

Hash function. Turns a key into a number. A good one spreads keys evenly and is fast. Take it modulo the number of buckets to pick a slot.

Collisions. Different keys can land in the same bucket. Two classic fixes:

Separate chaining — each bucket holds a small list of entries. Simple; what you'll build.
Open addressing — on a collision, probe other slots in the same array. Better cache behavior; trickier deletes.

Load factor is entries ÷ buckets. As it rises, chains get longer and lookups slow down. Past a threshold (0.75 is common), double the bucket count and rehash every entry into its new bucket. Like dynamic-array growth, that's O(n) occasionally and O(1) amortized.

Average vs. worst case. With a decent hash and resizing, operations are O(1) on average. If every key collides, a chain becomes a linked list and lookups are O(n) — which is why production hash tables seed their hash functions randomly, so attackers can't craft colliding keys.

COST

Cost of operations.

Operation	Average	Worst
Insert / lookup / delete	O(1)	O(n)
Resize (rehash)	O(n), amortized away
Iterate all entries	O(n + buckets)

IN GO

Go specifics.

The built-in map is a hash table. Since Go 1.24 it's implemented as a Swiss table (open addressing that probes groups of slots at once). The hash is seeded randomly per map.
Iteration order is deliberately randomized. Never depend on it; sort the keys if you need a stable order.
Keys must be comparable. Strings, numbers, pointers, arrays, and structs of those work. Slices, maps, and functions don't. An array like [26]int makes a great key — e.g., a letter-count signature for anagrams.
Comma-ok. v, ok := m[k] distinguishes "missing" from "present with zero value". A plain m[k] on a missing key returns the zero value, which is handy for counting: m[k]++ just works.
Sets are map[T]struct{} — the empty struct takes no space.
Not safe for concurrent writes. Two goroutines writing a map at once can crash the program (fatal error: concurrent map writes). Guard it with a sync.Mutex, or use sync.Map for the read-heavy cases it's designed for.

EXAMPLE

Worked example: map idioms.

counts := map[string]int{}
for _, w := range strings.Fields("the cat and the hat") {
	counts[w]++ // missing keys start at zero
}

if n, ok := counts["dog"]; !ok {
	fmt.Println("no dogs") // comma-ok tells missing from zero
} else {
	fmt.Println(n)
}

seen := map[int]struct{}{}  // a set
seen[42] = struct{}{}
_, has := seen[42]          // true

// A comparable array as a key: ASCII-lowercase anagram signature.
sig := func(s string) [26]int {
	var c [26]int
	for i := 0; i < len(s); i++ {
		c[s[i]-'a']++
	}
	return c
}
fmt.Println(sig("listen") == sig("silent"), has) // true true

PATTERNS

Patterns to recognize.

Complement lookup — "find two things that combine to X": store what you've seen, look up what you need.
Canonical key — group things that are "the same" (anagrams, shapes) by a normalized signature.
Frequency count — top-k, majority element, first unique.
Prefix sum + map — count subarrays with a given sum, even with negative numbers.
Set membership — dedupe, "longest consecutive run", cycle detection by remembering visited states.

EXERCISES

Your exercises.

Part A builds a separate-chaining HashMap with resizing; the tests insert 1,000 keys and check your load factor stays under 0.75. Part B uses Go's built-in map for six problems.

go test ./06-hashing/

SubarraySumK is the one to slow down on: work out by hand why count += seen[sum-k] counts every subarray ending at the current index.

The files for this module

Everything below is also in the course download, in 06-hashing/. Work in exercises.go; the tests decide when you’re done.

▶ types.go the structs and helpers you’re given · 41 lines›

// Package hashing is Module 6: hash tables.
//
// Go's built-in map is a hash table, and you'll use it for every problem in
// Part B. Part A has you build one yourself so the map stops being magic.
package hashing

import "hash/fnv"

type entry struct {
	key string
	val int
}

// HashMap maps strings to ints using separate chaining: each bucket is a
// slice of entries whose keys hash to that bucket.
//
// Keep the load factor (size / len(buckets)) at or below MaxLoad by doubling
// the bucket count and re-inserting every entry when it would be exceeded.
type HashMap struct {
	buckets [][]entry
	size    int
}

// MaxLoad is the highest allowed size/len(buckets) ratio.
const MaxLoad = 0.75

// NewHashMap returns an empty map with 8 buckets.
func NewHashMap() *HashMap {
	return &HashMap{buckets: make([][]entry, 8)}
}

// Len returns the number of keys stored.
func (m *HashMap) Len() int { return m.size }

// hashKey is the hash function: FNV-1a, 64-bit. Use hashKey(k) % len(buckets)
// to pick a bucket.
func hashKey(key string) uint64 {
	h := fnv.New64a()
	h.Write([]byte(key))
	return h.Sum64()
}

exercises.go — your work: every function is a stub marked TODO85 lines

//go:build !solutions

package hashing

// ============================================================
// Part A — build a hash map (see types.go)
// ============================================================

// Put sets key to val, overwriting an existing value. Before inserting a
// NEW key, if (size+1)/len(buckets) would exceed MaxLoad, double the bucket
// count and rehash every entry into the new buckets.
// Target: amortized O(1).
func (m *HashMap) Put(key string, val int) {
	// TODO
}

// Get returns the value for key, or (0, false). Target: O(1) average.
func (m *HashMap) Get(key string) (int, bool) {
	// TODO
	return 0, false
}

// Delete removes key and reports whether it was present.
// Target: O(1) average.
func (m *HashMap) Delete(key string) bool {
	// TODO
	return false
}

// ============================================================
// Part B — hashing problems (use Go's built-in map)
// ============================================================

// TwoSum returns indices i < j with nums[i]+nums[j] == target, or
// (0, 0, false). Unlike Module 1, nums is NOT sorted.
// Pattern: one pass, map from value to index of "complements" seen so far.
// Target: O(n).
func TwoSum(nums []int, target int) (int, int, bool) {
	// TODO
	return 0, 0, false
}

// GroupAnagrams groups words that are anagrams of each other. Groups appear
// in order of their first word's position in the input, and words keep their
// input order within a group.
// ["eat" "tea" "tan" "ate" "nat" "bat"] -> [[eat tea ate] [tan nat] [bat]].
// Pattern: map from a canonical signature (sorted runes) to group.
func GroupAnagrams(words []string) [][]string {
	// TODO
	return nil
}

// TopKFrequent returns the k most frequent values, most frequent first,
// breaking ties by smaller value first. [1 1 1 2 2 3], k=2 -> [1 2].
// Pattern: count with a map, then bucket by frequency. Target: O(n) plus
// sorting within buckets.
func TopKFrequent(nums []int, k int) []int {
	// TODO
	return nil
}

// LongestConsecutive returns the length of the longest run of consecutive
// integers present in nums, in any order. [100 4 200 1 3 2] -> 4 (1,2,3,4).
// Pattern: set lookup; only start counting at v when v-1 is absent.
// Target: O(n) — no sorting.
func LongestConsecutive(nums []int) int {
	// TODO
	return 0
}

// SubarraySumK counts contiguous subarrays summing to k. Values may be
// negative. [1 1 1], k=2 -> 2.
// Pattern: running prefix sum + map of how often each prefix sum occurred.
// Target: O(n).
func SubarraySumK(nums []int, k int) int {
	// TODO
	return 0
}

// FirstUniqueRune returns the first rune that appears exactly once, or
// (0, false). "loveleetcode" -> 'v'. Target: O(n), two passes.
func FirstUniqueRune(s string) (rune, bool) {
	// TODO
	return 0, false
}

▶ hashing_test.go the tests — the same file checks yours or the reference · 172 lines›

package hashing

import (
	"fmt"
	"slices"
	"testing"
)

func TestHashMapPutGet(t *testing.T) {
	m := NewHashMap()
	m.Put("a", 1)
	m.Put("b", 2)
	m.Put("a", 10) // overwrite
	if m.Len() != 2 {
		t.Fatalf("Len() = %d, want 2 (overwriting must not add a key)", m.Len())
	}
	if v, ok := m.Get("a"); !ok || v != 10 {
		t.Errorf("Get(a) = (%d, %v), want (10, true)", v, ok)
	}
	if v, ok := m.Get("b"); !ok || v != 2 {
		t.Errorf("Get(b) = (%d, %v), want (2, true)", v, ok)
	}
	if _, ok := m.Get("zzz"); ok {
		t.Error("Get(missing) should return ok=false")
	}
}

func TestHashMapResize(t *testing.T) {
	m := NewHashMap()
	const n = 1000
	for i := 0; i < n; i++ {
		m.Put(fmt.Sprintf("key-%d", i), i)
	}
	if m.Len() != n {
		t.Fatalf("Len() = %d, want %d", m.Len(), n)
	}
	if load := float64(m.size) / float64(len(m.buckets)); load > MaxLoad {
		t.Errorf("load factor %.2f exceeds MaxLoad %.2f — did you resize?", load, MaxLoad)
	}
	for i := 0; i < n; i++ {
		k := fmt.Sprintf("key-%d", i)
		if v, ok := m.Get(k); !ok || v != i {
			t.Fatalf("Get(%s) = (%d, %v) after resizing, want (%d, true)", k, v, ok, i)
		}
	}
}

func TestHashMapDelete(t *testing.T) {
	m := NewHashMap()
	for i := 0; i < 50; i++ {
		m.Put(fmt.Sprint(i), i)
	}
	for i := 0; i < 50; i += 2 {
		if !m.Delete(fmt.Sprint(i)) {
			t.Fatalf("Delete(%d) = false, want true", i)
		}
	}
	if m.Delete("0") {
		t.Error("deleting an already-deleted key should return false")
	}
	if m.Len() != 25 {
		t.Fatalf("Len() = %d, want 25", m.Len())
	}
	for i := 0; i < 50; i++ {
		_, ok := m.Get(fmt.Sprint(i))
		if want := i%2 == 1; ok != want {
			t.Fatalf("Get(%d) ok = %v, want %v", i, ok, want)
		}
	}
}

func TestTwoSum(t *testing.T) {
	for _, tc := range []struct {
		nums   []int
		target int
		ok     bool
	}{
		{[]int{2, 7, 11, 15}, 9, true},
		{[]int{3, 2, 4}, 6, true},
		{[]int{3, 3}, 6, true},
		{[]int{-1, 8, 4}, 3, true},
		{[]int{1, 2, 3}, 7, false},
	} {
		i, j, ok := TwoSum(tc.nums, tc.target)
		if ok != tc.ok {
			t.Errorf("TwoSum(%v, %d) ok = %v, want %v", tc.nums, tc.target, ok, tc.ok)
			continue
		}
		if ok && (i >= j || tc.nums[i]+tc.nums[j] != tc.target) {
			t.Errorf("TwoSum(%v, %d) = (%d, %d): not a valid pair", tc.nums, tc.target, i, j)
		}
	}
}

func TestGroupAnagrams(t *testing.T) {
	got := GroupAnagrams([]string{"eat", "tea", "tan", "ate", "nat", "bat"})
	want := [][]string{{"eat", "tea", "ate"}, {"tan", "nat"}, {"bat"}}
	if !slices.EqualFunc(got, want, slices.Equal[[]string]) {
		t.Errorf("GroupAnagrams = %v, want %v", got, want)
	}
	if got := GroupAnagrams([]string{""}); !slices.EqualFunc(got, [][]string{{""}}, slices.Equal[[]string]) {
		t.Errorf("GroupAnagrams([\"\"]) = %v, want [[]]", got)
	}
}

func TestTopKFrequent(t *testing.T) {
	for _, tc := range []struct {
		nums []int
		k    int
		want []int
	}{
		{[]int{1, 1, 1, 2, 2, 3}, 2, []int{1, 2}},
		{[]int{4, 4, 5, 5, 6}, 2, []int{4, 5}},
		{[]int{7}, 1, []int{7}},
		{[]int{3, 1, 2, 2, 3, 1}, 3, []int{1, 2, 3}},
	} {
		if got := TopKFrequent(tc.nums, tc.k); !slices.Equal(got, tc.want) {
			t.Errorf("TopKFrequent(%v, %d) = %v, want %v", tc.nums, tc.k, got, tc.want)
		}
	}
}

func TestLongestConsecutive(t *testing.T) {
	for _, tc := range []struct {
		in   []int
		want int
	}{
		{[]int{100, 4, 200, 1, 3, 2}, 4},
		{[]int{0, 3, 7, 2, 5, 8, 4, 6, 0, 1}, 9},
		{[]int{1, 2, 0, 1}, 3},
		{[]int{}, 0},
		{[]int{-2, -3, -1}, 3},
	} {
		if got := LongestConsecutive(tc.in); got != tc.want {
			t.Errorf("LongestConsecutive(%v) = %d, want %d", tc.in, got, tc.want)
		}
	}
}

func TestSubarraySumK(t *testing.T) {
	for _, tc := range []struct {
		in      []int
		k, want int
	}{
		{[]int{1, 1, 1}, 2, 2},
		{[]int{1, 2, 3}, 3, 2},
		{[]int{1, -1, 0}, 0, 3},
		{[]int{3, 4, 7, 2, -3, 1, 4, 2}, 7, 4},
	} {
		if got := SubarraySumK(tc.in, tc.k); got != tc.want {
			t.Errorf("SubarraySumK(%v, %d) = %d, want %d", tc.in, tc.k, got, tc.want)
		}
	}
}

func TestFirstUniqueRune(t *testing.T) {
	for _, tc := range []struct {
		in   string
		want rune
		ok   bool
	}{
		{"loveleetcode", 'v', true},
		{"leetcode", 'l', true},
		{"aabb", 0, false},
		{"ééx", 'x', true},
	} {
		got, ok := FirstUniqueRune(tc.in)
		if got != tc.want || ok != tc.ok {
			t.Errorf("FirstUniqueRune(%q) = (%q, %v), want (%q, %v)", tc.in, got, ok, tc.want, tc.ok)
		}
	}
}

Before you open the solution

Try not to open solution.go until your tests pass, or until you’ve been stuck for a solid half hour. Then compare: different-but-correct is fine; notice where the reference is simpler. go test -tags solutions ./06-hashing/ runs the same tests against it.

▶ solution.go reference solutions — build tag solutions · 160 lines›

//go:build solutions

package hashing

import (
	"slices"
	"sort"
)

func (m *HashMap) bucketFor(key string) int {
	return int(hashKey(key) % uint64(len(m.buckets)))
}

func (m *HashMap) resize() {
	old := m.buckets
	m.buckets = make([][]entry, len(old)*2)
	for _, b := range old {
		for _, e := range b {
			i := m.bucketFor(e.key)
			m.buckets[i] = append(m.buckets[i], e)
		}
	}
}

func (m *HashMap) Put(key string, val int) {
	i := m.bucketFor(key)
	for j := range m.buckets[i] {
		if m.buckets[i][j].key == key {
			m.buckets[i][j].val = val
			return
		}
	}
	if float64(m.size+1)/float64(len(m.buckets)) > MaxLoad {
		m.resize()
		i = m.bucketFor(key)
	}
	m.buckets[i] = append(m.buckets[i], entry{key, val})
	m.size++
}

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

func (m *HashMap) Delete(key string) bool {
	i := m.bucketFor(key)
	b := m.buckets[i]
	for j, e := range b {
		if e.key == key {
			// Order inside a bucket doesn't matter: swap with last and shrink.
			b[j] = b[len(b)-1]
			m.buckets[i] = b[:len(b)-1]
			m.size--
			return true
		}
	}
	return false
}

func TwoSum(nums []int, target int) (int, int, bool) {
	seen := make(map[int]int) // value -> index
	for j, v := range nums {
		if i, ok := seen[target-v]; ok {
			return i, j, true
		}
		seen[v] = j
	}
	return 0, 0, false
}

func GroupAnagrams(words []string) [][]string {
	index := make(map[string]int) // signature -> position in out
	var out [][]string
	for _, w := range words {
		r := []rune(w)
		slices.Sort(r)
		sig := string(r)
		if i, ok := index[sig]; ok {
			out[i] = append(out[i], w)
		} else {
			index[sig] = len(out)
			out = append(out, []string{w})
		}
	}
	return out
}

func TopKFrequent(nums []int, k int) []int {
	freq := make(map[int]int)
	for _, v := range nums {
		freq[v]++
	}
	// Bucket sort by frequency: buckets[f] holds values seen f times.
	buckets := make([][]int, len(nums)+1)
	for v, f := range freq {
		buckets[f] = append(buckets[f], v)
	}
	var out []int
	for f := len(buckets) - 1; f > 0 && len(out) < k; f-- {
		sort.Ints(buckets[f]) // deterministic tie-break: smaller value first
		for _, v := range buckets[f] {
			if len(out) == k {
				break
			}
			out = append(out, v)
		}
	}
	return out
}

func LongestConsecutive(nums []int) int {
	set := make(map[int]struct{}, len(nums))
	for _, v := range nums {
		set[v] = struct{}{}
	}
	best := 0
	for v := range set {
		if _, hasPrev := set[v-1]; hasPrev {
			continue // not the start of a run
		}
		n := 1
		for {
			if _, ok := set[v+n]; !ok {
				break
			}
			n++
		}
		best = max(best, n)
	}
	return best
}

func SubarraySumK(nums []int, k int) int {
	count, sum := 0, 0
	seen := map[int]int{0: 1} // prefix sum -> times seen
	for _, v := range nums {
		sum += v
		count += seen[sum-k]
		seen[sum]++
	}
	return count
}

func FirstUniqueRune(s string) (rune, bool) {
	counts := make(map[rune]int)
	for _, r := range s {
		counts[r]++
	}
	for _, r := range s {
		if counts[r] == 1 {
			return r, true
		}
	}
	return 0, false
}

FURTHER

Going further.

Rewrite your HashMap with open addressing (linear probing). Deletion needs "tombstones" — find out why.
LeetCode practice: Valid Sudoku, Contiguous Array, LRU Cache.

QUIZ

Check yourself.

Four questions. Answer each one in your head — or out loud — before you open the answer.

Question 1

Which of these can be a Go map key?

A[]int
B[3]int
Cmap[string]int
Dfunc()

Show the answer

B — Keys must be comparable. Arrays are (element-wise); slices, maps, and functions are not. A [26]int letter count makes a good anagram key.

Question 2

Your HashMap starts with 8 buckets and resizes when (size+1)/buckets would exceed 0.75. Inserting which key triggers the first resize?

AThe 6th
BThe 7th
CThe 8th
DThe 9th

Show the answer

B — Before the 7th insert, (6+1)/8 = 0.875 > 0.75. Before the 6th it was 6/8 = 0.75, which doesn't exceed the limit.

Question 3

Why does Go randomize map iteration order?

AIt's faster
BSo programs can't accidentally depend on an order the language doesn't promise
CFor security against timing attacks
DBecause Swiss tables require it

Show the answer

B — Implementation details change between releases (they did in Go 1.24). Randomizing surfaces order-dependent bugs early. Sort the keys if you need order.

Question 4

Two Sum on an unsorted slice: brute force is O(n²). With a map it's…

AO(n log n)
BO(n)
CO(1)
DStill O(n²)

Show the answer

B — One pass: for each value, look up target − value among the values already seen, then record the current one.

Where to next.

Commit your work before you move on to module 7, so git log shows your own progress through the course.

Hashing

Why it matters.

The core ideas.

Cost of operations.

Go specifics.

Worked example: map idioms.

Patterns to recognize.

Your exercises.

The files for this module

Going further.

Check yourself.

Where to next.

← Previous: Module 5 — Queues

Next →: Module 7 — Trees

Course home