Data Structures
Hash Map (Dictionary) Basics
Difficulty: Beginner
Two Sum is the canonical example: scan the array once, and for every number x ask the data structure whether you have already seen target - x. With a list that is O(n^2). With a Hash Map, the lookup becomes a single function call and the...
Hash Map (Dictionary) Basics
Two Sum is the canonical example: scan the array once, and for every number x ask the data structure whether you have already seen target - x. With a list that is O(n^2). With a Hash Map, the lookup becomes a single function call and the whole algorithm collapses to O(n).
This lesson covers the key-value abstraction, the intuition behind a hash function (a key gets converted to a bucket index by an integer-valued function), what a collision is, and how get, set, delete, and has behave in JavaScript's Map and Python's dict. You will also meet two recurring patterns: counting frequencies and bucketing/grouping by a derived key, both of which appear in dozens of interview problems and real applications such as analytics, caching, and indexing.
In Arrays & Strings, you saw that searching an unsorted array is O(n) because every position is equally plausible. A hash map turns that linear scan into an arithmetic computation that points directly at the right slot, which is the entire reason hash-based lookups dominate practical software.
With key-based lookup in hand, Set Basics specializes the same machinery to a single question: have I seen this value before?
Prerequisites:
Arrays & StringsTopics:
What You'll Learn
By the end of this lesson, you will be able to:
Explain the key-value concept and how a hash function maps keys to array indices.
Implement get, set, delete, and has operations on a hash map from scratch.
Describe collision handling via chaining and open addressing (linear probing).
Explain load factor, why resizing is needed, and its amortized cost.
State time complexity for hash map operations: O(1) average, O(n) worst case.
Identify when to use hash maps vs arrays vs sets and apply the frequency-counting pattern.
Why This Matters
01
Hash maps are the single most common data structure in coding interviews -- nearly every 'optimize from O(n^2) to O(n)' solution involves a hash map for O(1) lookups.
02
In real-world software, hash maps power caches, database indexes, symbol tables, configuration stores, and session management -- any time you need fast key-based retrieval.
03
Understanding how hash maps work internally (hash functions, collisions, load factor) helps you predict when O(1) degrades to O(n) and choose appropriate data structures.
Key Terms
7 terms you'll encounter in this lesson
Hash Map (Dictionary)
A data structure that stores key-value pairs and uses a hash function to map keys to array indices for O(1) average-case access.
Hash Function
A function that converts a key (string, number, etc.) into an integer index within the underlying array. A good hash function distributes keys uniformly.
Collision
When two different keys produce the same hash index. Must be resolved via chaining (linked lists at each slot) or open addressing (probing for the next empty slot).
Chaining
A collision resolution strategy where each array slot holds a linked list (or array) of all key-value pairs that hash to that index.
Open Addressing
A collision resolution strategy where, upon collision, the algorithm probes subsequent slots (linear probing, quadratic probing, or double hashing) until an empty slot is found.
Load Factor
The ratio of stored entries to total capacity (n / capacity). When it exceeds a threshold (commonly 0.75), the table resizes to maintain O(1) performance.
Rehashing
The process of creating a larger array and re-inserting all existing key-value pairs using the hash function with the new capacity. Triggered when the load factor exceeds the threshold.
Related Problems
Coding problems that put this lesson's concepts into practice
Heads Up
Common misconceptions to watch out for
"Hash maps are always O(1)"
Hash maps are O(1) on AVERAGE. In the worst case (all keys collide into one slot), operations degrade to O(n). A good hash function and proper load factor management keep the average case close to O(1).
"Keys in a hash map are stored in insertion order"
Standard hash maps do NOT guarantee order. In Python 3.7+, dict preserves insertion order as an implementation detail, but this is not true for all languages or hash table implementations. JavaScript's Map does preserve insertion order by spec.
"You can use any object as a hash map key"
Keys must be hashable (immutable in Python: strings, numbers, tuples). In JavaScript, Object keys are always strings; use Map for non-string keys. Mutable objects like lists/arrays cannot be dictionary keys in Python.
"Resizing a hash map is O(n^2)"
A single resize is O(n) because each of the n elements must be rehashed. But resizing happens rarely (only when load factor is exceeded), so the AMORTIZED cost of insertion remains O(1).