How list, dict and set work

Part of the free LogicWiz Python course, Module 13: Python under the hood. The examples and practice run in the app.

Kabir's attendance checker took ages to mark 50,000 roll numbers. Meher changed one pair of brackets, [...] to {...}, and it finished instantly. What did the brackets change inside Python?

You'll learn to

• Explain why a list is a dynamic array and why `append` is fast on average
• Explain how dict and set use hashing, and what makes a key hashable
• Know the time cost of common operations: `in`, `append`, `pop(0)`, string `+=`
• Pick the right structure for fast lookups

Learn

A list is a dynamic array

A list stores, side by side in memory, references to its items: slot 0, slot 1, slot 2. So items[5000] jumps straight to slot 5000: O(1), the same time for any index.

When the slots run out, the list grabs a bigger block, copies the references over, and keeps some spare slots. That is called over-allocation. Most appends just fill a spare slot; only now and then does a costly resize happen. On average (amortised) append is O(1).

See the list grow in jumps

import sys

items = []
last = sys.getsizeof(items)
for i in range(20):
    items.append(i)
    size = sys.getsizeof(items)
    if size != last:
        print("resized at length", len(items))
        last = size

The size changes only at some lengths, not at every append: the spare slots absorb the rest. The exact byte sizes differ between machines (64-bit laptop vs the 32-bit browser), so watch the pattern, not the numbers.

dict and set are hash tables

To store a key, Python computes hash(key), a whole number, and uses it to pick a slot in a table. To look the key up later, it hashes again and jumps to the same slot. No scanning, so lookup is O(1) on average.

Two keys can land in the same slot (a collision). CPython then probes other slots until it finds the key or an empty one, comparing with ==. That is why keys need both a stable hash and ==.

Since Python 3.7, a dict also remembers insertion order. A set does not promise any order.

Hashes and keys

print(hash("chai") == hash("chai"))
print(hash(10) == hash(10.0))
print({"b": 1, "a": 2})
print(hash((1, 2)) == hash((1, 2)))
try:
    stock = {["chai", "small"]: 5}
except TypeError as e:
    print("TypeError:", e)

Equal values must have equal hashes, so 10 and 10.0 hash the same. A list has no hash: it could change after being stored, and then it would sit in the wrong slot.

What is hashable?

An object is hashable if its hash never changes during its life and it can be compared with ==.

• Hashable: int, float, str, bool, None, frozenset, and a tuple whose items are all hashable.
• Not hashable: list, dict, set.
• Your own class: hashable by identity by default. If you define __eq__, Python sets __hash__ to None (unhashable) until you also define __hash__, using the same fields as __eq__.

The cost of common operations

Fixes: use a set for repeated in checks, collections.deque for a queue (popleft is O(1)), and "".join(parts) to build a long string.

Timing `in`: list vs set

import time

rolls = list(range(50000))
roll_set = set(rolls)
wanted = range(0, 50000, 25)

start = time.perf_counter()
found_list = sum(1 for r in wanted if r in rolls)
t_list = time.perf_counter() - start

start = time.perf_counter()
found_set = sum(1 for r in wanted if r in roll_set)
t_set = time.perf_counter() - start

print("same answer:", found_list == found_set)
print("set was faster:", t_set < t_list)
print("list took roughly", round(t_list / t_set), "times longer")

The exact times change from run to run and phone to laptop. What stays true: the list does about n/2 comparisons per lookup, the set about one.

if x in some_list: inside a loop over another list is a hidden O(n²): 50,000 × 50,000 comparisons. Turn the list into a set once, before the loop: seen = set(some_list).

List vs tuple inside: a tuple is a fixed-size array, so it needs no spare slots and takes a little less memory; it is immutable, so it can be hashed (if its items can) and used as a dict key. A list over-allocates so it can grow cheaply.

In one line

A list is a growing array (index O(1), in O(n), pop(0) O(n)); dict and set are hash tables (in O(1)) that need hashable keys.

Interview corner

How is a Python dict implemented?

As a hash table. The key's hash() picks a slot; collisions are resolved by probing other slots and comparing keys with ==. CPython keeps a compact array of entries in insertion order plus a sparse index table, which is why dicts remember insertion order (guaranteed since 3.7). Lookup, insert and delete are O(1) on average.

Why must dictionary keys be hashable (immutable)?

A key is stored in the slot chosen by its hash. If the key could change, its hash would change and the dict could never find it again. So keys must have a hash that never changes and a consistent __eq__: equal keys must have equal hashes.

What is the time complexity of `append`, `pop(0)` and `x in list`?

append is amortised O(1) thanks to over-allocation. pop(0) is O(n) because every remaining item shifts left (use collections.deque.popleft() instead). x in list is O(n); x in set is O(1) on average.

How do a list and a tuple differ internally?

A list is a dynamic array with spare capacity so it can grow; a tuple is a fixed-size array with no spare room, so it is slightly smaller and faster to create. A tuple is immutable and therefore hashable when its items are, so it can be a dict key; a list cannot.