DSA Tutorial #4: Hash Maps and Sets — O(1) Lookup Explained

Hash maps are the most useful data structure for coding interviews. If you can only master one data structure beyond arrays, make it hash maps. They give you O(1) average-time lookups, insertions, and deletions. Many interview problems that seem hard become easy once you use a hash map.

In this article, you will learn how hashing works, when to use hash maps vs hash sets, and how to solve classic interview problems. We show every example in Kotlin, Python, and Go.

What is Hashing?

Hashing is a process that converts a key (like a string or number) into an index in an array. The function that does this conversion is called a hash function.

Here is the basic idea:

1. You have a key (for example, the string “apple”)
2. The hash function converts “apple” into a number (for example, 42)
3. You store the value at index 42 in an internal array

When you look up “apple” later, the hash function converts it to 42 again, and you go directly to index 42. No searching needed. That is why the lookup is O(1).

What is a Hash Map?

A hash map (also called a dictionary, hash table, or associative array) stores key-value pairs. Each key maps to one value. You can look up a value by its key in O(1) average time.

Hash Map Operations

The worst case O(n) happens when many keys produce the same hash (called a collision). With a good hash function, this is rare in practice.

Basic Hash Map Operations

Kotlin:

fun main() {
    val map = mutableMapOf<String, Int>()

    // Put - insert key-value pairs
    map["apple"] = 3
    map["banana"] = 5
    map["cherry"] = 2

    // Get - look up by key
    println(map["apple"]) // 3
    println(map["grape"]) // null (key not found)

    // Contains key
    println(map.containsKey("banana")) // true

    // Remove
    map.remove("cherry")

    // Iterate
    for ((key, value) in map) {
        println("$key: $value")
    }
}

Python:

# Create a dictionary (hash map)
counts = {}

# Put - insert key-value pairs
counts["apple"] = 3
counts["banana"] = 5
counts["cherry"] = 2

# Get - look up by key
print(counts["apple"])  # 3
print(counts.get("grape", -1))  # -1 (default for missing key)

# Contains key
print("banana" in counts)  # True

# Remove
del counts["cherry"]

# Iterate
for key, value in counts.items():
    print(f"{key}: {value}")

Go:

package main

import "fmt"

func main() {
    // Create a map
    m := make(map[string]int)

    // Put - insert key-value pairs
    m["apple"] = 3
    m["banana"] = 5
    m["cherry"] = 2

    // Get - look up by key
    fmt.Println(m["apple"]) // 3
    val, ok := m["grape"]
    fmt.Println(val, ok) // 0 false

    // Contains key
    _, exists := m["banana"]
    fmt.Println(exists) // true

    // Remove
    delete(m, "cherry")

    // Iterate
    for key, value := range m {
        fmt.Printf("%s: %d\n", key, value)
    }
}

What is a Hash Set?

A hash set stores unique elements only. There are no key-value pairs — just keys. It supports O(1) average-time membership checks. Use a hash set when you need to quickly check if an element exists.

Kotlin:

fun main() {
    val set = mutableSetOf<Int>()

    // Add elements
    set.add(10)
    set.add(20)
    set.add(10) // duplicate, ignored

    // Check membership
    println(set.contains(10)) // true
    println(set.contains(30)) // false

    // Remove
    set.remove(20)

    println(set) // [10]
}

Python:

s = set()

# Add elements
s.add(10)
s.add(20)
s.add(10)  # duplicate, ignored

# Check membership
print(10 in s)  # True
print(30 in s)  # False

# Remove
s.remove(20)

print(s)  # {10}

Go:

// Go does not have a built-in set. Use a map with empty struct.
set := make(map[int]struct{})

// Add elements
set[10] = struct{}{}
set[20] = struct{}{}
set[10] = struct{}{} // duplicate, overwritten

// Check membership
_, exists := set[10]
fmt.Println(exists) // true

// Remove
delete(set, 20)

How Collisions Work

A collision happens when two different keys produce the same hash. For example, if “apple” and “grape” both hash to index 42, that is a collision.

There are two common ways to handle collisions:

Chaining: Each index in the array holds a linked list. When a collision happens, add the new element to the list at that index. To look up a key, hash it, go to the index, then walk the list.

Open addressing: When a collision happens, look for the next empty slot. Common strategies include linear probing (check the next slot) and quadratic probing (check slots at increasing distances).

You rarely need to implement collision handling in interviews. But understanding it explains why the worst case is O(n) — if all keys collide, the hash map becomes a linked list.

Two Sum with Hash Map

This is the most famous coding interview problem. Given an array and a target sum, find two numbers that add up to the target. Return their indices.

