How are Python dictionaries implemented and ordered?

Q: How are Python dictionaries implemented and ordered?

**Target Audience:** Beginners who use dicts daily and want to know what happens underneath; anyone preparing for a Python interview. **Difficulty:** Easy **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). > **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 Picture a coat check at a theatre. You hand over your coat and get a ticket with a number. When you come back, the attendant does not search every coat on every rack; the ticket number tells them exactly which hook to walk to. If two guests somehow get sent to the same hook, the attendant has a simple rule: "try the next hook along until you find the right coat or an empty hook". Now add a sec

The problem

Question presented to candidate: "Dictionaries are everywhere in Python. How does a dict actually find a value by its key so fast, and why does it remember the order you inserted things in? Was that always the case?"

What a strong answer should cover:

A dict is a hash table: hash(key) picks a starting slot, collisions are resolved by open addressing (probing other slots), and == confirms the match, giving average O(1) get, set and delete.
Keys must be hashable; equal keys must hash alike, which is why 1, 1.0 and True are one key.
The compact layout (CPython 3.6+): a small sparse indices table pointing into a dense entries array of (hash, key, value) kept in insertion order. Iteration walks the dense array, which is where the order comes from.
The version fact: insertion order was a CPython 3.6 implementation detail and became a language guarantee in 3.7; updating a value keeps the position, delete + re-insert moves the key to the end.
Resizing keeps the table at most about two thirds full; worst case lookup is O(n) when many keys collide.

Code / implementation expected: Optional — a short demo of ordering rules, or a sketch of the indices + entries layout.

dict
data-structures

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: Beginners who use dicts daily and want to know what happens underneath; anyone preparing for a Python interview. Difficulty: Easy 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).

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

Picture a coat check at a theatre. You hand over your coat and get a ticket with a number. When you come back, the attendant does not search every coat on every rack; the ticket number tells them exactly which hook to walk to. If two guests somehow get sent to the same hook, the attendant has a s

The solution is hidden so you can try first

13 min read · 12 sections

Run the code

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

PythonDict ordering rules, key equality and resize points

Practice

PythonA model of the compact dict: indices, entries and probing

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.