HashingData structureaka dictionary, dict, unordered_map, associative array, Map

Hash Map

A key → value store backed by a hash table with expected O(1) get, put, and delete.

▶ Visualize Pattern: Hashing Practice (8)

Progress

Definition

A hash map is the key → value interface of a Hash Table. put(k, v) associates a value with a key, get(k) retrieves it, remove(k) deletes it — all in expected O(1).

It is the most used data structure in interview solutions: counting frequencies, indexing elements by value, memoizing subproblems, mapping ids to objects, and building adjacency lists all reduce to a hash map.

Language implementations: Python dict (insertion-ordered, open addressing), Java HashMap (chaining with treeified bins), C++ std::unordered_map (chaining), JavaScript Map (insertion-ordered), Go map (bucketed open addressing).

key-valueO(1) averagedictionarycountingmemoization

Intuition

A mental model before the formal terms.

A phone book where instead of flipping to a page, you compute the page number from the name. The book is unordered and has some blank pages, but every name is exactly where the computation says it is.

Under the hood it is the coat check from Hash Table: the ticket is the key, the coat is the value.

How it works

Hash the key to a bucket index.
put: search the bucket for an equal key; overwrite its value if found, else append a new (key, value) entry and grow the table if the load factor is exceeded.
get: search the bucket for an equal key; return its value or a sentinel (None, null, undefined).
remove: search and unlink the entry.
Convenience operations are built on these: getOrDefault, computeIfAbsent, counter[k] += 1, setdefault.

Why it works

Inherits the O(1) expected bound of the underlying Hash Table: a bounded load factor keeps buckets short and uniform hashing keeps them balanced.

Keys are compared with equals after matching hashes, so distinct keys with equal hashes are still distinguished.

Operations

Operation	Description	Cost
put(k, v) / set	Insert or overwrite.	O(1) average
get(k)	Retrieve the value or a sentinel.	O(1) average
remove(k) / delete	Remove the entry.	O(1) average
containsKey(k) / has	Membership test.	O(1) average
keys() / values() / entries()	Iterate all stored data.	O(n)
size()	Number of entries.	O(1)

Recognition

How to tell a problem wants this.

"Count how many times…", "find the first/most frequent…", "is there a pair such that…".
You need to remember something about each element you have already seen while scanning once (index, count, last position).
Memoization of a recursive function keyed by its arguments.
Grouping items by a computed key (anagrams, same remainder, same length).

“have you seen this before” → Hashing “sum of subarray” → Prefix Sum

Interactive demo

Play, step, change the input. ← → and space work too.

Showing the closely related Hash Table visualization.

Commands — insert N, search N, delete N — m = 7 buckets, hash = key % 7

∅

bucket 0

∅

bucket 1

∅

bucket 2

∅

bucket 3

∅

bucket 4

∅

bucket 5

∅

bucket 6

∅

1/41Empty table with m = 7 buckets. Colliding keys share a bucket as a linked chain, so the table never "fills up" — only the chains grow.

Hashed bucketChain node comparedMatchInserted / removed

PseudocodeLearn Hash Table →

1h = key % m
2insert: scan bucket[h]; if key present: done, else append to the chain
3search: scan bucket[h] comparing each key
4delete: scan bucket[h]; unlink the matching node

Variables

size0

load0.00

Complexity

access O(1)

search O(1)

insert O(1)

delete O(1)

Speed

Pseudocode

1class HashMap:
2  table = HashTable()
3  put(k, v): table.put(k, v)
4  get(k): return table.get(k) or null
5  remove(k): table.remove(k)
6  getOrDefault(k, d): v = get(k); return v if v != null else d

Implementation

1from collections import Counter, defaultdict
2 
3 
4# dict is the built-in hash map. This shows the core API.
5def demo() -> None:
61 · Create and insert
7    ages: dict[str, int] = {}
8    ages["alice"] = 30              # insert or overwrite
9    ages.setdefault("bob", 25)      # insert only if absent
10    ages["bob"] = 26                # overwrite
11 
122 · Lookup without inserting
13    if "carol" not in ages:
14        print("carol missing")
15    bob_age = ages.get("bob", -1)
16 
173 · Counting pattern
18    words = ["a", "b", "a"]
19    freq: defaultdict[str, int] = defaultdict(int)
20    for w in words:
21        freq[w] += 1
22    counts = Counter(words)          # same thing, batteries included
23 
244 · Erase and iterate
25    del ages["alice"]
26    for name, age in ages.items():   # insertion order (3.7+)
27        print(name, age)
28    print("size", len(ages), "bob", bob_age, dict(freq), counts.most_common(1))
29 
30 
31demo()

