Go Guide

Core patterns · Lesson 16 of 62 · about 45 min

Hashing

Turn 'have I seen the thing that completes this one?' into an O(1) lookup, and learn how to choose the right key.

Go by Example: Maps ↗Go maps in action ↗
On this page · 10 sections
  1. 01How a hash map works (enough to reason about it)
  2. 02Pattern 1: complement lookup (Two Sum)
  3. 03Pattern 2: a signature key (Group Anagrams)
  4. 04Pattern 3: a set for existence (Longest Consecutive Sequence)
  5. 05Pattern 4: counting
  6. 06The full program
  7. 07Complexity
  8. 08Summary
  9. 09Check your understanding
  10. 10Practice in Go

How a hash map works (enough to reason about it)#

A map keeps an array of buckets. To store a key, it runs a hash function that turns the key into a number, uses that number to pick a bucket, and puts the pair there. Looking up the key repeats the same calculation, so it goes straight to the right bucket instead of scanning everything. When the map gets too full, it allocates more buckets and moves entries over (like append growing a slice), which keeps lookups fast on average.

Consequences you should remember:

  • Lookups, inserts and deletes are O(1) on average.
  • Keys must be comparable (==), so slices cannot be keys but arrays and structs can.
  • Iteration order is random.
  • Memory is O(n) for n entries.

Map basics in Go

Every pattern below uses the same handful of operations. Note the comma-ok form: a missing key returns the zero value, so ok is the only way to tell "absent" from "stored 0".

mapbasics.go
Go
package main
 
import "fmt"
 
type point struct{ x, y int }
 
func main() {
	ages := map[string]int{"ana": 31, "bo": 25}
	ages["cy"] = 40        // insert
	ages["bo"]++           // update in place
	delete(ages, "ana")    // delete
	age, ok := ages["ana"] // missing key: zero value and ok == false
	fmt.Println(len(ages), age, ok, ages["bo"])
 
	// Structs and arrays are comparable, so they can be keys. Slices cannot.
	visited := map[point]bool{{0, 0}: true}
	visited[point{1, 2}] = true
	fmt.Println(visited[point{1, 2}], visited[point{2, 1}])
 
	byLetters := map[[3]byte]string{{'c', 'a', 't'}: "cat"}
	fmt.Println(byLetters[[3]byte{'c', 'a', 't'}])
}
Output
2 0 false 26
true false
cat

See it: collisions and probing

Since Go 1.24, Go's map is a Swiss table: slots come in groups of 8, each with a small control byte holding a few bits of the hash, so one comparison can check a whole group. The core idea is the same as below: hash to a slot, and handle collisions by probing. Insert keys that share a remainder, such as 12, 22 and 32, to see a cluster form.

Pattern 1: complement lookup (Two Sum)#

"Find two indexes whose values add to target." For each number n, the partner we need is target - n. Instead of scanning for it, we remember every number seen so far with its index.

Trace nums = [2, 7, 11, 15], target = 18:

inneed target - nin map?map after
0216no{2:0}
1711no{2:0, 7:1}
2117yes, index 1return [1, 2]

We check before inserting, so n can never pair with itself.

Run the trace

This prints the table above, including the map's contents at each step. (fmt prints maps with sorted keys, so the output is stable even though map iteration is not.)

twosum_trace.go
Go
package main
 
import "fmt"
 
func main() {
	nums, target := []int{2, 7, 11, 15}, 18
	idx := map[int]int{} // value -> index where we saw it
	for i, n := range nums {
		need := target - n
		j, ok := idx[need] // check before inserting n
		fmt.Printf("i=%d n=%-2d need=%-2d found=%-5v map=%v\n", i, n, need, ok, idx)
		if ok {
			fmt.Println("answer:", []int{j, i})
			return
		}
		idx[n] = i
	}
}
Output
i=0 n=2  need=16 found=false map=map[]
i=1 n=7  need=11 found=false map=map[2:0]
i=2 n=11 need=7  found=true  map=map[2:0 7:1]
answer: [1 2]

Pattern 2: a signature key (Group Anagrams)#

Anagrams have the same letters in different orders. Give every word a signature that is identical for all anagrams, and group by it. Two choices:

SignatureCost per word of length kNotes
sorted letters, "aet"O(k log k) plus a new stringworks for any characters
letter counts, [26]byteO(k), no allocationlowercase a–z only; arrays are valid map keys in Go

For eat, tea and ate, the count array has a 1 at positions a, e and t, so all three land in the same group.

See the signatures

Print the counts for a few words. Anagrams produce equal arrays, and == compares arrays element by element, which is exactly why they work as map keys:

signature.go
Go
package main
 
import "fmt"
 
func signature(w string) [26]byte {
	var key [26]byte
	for i := 0; i < len(w); i++ {
		key[w[i]-'a']++
	}
	return key
}
 
func main() {
	for _, w := range []string{"eat", "tea", "ate", "tan"} {
		s := signature(w)
		fmt.Printf("%-4s a=%d e=%d n=%d t=%d\n", w, s['a'-'a'], s['e'-'a'], s['n'-'a'], s['t'-'a'])
	}
	fmt.Println(signature("eat") == signature("ate"), signature("eat") == signature("tan"))
}
Output
eat  a=1 e=1 n=0 t=1
tea  a=1 e=1 n=0 t=1
ate  a=1 e=1 n=0 t=1
tan  a=1 e=0 n=1 t=1
true false

Pattern 3: a set for existence (Longest Consecutive Sequence)#

"Find the length of the longest run of consecutive integers, in O(n)." Put every number in a set. A number starts a run only if n-1 is not in the set; from each start, count upward.

