Intuition Rewire
Esc
  • Loading…
↑ ↓ to moveEnter to openEsc to close

Hash Map

Learn how a hash map finds any key in one step, then use it to crack the 11 counting, prefix-sum and sliding-window questions interviews ask most.

  • 4 Lessons
  • 11 Problems
  • 48 Illustrations

Dry-run engine

Linear Probing (Open Addressing)

A hash table is just an array plus a function that turns keys into indices.

O(1) Avg Lookup
Input · Keys
10, 22, 31, 4, 15
Output · get(4)
Press play to run it
How it works

Store key k at bucket k % 7. If that bucket is taken, probe the next one (i + 1, wrapping around) until an empty bucket turns up. Lookups follow the same path.

bucket_array[7]

  • key—
  • Hash h(k)—
  • Probe path—
  • Load factor0 / 7

A hash table is a plain contiguous array of buckets. h(k) = k % 7 turns any key into a bucket index with one division — no searching.

1 / 7

What you will learn

  • What a hash map is: keys, values, and the O(1) put, get and remove that make it special
  • How it works inside: hash functions, buckets, collisions, load factor and resizing
  • When a problem wants a hash map: counting, “have I seen this before?”, prefix sums and sliding windows
  • How to use the built-in map in JavaScript, Python, Java and C++, and the traps in each
  • The prefix sum + hash map trick behind every “subarray with sum …” question
  • Brute force, optimal and best solutions for 11 interview questions, each with a dry-run simulator

Why this course

A hash map stores key → value pairs and finds any key in about one step, however many entries it holds. That one ability — looking things up by what they are instead of where they are — turns a whole family of O(n²) problems into O(n) ones.

The introduction is short but complete: what a hash map is, how it works inside, when to reach for one and how to use it in four languages. Every idea is drawn, and every lesson has a simulator you can step through.

Then come 11 interview questions in three groups — counting, prefix sums + hash map and sliding window + hash map — ordered from easiest to hardest, so each one builds on the last. Every problem goes from brute force to optimal to the best solution, with code in four languages and its common variations.

Requirements

  • Comfort writing loops, conditionals and functions in at least one language
  • The Arrays course helps: prefix sums and the sliding window come back here

Course Contents

Related courses