Hash Maps

A hash map (also called a dictionary, hash table, or associative array) stores key-value pairs with O(1) average time complexity for lookup, insertion, and deletion. It's one of the most powerful and frequently used data structures in coding interviews.

A hash map uses a hash function to convert keys into array indices. When you store a key-value pair, the key is hashed to determine where to store the value. When you look up a key, the same hash function is used to find where the value is stored.

Count occurrences of elements. This is the most common hash map pattern in interviews.

Store previously seen values to find pairs that satisfy a condition.

Group elements by some property using a hash map with list values.

Store computed results to avoid redundant calculations.

When you only need to track if something exists (no values needed), use a set instead of a hash map.

Operation	Average	Worst
Lookup	O(1)	O(n)*
Insert	O(1)	O(n)*
Delete	O(1)	O(n)*
Iteration	O(n)	O(n)

*Worst case O(n) occurs with hash collisions. In practice with good hash functions, this is rare.

Need O(1) lookups: When you need to quickly check if something exists or retrieve associated data.
Counting occurrences: Frequency problems, anagram detection, finding duplicates.
Index mapping: Storing the position of elements for quick lookup (Two Sum pattern).
Grouping data: Grouping elements by some key property.
Caching: Memoization to avoid repeated calculations.

Think "hash map" when you see O(n²) brute force: Many problems with nested loops can be optimized to O(n) using a hash map.
Consider what to store as key vs. value: Sometimes the "obvious" choice isn't optimal.
Use defaultdict or Counter: They simplify code and reduce edge case handling.
Remember hash maps are unordered: If you need ordering, consider OrderedDict or just track order separately.

Was this helpful?

Study plan All problems

Cheat Sheet

How Hash Maps Work

Basic Operations

Creating and Adding

Accessing Values

Removing Elements

Iterating Over Hash Maps

Common Hash Map Patterns

Pattern 1: Frequency Counter

Pattern 2: Two Sum (Index Lookup)

Pattern 3: Grouping by Key

Pattern 4: Caching/Memoization

Pattern 5: Existence Check with Set

Useful Methods

Time Complexity Reference

When to Use Hash Maps

Common Interview Tips

Company

Practice

Learn