For [100, 4, 200, 1, 3, 2]: starts are 100, 200 and 1 (because 99, 199 and 0 are absent). From 1 we find 2, 3, 4: length 4. Each number is visited at most twice overall, so the total is O(n).

Pattern 4: counting#

count[x]++ builds a frequency table in one pass. Then answer questions like "first unique character", "most frequent element" or "are these two strings anagrams". For small fixed alphabets, an array counter is faster than a map.

Counting in practice

Three small counting problems. The first two use a [26]int array as the counter because the alphabet is fixed; the third counts arbitrary strings, so it needs a map:

counting.go
Go
package main
 
import "fmt"
 
// firstUnique returns the index of the first letter that appears once, or -1.
func firstUnique(s string) int {
	var count [26]int
	for i := 0; i < len(s); i++ {
		count[s[i]-'a']++
	}
	for i := 0; i < len(s); i++ { // second pass, in original order
		if count[s[i]-'a'] == 1 {
			return i
		}
	}
	return -1
}
 
// isAnagram adds a's letters and subtracts b's; anagrams cancel out to all zeros.
func isAnagram(a, b string) bool {
	if len(a) != len(b) {
		return false
	}
	var count [26]int
	for i := 0; i < len(a); i++ {
		count[a[i]-'a']++
		count[b[i]-'a']--
	}
	return count == [26]int{}
}
 
func mostFrequent(words []string) (string, int) {
	count := map[string]int{}
	best, bestN := "", 0
	for _, w := range words {
		count[w]++
		if count[w] > bestN {
			best, bestN = w, count[w]
		}
	}
	return best, bestN
}
 
func main() {
	fmt.Println(firstUnique("leetcode"), firstUnique("loveleetcode"), firstUnique("aabb"))
	fmt.Println(isAnagram("listen", "silent"), isAnagram("rat", "car"))
	fmt.Println(mostFrequent([]string{"go", "is", "fun", "go", "go", "fun"}))
}
Output
0 2 -1
true false
go 3

The full program#

hashing.go
Go
package main
 
import (
	"fmt"
	"slices"
)
 
func twoSum(nums []int, target int) []int {
	idx := make(map[int]int, len(nums))
	for i, n := range nums {
		if j, ok := idx[target-n]; ok {
			return []int{j, i}
		}
		idx[n] = i
	}
	return nil
}
 
func groupAnagrams(words []string) [][]string {
	groups := map[[26]byte][]string{}
	var order [][26]byte // remember first-seen order for stable output
	for _, w := range words {
		var key [26]byte
		for i := 0; i < len(w); i++ {
			key[w[i]-'a']++
		}
		if _, ok := groups[key]; !ok {
			order = append(order, key)
		}
		groups[key] = append(groups[key], w)
	}
	out := make([][]string, 0, len(groups))
	for _, k := range order {
		out = append(out, groups[k])
	}
	return out
}
 
func longestConsecutive(nums []int) int {
	set := make(map[int]struct{}, len(nums))
	for _, n := range nums {
		set[n] = struct{}{}
	}
	best := 0
	for n := range set {
		if _, hasPrev := set[n-1]; hasPrev {
			continue // not the start of a run
		}
		length := 1
		for {
			if _, ok := set[n+length]; !ok {
				break
			}
			length++
		}
		best = max(best, length)
	}
	return best
}
 
func topKFrequent(nums []int, k int) []int {
	count := map[int]int{}
	for _, n := range nums {
		count[n]++
	}
	buckets := make([][]int, len(nums)+1) // buckets[f] = numbers appearing f times
	for n, f := range count {
		buckets[f] = append(buckets[f], n)
	}
	var out []int
	for f := len(buckets) - 1; f > 0 && len(out) < k; f-- {
		slices.Sort(buckets[f]) // deterministic order for ties
		out = append(out, buckets[f]...)
	}
	return out[:k]
}
 
func main() {
	fmt.Println(twoSum([]int{2, 7, 11, 15}, 18), twoSum([]int{3, 3}, 6), twoSum([]int{1}, 5))
	fmt.Println(groupAnagrams([]string{"eat", "tea", "tan", "ate", "nat", "bat"}))
	fmt.Println(longestConsecutive([]int{100, 4, 200, 1, 3, 2}))
	fmt.Println(topKFrequent([]int{1, 1, 1, 2, 2, 3}, 2))
}
Output
[1 2] [0 1] []
[[eat tea ate] [tan nat] [bat]]
4
[1 2]

Complexity#

ProblemTimeSpace
Two SumO(n)O(n)
Group AnagramsO(total letters)O(total letters)
Longest Consecutive SequenceO(n)O(n)
Top K Frequent (bucket sort)O(n)O(n)

Summary#

  • A hash map gives O(1) average lookup by hashing keys into buckets.
  • Complement lookup: store what you have seen, ask for what you need.
  • Signature keys group equivalent items; [26]byte is a fast, comparable key.
  • A set plus "only start at the beginning of a run" keeps sequence problems O(n).
  • Sort or track order whenever output depends on map iteration.

Check your understanding

Answer before scrolling back up. If you miss one, reread the matching section, then try again.

  1. Q1.In Two Sum, why check the map for target - n before storing n?

  2. Q2.Why can [26]byte be a map key but []byte cannot?

  3. Q3.What is the average time of a map lookup?

  4. Q4.In Longest Consecutive Sequence, why only start counting from numbers where n-1 is not in the set?

Practice in Go

Write a table test first, then the solution. On LeetCode, choose Go as the language. Open a hint only after 15 minutes stuck.

Finished this lesson?

Mark it done to track your progress. It is saved in this browser only.