Walkthrough

dict[str, int] annotates the map; ages["alice"] = 30 inserts or overwrites.
setdefault inserts only when absent and returns the value; get(key, default) reads without inserting.
"carol" not in ages is the membership test — O(1).
defaultdict(int) makes freq[w] += 1 work without a check; Counter is a specialised dict for counting.
del ages["alice"] raises KeyError if missing; ages.pop("alice", None) does not. Iteration is insertion-ordered.

Complexity (this implementation)

time O(1) average per operation · space O(n)

Language notes

Dict preserves insertion order since 3.7 — OrderedDict is only needed for move_to_end.
Dict comprehensions {k: v for ...} and dict(zip(keys, values)) build maps concisely.
Keys must be hashable; use tuple instead of list for composite keys.

Common mistakes in this language

Iterating for k in d and deleting inside the loop (RuntimeError: dictionary changed size).
Using defaultdict and then checking key in d after an accidental read created the key.
Passing a mutable default like {} as a function argument default.

Language differences that matter here

Insertion order: Python dict (3.7+) and JS/TS Map are ordered; C++ unordered_map is not.
Missing-key access: C++ operator[] inserts a default; Python d[k] raises KeyError; JS get returns undefined.
JS objects stringify keys and expose prototype properties; Map, dict and unordered_map keep key types.
Sorted alternative: C++ std::map, Python sortedcontainers (third-party), JS none built in.

Complexity

Operation	Average	Worst	Note
Access	O(1)	O(n)	By key.
Search	O(1)	O(n)	By key; searching by value is O(n).
Insert	O(1)	O(n)	Amortized; resize is O(n).
Delete	O(1)	O(n)
Update	O(1)	O(n)
Iterate	O(n)	O(n + m)
Space	O(n)

Advantages & disadvantages

Advantages

Expected constant-time operations for any hashable key.
Extremely versatile: counters, indexes, caches, graphs, and memo tables are all one-liners.
Insertion-ordered in Python and JavaScript, which often removes the need for a separate ordering structure.

Disadvantages

No sorted order or range queries.
Memory-heavy compared with arrays: boxed keys/values, hash storage, empty slots.
Worst-case O(n) operations under pathological hashing; unpredictable resize pauses.

Use cases

Frequency counting and anagram grouping.
Two-sum style complement lookup and prefix-sum → count maps.
Memoization tables for Dynamic Programming and Memoization (Top-Down DP).
Adjacency lists keyed by node id, id → object registries, configuration lookups.

Use it when

Any lookup by key where order does not matter.
Counting, indexing, grouping, and caching during a single pass.
Memoizing recursive calls keyed by argument tuple.

Avoid it when

Keys are dense integers 0..k — a plain array is faster and uses less memory.
You need sorted keys, floor/ceiling, or range scans — use a balanced BST / TreeMap.
You only need membership, not values — a Hash Set is clearer and smaller.
Prefix matching over strings — use a Trie.

Alternatives

Hash Set Array AVL Tree Red-Black Tree Trie

Compare: Hash Map vs Tree Map Compare: Trie vs Hash Map

Common mistakes

Checking if map[key] instead of key in map when the stored value may be falsy (0, "", false).
Using plain JS objects as maps with non-string keys (they are coerced to strings) — use Map.
Mutating a key object after insertion.
Relying on iteration order in Java HashMap, C++ unordered_map, or Go map (Go randomises it on purpose).
In Two Sum, inserting the current element before checking for its complement, so target/2 matches itself.

Interview patterns

Complement lookup: Two Sum, Subarray Sum Equals K (prefix sum → count).
Frequency map + heap: Top K Frequent Elements.
Grouping by canonical key: Group Anagrams.
Index map for O(1) delete in an array: Insert Delete GetRandom O(1).
Map + doubly linked list: LRU Cache.

Interview questions on this

Recognizing the approach from an array and a targetIntermediate
Deciding whether O(n²) can be improvedIntermediate
Hash map or array?Beginner
Average case versus worst caseIntermediate

Mock interviews

Minimum Size Subarray SumIntermediate
Two SumBeginner
Longest Substring Without Repeating CharactersIntermediate

Interview problems

Two Sumeasy Group Anagramsmedium Design HashMapeasy Insert Delete GetRandom O(1)medium Repeated DNA Sequencesmedium LRU Cachemedium Subarray Sum Equals Kmedium Top K Frequent Elementsmedium

Definition

Intuition

How it works

Why it works

Operations

Recognition

Interactive demo

Pseudocode

Implementation

Complexity

Advantages & disadvantages

Use cases

Alternatives

Common mistakes

Interview patterns

Interview problems

Related