How does a Python set find items? | Interview Question

Q: How does a Python set find items?

**Target Audience:** Developers who know what a set is and want to explain how membership tests work; no prior hash-table knowledge needed. **Difficulty:** Medium **Python version:** Behaviour checked on CPython 3.11 (python3.11 and the in-page Pyodide 0.25.1 runtime, which is CPython 3.11.3). Probe constants are CPython implementation details. > **How to read this doc:** Each idea is explained in plain language first, then tagged with `📌 Interview term:` so you also learn the exact word an interviewer expects. Every output in the **Verified** section was copied from a real run of the examples on this page. ## 1. Why This Even Matters — A Story First Imagine a block of post office boxes. A clerk does not keep letters in one long pile and search through it. Each letter's postcode is turned into a box number by a fixed rule, so to check "is there a letter for Ana?" the clerk walks straight to one box. If someone else's letter is already in that box (a collision), the clerk follows a

The problem

Question presented to candidate: "x in my_list is slow for a big list, but x in my_set is fast. What does a set actually do to find x, which of your object's methods does it call, and when does that speed break down?"

What a strong answer should cover:

A set is a hash table of keys only: hash(x) picks a starting slot (hash & mask), and the search walks a probe sequence until it hits the key or an empty slot. Average O(1), worst case O(n).
The match test, in order: equal stored hash, then identity (is), then __eq__. So __eq__ runs only on a hash match, and the identity shortcut is why the same NaN object is found.
The rules this imposes: members must be hashable, equal objects must hash alike ({1, 1.0, True} has one element), and mutating an object's hash after insertion loses it.
A CPython detail: sets probe a few neighbouring slots linearly (LINEAR_PROBES, 9) before jumping with the perturbed 5*i + 1 + perturb step, and resize at about 60% full, growing 4x.
Order: iteration walks slots, so set order depends on hashes, is not insertion order, and can change between runs for strings (hash randomisation).

Code / implementation expected: Optional — instrumenting __hash__ / __eq__ to show which calls a lookup makes is a strong answer.

set
hashing

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Developers who know what a set is and want to explain how membership tests work; no prior hash-table knowledge needed. Difficulty: Medium Python version: Behaviour checked on CPython 3.11 (python3.11 and the in-page Pyodide 0.25.1 runtime, which is CPython 3.11.3). Probe constants are CPython implementation details.

How to read this doc: Each idea is explained in plain language first, then tagged with 📌 Interview term: so you also learn the exact word an interviewer expects. Every output in the Verified section was copied from a real run of the examples on this page.

1. Why This Even Matters — A Story First

Imagine a block of post office boxes. A clerk does not keep letters in one long pile and search through it. Each letter's postcode is turned into a box number by a fixed rule, so to check "is there a letter for Ana?" the clerk walks stra

The solution is hidden so you can try first

15 min read · 11 sections

Run the code

Edit the code and run it here. Each console line with an expected value becomes a test.

PythonWhich of your methods a set lookup calls

Practice

PythonSlots, collisions, growth and a lost member

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.