In DSA Tutorial #1, we solved this for sorted arrays using two pointers. The hash map approach works for unsorted arrays too.

Kotlin:

fun twoSum(nums: IntArray, target: Int): IntArray {
    val map = mutableMapOf<Int, Int>() // value -> index

    for (i in nums.indices) {
        val complement = target - nums[i]
        if (map.containsKey(complement)) {
            return intArrayOf(map[complement]!!, i)
        }
        map[nums[i]] = i
    }
    return intArrayOf()
}

Python:

def two_sum(nums: list, target: int) -> list:
    seen = {}  # value -> index

    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i

    return []

Go:

func twoSum(nums []int, target int) []int {
    m := make(map[int]int) // value -> index

    for i, num := range nums {
        complement := target - num
        if j, ok := m[complement]; ok {
            return []int{j, i}
        }
        m[num] = i
    }
    return nil
}

How it works: For each number, calculate the complement (target minus current number). Check if the complement is already in the hash map. If yes, you found the pair. If no, store the current number and its index.

Time complexity: O(n). Space complexity: O(n).

Frequency Counting

Frequency counting is the most common hash map pattern in interviews. Count how many times each element appears, then use the counts to solve the problem.

Group Anagrams

Given a list of strings, group the anagrams together. Two strings are anagrams if they have the same characters. For example, “eat”, “tea”, and “ate” are all anagrams.

The key insight: if you sort the characters of an anagram, you get the same string. Sort each word and use it as the hash map key.

Kotlin:

fun groupAnagrams(strs: Array<String>): List<List<String>> {
    val map = mutableMapOf<String, MutableList<String>>()

    for (s in strs) {
        val key = String(s.toCharArray().apply { sort() })
        map.getOrPut(key) { mutableListOf() }.add(s)
    }
    return map.values.toList()
}

Python:

def group_anagrams(strs: list) -> list:
    groups = {}

    for s in strs:
        key = "".join(sorted(s))
        if key not in groups:
            groups[key] = []
        groups[key].append(s)

    return list(groups.values())

Go:

func groupAnagrams(strs []string) [][]string {
    m := make(map[string][]string)

    for _, s := range strs {
        runes := []rune(s)
        sort.Slice(runes, func(i, j int) bool {
            return runes[i] < runes[j]
        })
        key := string(runes)
        m[key] = append(m[key], s)
    }

    result := make([][]string, 0, len(m))
    for _, group := range m {
        result = append(result, group)
    }
    return result
}

Time complexity: O(n * k log k) where n is the number of strings and k is the maximum string length. The sorting takes O(k log k) per string.

Contains Duplicate

Given an array, return true if any value appears at least twice. This is the simplest hash set problem.

Kotlin:

fun containsDuplicate(nums: IntArray): Boolean {
    val seen = mutableSetOf<Int>()
    for (num in nums) {
        if (!seen.add(num)) return true
    }
    return false
}

Python:

def contains_duplicate(nums: list) -> bool:
    seen = set()
    for num in nums:
        if num in seen:
            return True
        seen.add(num)
    return False

Go:

func containsDuplicate(nums []int) bool {
    seen := make(map[int]struct{})
    for _, num := range nums {
        if _, exists := seen[num]; exists {
            return true
        }
        seen[num] = struct{}{}
    }
    return false
}

Time complexity: O(n). Space complexity: O(n).

When to Use Hash Maps vs Other Structures

Why Interviewers Ask Hash Map Questions

Hash map questions test:

1. Problem-solving instinct — recognizing when O(1) lookup turns an O(n^2) brute force into O(n)
2. Understanding of trade-offs — using extra space (hash map) to save time
3. Key design skills — choosing the right key for the hash map (like sorted string for anagrams)
4. Handling edge cases — missing keys, duplicate values, empty input

Practice Problems

Try these problems on LeetCode:

1. Two Sum (LeetCode #1) — hash map for complement lookup
2. Contains Duplicate (LeetCode #217) — hash set for uniqueness
3. Group Anagrams (LeetCode #49) — hash map with sorted key
4. Longest Consecutive Sequence (LeetCode #128) — hash set for O(n) solution
5. Valid Sudoku (LeetCode #36) — multiple hash sets for validation

What’s Next?

In the next article, we cover Trees — specifically binary trees and binary search trees. Trees are hierarchical data structures that appear in many advanced interview problems. You will learn tree traversals, BST operations, and how to solve tree problems recursively.

Next: DSA Tutorial #5: Trees — Binary Trees and BST

Full series: DSA from Zero to Interview Ready