Hash Maps: O(1) Lookup

Arrays & Hashing, lesson 1 of 3

Hash Maps: O(1) Lookup

Why sets and dicts turn O(n²) searches into a single O(n) pass.

12 min, 0 of 3 activities solved

View cheatsheet

Getting Python ready… examples can run in a moment.

A huge share of interview problems hide the same question: "have I seen this before?"

With a list, answering it means scanning every element: x in my_list is O(n). Ask it once per element and you're at O(n²).

A set or dict answers it in O(1) on average. Python runs the key through hash(), which turns it into a number, and uses that number to jump straight to a slot (a "bucket") in an internal table.

To check x in s, Python hashes x again, lands on the same slot and compares one item. No scanning. Step through it below with small ints, which conveniently hash to themselves (string hashes change every time Python starts).

Walkthrough

A set's slots: s = {13, 6, 20}

slot01234567
Step 1 of 6

A new small set has a table of 8 slots. Where a value goes is decided by its hash, not by when it was added.

slot being used
found

When two values want the same slot (a collision), Python tries another slot. Collisions are rare, which is why lookups are O(1) on average.

Example

List vs set membership

Same 500 lookups, same answer. The list walks up to 20,000 items per lookup; the set jumps straight to the slot. Double n and watch only the list time grow.

Brute force vs the pattern. "Does this list contain a duplicate?" The brute force compares every pair: O(n²) time, O(1) space. The hashing version walks once and remembers what it has seen: O(n) time, O(n) space.

That's the core trade of this whole unit: spend memory to save time. Interviewers expect you to name it out loud.

Example

Pairs vs a seen set

Both find the duplicate, but the pair version does about half a million comparisons, the set version 1,001. Notice the order inside the loop: check first, then add.

What can be a key? Only hashable values: ints, floats, strings, tuples (of hashables) and frozensets. Lists, dicts and sets are mutable, so their hash could change after you store them, and Python refuses:

Example

Unhashable keys

The fix is almost always tuple(my_list). You'll use tuple keys constantly in this unit: grid cells, letter counts, slopes.

Quiz

What does this print?

Quiz

Which of these can NOT be used as a set element or dict key?

Exercise

First repeat

Write first_repeat(nums) that returns the first value whose second appearance comes earliest while scanning left to right, or None if every value is unique.

first_repeat([3, 1, 4, 1, 5, 3]) is 1: the second 1 (index 3) shows up before the second 3 (index 5).

Do it in one pass with a set.