A hash map stores key-value pairs and provides O(1)
average-time lookups, inserts, and deletes. In Go, the
built-in map type is a hash map.
Use when: you need to quickly check if a value exists, find a complement, or associate data with a key.
A common pattern is the complement lookup: given a collection and a target, find two elements that combine to produce the target. Instead of checking every pair (O(n²)), store seen values in a map and check for the complement in O(1).
Map from value to its index. As we scan, this holds every number we’ve already visited.
If the complement is in our map, we found a pair that sums to target.
Record this number for future lookups.
Let’s trace through an example:
nums = [2, 7, 11, 15], target = 9
i=0: num=2, complement=7, seen={} -> miss, store 2->0
i=1: num=7, complement=2, seen={2:0} -> hit! return (0, 1)
func findPairWithSum(nums []int, target int) (int, int, bool) {
seen := make(map[int]int)
for i, num := range nums {
complement := target - num
if j, ok := seen[complement]; ok {
return j, i, true
}
seen[num] = i
}
return 0, 0, false
}
func main() {
i, j, found := findPairWithSum([]int{2, 7, 11, 15}, 9)
fmt.Printf("indices: (%d, %d), found: %v\n", i, j, found)
i, j, found = findPairWithSum([]int{3, 2, 4}, 6)
fmt.Printf("indices: (%d, %d), found: %v\n", i, j, found)
_, _, found = findPairWithSum([]int{1, 2, 3}, 10)
fmt.Printf("found: %v\n", found)
}