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

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:

"cat" --hash()--> 8412... % 8 = 3
"dog" --hash()--> 1937... % 8 = 6

slot: 0   1   2   3      4   5   6      7
      .   .   .   "cat"  .   .   "dog"  .

To check "cat" in s, Python hashes "cat" again, lands on slot 3 and compares one item. No scanning.

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?

3 a

2 b

3 b

2 a

Quiz

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

(1, 2)

"abc"

[1, 2]

frozenset({1, 2})

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.