CATEGORY 4 OF 13

Hash Map Basics

Learn the most versatile data structure in programming: hash maps (dictionaries, objects). Master creation, lookup, counting, and grouping patterns that appear in nearly every coding problem.

Time: O(1) average per operation, O(n) to build

Space: O(n)

Learn & Reference

Understanding the Pattern

Hash Map Basics

A hash map (also called a dictionary, associative array, or object) stores key-value pairs with O(1) average lookup time. It's arguably the most-used data structure in real-world programming and interview problems alike.

Why Hash Maps Matter

Nearly every "find something efficiently" problem benefits from a hash map. Instead of scanning an array repeatedly (O(n) per lookup), store what you've seen in a map for instant access.

Core Operations

Create and Access

All languages provide a built-in hash map type. You create one, insert key-value pairs, and retrieve values by key — all in O(1) average time.

Check Existence

Before accessing a key, check if it exists. Each language has its own idiom: in (Python), has() (JS/TS), containsKey() (Java), comma-ok (Go).

Delete

Remove a key-value pair when you no longer need it. Some languages return the old value, others don't.

Iterate

Loop over all keys, all values, or all key-value pairs. Iteration order depends on the language and map type.

Common Patterns

Counting / Frequency

The #1 hash map pattern: count how many times each element appears. Initialize counts to 0 (or use defaultdict/getOrDefault), then increment as you scan.

Grouping

Group elements by some property — the key is the group label, the value is a list of elements belonging to that group.

Lookup Table

Pre-compute values into a map so you can retrieve them in O(1) later. Convert arrays into maps for fast cross-referencing.

Two-Pass Pattern

First pass: build the map. Second pass: query the map. This separates data collection from data usage.

Key Principles

Choose the right key — the key should be whatever you're looking up by. If you're checking for duplicates, the element itself is the key
Default values matter — use defaultdict(int), getOrDefault(), or ?? 0 to avoid "key not found" errors
Maps are unordered — don't rely on insertion order (except in Python 3.7+ dicts and JS Maps)
Keys must be hashable — in most languages, mutable objects (lists, arrays) can't be keys. Use tuples or strings instead

Common Mistakes

Accessing a missing key: In Python, dict[key] throws KeyError if the key doesn't exist. Use .get(key, default) instead
Forgetting to initialize: Incrementing a counter that doesn't exist yet causes errors. Use defaultdict or check-then-set
Using mutable keys: Lists/arrays can't be dictionary keys in most languages. Convert to tuples or strings first
Confusing Map vs Object in JS: Map preserves insertion order and allows any key type; plain objects coerce keys to strings
Overcomplicating with nested maps: Often a single map with a compound key (tuple or string) is simpler than nested maps

When to Use

Count occurrences or frequency of elements

Check if an element has been seen before

Group elements by a shared property

Build a lookup table for O(1) access

Find pairs or matches between two collections

Remove duplicates while preserving information

Map one value to another (translation/encoding)

Template

1# Hash Map / Dictionary Basics
2# Create: d = {} or defaultdict(int)
3# Access: d[key], d.get(key, default)
4# Check:  key in d
5# Delete: del d[key], d.pop(key, default)
6
7def solve(data):
8    freq = {}
9    for item in data:
10        freq[item] = freq.get(item, 0) + 1
11    return freq

{ }

Syntax Reference

1# Create
2d = {}                          # empty dict
3d = {"a": 1, "b": 2}           # with initial values
4d = dict(a=1, b=2)             # keyword constructor
5from collections import defaultdict
6dd = defaultdict(int)           # auto-initializes missing keys to 0
7dd = defaultdict(list)          # auto-initializes to []
8
9# Access
10val = d["key"]                  # raises KeyError if missing
11val = d.get("key", default)    # returns default if missing
12d["key"] = value               # set / overwrite
13
14# Check & Delete
15"key" in d                     # True/False
16del d["key"]                   # remove (raises KeyError if missing)
17val = d.pop("key", default)    # remove and return
18
19# Iterate
20for k in d:                    # keys
21for k, v in d.items():         # key-value pairs
22for v in d.values():           # values only
23len(d)                         # number of entries
24
25# Counting shortcut
26from collections import Counter
27counts = Counter(arr)          # frequency map in one line
28counts.most_common(k)          # top k elements

📋

Common Recipes

1# --- Count Frequency ---
2from collections import Counter
3def count_freq(arr):
4    return Counter(arr)
5# Or manually:
6# freq = {}
7# for x in arr:
8#     freq[x] = freq.get(x, 0) + 1
9
10# --- Group Elements by Property ---
11from collections import defaultdict
12def group_by_length(words):
13    groups = defaultdict(list)
14    for w in words:
15        groups[len(w)].append(w)
16    return dict(groups)
17
18# --- Check for Duplicates ---
19def has_duplicates(arr):
20    seen = set()
21    for x in arr:
22        if x in seen:
23            return True
24        seen.add(x)
25    return False
26
27# --- Two-Array Intersection ---
28def intersection(a, b):
29    set_a = set(a)
30    return [x for x in b if x in set_a]

O(n)

Complexity

Operation	Average	Worst	Notes
Insert / Set	O(1)	O(n)	Amortized O(1); O(n) on hash collision
Lookup / Get	O(1)	O(n)	O(n) only with pathological collisions
Delete	O(1)	O(n)	Same as lookup
Check existence	O(1)	O(n)	containsKey / in / has
Iterate all entries	O(n)	O(n)	Must visit every key-value pair
Count frequency (n items)	O(n)	O(n)	One pass with O(1) per insert

Watch Out

✗Accessing a missing key: In Python, `dict[key]` throws `KeyError` if the key doesn't exist. Use `.get(key, default)` instead
✗Forgetting to initialize: Incrementing a counter that doesn't exist yet causes errors. Use `defaultdict` or check-then-set
✗Using mutable keys: Lists/arrays can't be dictionary keys in most languages. Convert to tuples or strings first
✗Confusing Map vs Object in JS: `Map` preserves insertion order and allows any key type; plain objects coerce keys to strings
✗Overcomplicating with nested maps: Often a single map with a compound key (tuple or string) is simpler than nested maps

PRACTICE PROBLEMS

Number & Math

Iteration Patterns