Lists and dictionaries

What a list actually is#

A CPython list is a PyListObject: a length, an allocated capacity, and a pointer to a heap array of PyObject*. It is a dynamic array of references, never of values. Two consequences follow.

Elements are boxed, so a list of a million floats holds a million pointers plus a million separate 24-byte float objects, scattered across the heap. Iterating it defeats the cache in a way a contiguous buffer does not.

Growth is amortised O(1) because list_resize over-allocates. The pattern in Objects/listobject.c is roughly new_allocated = size + (size >> 3) + 6, a growth factor near 1.125 rather than the 2.0 used by many other languages. Small factor, frequent but cheap reallocations, low memory slack.

Timsort (Peters, 2002) is worth knowing about: it detects existing runs and merges them, so it is O(n) on already-sorted or reverse-sorted input, and it is stable, which is what makes multi-key sorting work by sorting on the least significant key first.

What a dictionary actually is#

A dict is an open-addressed hash table in the compact layout introduced by Raymond Hettinger for Python 3.6. It has two parts: a small indices array of integers, and a dense entries array of (hash, key, value) triples appended in insertion order.

Three properties fall out of that design:

1. Insertion order is preserved, because the entries array is append-only. This became a language guarantee in 3.7, rather than remaining a CPython implementation detail.
2. Memory drops by roughly 20 to 25 percent versus the old sparse table, because the sparse part now stores narrow indices — one byte each while the table is under 128 slots — rather than 24-byte triples.
3. Iteration is a linear walk over a dense array, so it is cache-friendly.

Collisions are handled by open addressing with a perturbed probe sequence, not by chaining:

perturb = hash
i = hash & mask
loop:
    i = (5 * i + 1 + perturb) & mask
    perturb >>= 5

Mixing the high bits of the hash back in via perturb is what stops clustered hashes from degenerating. The table is resized when it reaches two thirds full.

Lookup, insert and delete are O(1) average and O(n) worst case. The worst case is reachable by an adversary who controls the keys, which is why string hashing is randomised per process under PEP 456 (SipHash-1-3). A practical consequence: hash("abc") differs between runs unless PYTHONHASHSEED is fixed, so never persist a hash value or rely on set iteration order for reproducible output.

The hashability contract#

A key must be hashable: it needs __hash__ and __eq__, and objects that compare equal must hash equal. Mutable built-ins deliberately set __hash__ = None.

from collections import Counter, defaultdict, deque

d = {"b": 2, "a": 1, "c": 3}
print("insertion order kept:", list(d))

print("unhashable key:", end=" ")
try:
    {[1, 2]: "x"}
except TypeError as e:
    print(type(e).__name__, "-", e)

dq = deque([1, 2, 3])
dq.appendleft(0)                    # O(1) at both ends; list.insert(0, x) is O(n)
print("deque:", list(dq))

print("counter:", Counter("mississippi").most_common(3))

groups = defaultdict(list)
for word in ["idli", "dosa", "vada", "dhokla"]:
    groups[word[0]].append(word)
print("grouped:", dict(groups))

insertion order kept: ['b', 'a', 'c']
unhashable key: TypeError - unhashable type: 'list'
deque: [0, 1, 2, 3]
counter: [('i', 4), ('s', 4), ('p', 2)]
grouped: {'i': ['idli'], 'd': ['dosa', 'dhokla'], 'v': ['vada']}

defaultdict and Counter remove most hand-written grouping code, and deque is the correct structure for a queue or a sliding window — a replay buffer built on list.pop(0) is quadratic and this is a genuinely common bug in reinforcement-learning code.

Note that a dataclass with eq=True, frozen=True gets a generated __hash__, which makes it usable as a dictionary key. A plain class uses identity for both hash and equality, so two structurally identical instances are different keys.

Where these structures stop being appropriate#

The accidental quadratic is the dominant failure. A loop over n items that tests x in some_list of length n is O(n²). Converting the inner container to a set makes it O(n). This appears constantly in vocabulary filtering, deduplication and stop-word removal, and it is invisible on a test file of 200 rows.

The deeper limit is representational. Numerical work wants one dtype, contiguous memory and no per-element Python object. That is precisely what an ndarray provides and what a list of dictionaries cannot. The standard pipeline is therefore: parse JSON into lists of dicts, validate, then convert once into a DataFrame or an array and never touch per-element Python again.

For fixed-schema rows, dataclasses with slots=True or NamedTuple beat a dict on both memory and attribute-access cost, because they drop the per-instance dictionary. For sparse feature maps in classical ML, scipy.sparse beats both.

References#

• Hettinger, R. "Modern Python Dictionaries: A Confluence of a Dozen Great Ideas", PyCon US 2017.
• Peters, T. Objects/listsort.txt in the CPython source — the Timsort design note.
• PEP 456 — Secure and Interchangeable Hash Algorithm, Heimes, 2013.
• PEP 468 — Preserving the Order of **kwargs in a Function, Snow, 2014.
• PEP 372 — Adding an Ordered Dictionary to collections, Ronacher and Hettinger, 2008.
• Knuth, D. The Art of Computer Programming, Vol. 3, section 6.4 — open addressing and probe sequences.
• CPython source, Objects/listobject.c and Objects/dictobject.c.

What to learn next#

• Loops and conditions — the iterator protocol these containers implement.
• NumPy — contiguous buffers and why boxing costs so much.
• Pandas — columnar storage over those buffers.