Python's dictionary is so convenient that it can disappear from view. Namespaces are dictionaries. Objects often keep attributes in dictionaries. JSON objects become dictionaries. Caches, indexes, counters, registries, and configuration all lean on the same syntax:

Pyodide / WebAssembly
language = {"name": "Python", "year": 1991}
language["creator"] = "Guido van Rossum"

print("[result] language name:", language["name"])
print("[check] year key exists:", "year" in language)

That simple interface hides several distinct jobs. A dictionary must turn arbitrary immutable keys into search locations, survive collisions, grow without making every insertion expensive, preserve insertion order, and avoid wasting too much memory while doing it.

This tutorial builds a model in layers. We will start with behavior guaranteed by Python, inspect what CPython 3.14 does underneath, and finish with the choices that should affect production code.

Version note. The examples are written for Python 3.10 through 3.14 and were verified on CPython 3.14. Memory sizes and table layout are CPython implementation details. They can differ by version, build, architecture, and Python implementation.

First surprise: a hash is not an identity

What should this print?

Pyodide / WebAssembly
class Collision:
    def __init__(self, label):
        self.label = label

    def __hash__(self):
        return 42

    def __eq__(self, other):
        return isinstance(other, Collision) and self.label == other.label


left = Collision("left")
right = Collision("right")
mapping = {left: "L", right: "R"}

print("[check] colliding key hashes:", hash(left), hash(right))
print("[result] distinct collision entries:", len(mapping), mapping[left], mapping[right])

The result is:

42 42
2 L R

Both keys return the same hash, yet both remain in the dictionary. This is not an edge case Python reluctantly tolerates. A hash table is designed around the fact that the set of possible objects is much larger than the set of possible hash values. Collisions are inevitable.

The useful model is:

  1. Python computes the key's hash.
  2. The dictionary uses bits from that hash to choose a place to begin searching.
  3. If the candidate slot belongs to a different key, the dictionary continues through a probe sequence.
  4. A matching hash narrows the search; identity or equality confirms the key.

Python guarantee. Objects that compare equal must have the same hash value if they are hashable. Different objects are allowed to share a hash. The reverse implication does not hold: equal hashes do not imply equal objects.

This is why a hash is better understood as a routing hint than a fingerprint. It gets the search into the right neighborhood. Equality determines whether Python has reached the right house.

The contract your keys must keep

Most built-in immutable values already satisfy the hash contract. Strings, bytes, integers, and tuples of hashable values are common dictionary keys. Lists and dictionaries are mutable and therefore unhashable.

Custom classes need more care. If you define equality but do not define a compatible hash, Python normally makes instances unhashable:

Pyodide / WebAssembly
class Coordinate:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __eq__(self, other):
        return (
            isinstance(other, Coordinate)
            and (self.x, self.y) == (other.x, other.y)
        )


print("[check] Coordinate hash implementation:", Coordinate.__hash__)
# None

That default protects you from a dangerous class of bugs. A dictionary assumes that a key's hash will not change while the key is stored. Break that assumption and the object can become unreachable even though it is visibly still inside the dictionary.

class BadKey:
    def __init__(self, value):
        self.value = value

    def __hash__(self):
        return hash(self.value)

    def __eq__(self, other):
        return isinstance(other, BadKey) and self.value == other.value


key = BadKey("draft")
mapping = {key: "saved"}

key.value = "published"

print(key in mapping)       # usually False
print(list(mapping.keys())) # the object is still there

The exact accidental outcome can depend on table state and hash values, which makes the bug worse, not better. The dictionary placed key using the hash of "draft". Lookup after mutation starts from the hash of "published" and follows a different route.

Prefer immutable key objects. A frozen data class expresses that intent directly:

from dataclasses import dataclass


@dataclass(frozen=True)
class Coordinate:
    x: int
    y: int


prices = {Coordinate(4, 7): 12.50}
assert prices[Coordinate(4, 7)] == 12.50

The generated equality and hash use the same fields, and frozen instances prevent ordinary field reassignment.

From hash to candidate slot

A simplified hash table often appears as one large row of slots. To find a key, take its hash modulo the table size and inspect that position. Real CPython dictionaries are more sophisticated, but one piece of that model remains useful.

CPython keeps table sizes as powers of two. A bit mask can therefore select an initial index efficiently:

table_size = 8
mask = table_size - 1

for hash_value in (5, 13, 21):
    print(hash_value, hash_value & mask)

All three values begin at index 5 because their low bits match. CPython then mixes in more of the hash while probing, rather than walking only to the immediately adjacent slot. The real recurrence is an implementation detail; the durable point is that lookup can visit several candidates and still remain constant-time on average.

Worst-case lookup is linear in the number of entries. Average-case lookup is fast because hashes are expected to distribute keys well and because the table keeps unused space. Big-O notation does not promise that every individual operation takes the same amount of time.

Python also randomizes hashes for strings and bytes between interpreter processes by default. You can observe it by launching Python twice:

python -c 'print(hash("python-deepcuts"))'
python -c 'print(hash("python-deepcuts"))'

The values will usually differ. Never persist hash() output as a stable identifier, shard assignment, cache key shared between processes, or file format. Use a specified digest when stability is part of the requirement.

Security note. Hash randomization helps make collision-based denial-of-service attacks harder. It is not cryptographic hashing and does not make hash() suitable for passwords or integrity checks.

CPython stores an index and an entry array

Calling a modern CPython dictionary "an array of key/value slots" misses the design that made it compact and ordered. CPython separates two concerns:

sparse index table                 compact entry array
+----+----+----+----+----+        +-----------------------+
|  1 |  . |  0 |  . |  2 | ----> | hash | key | value    |  entry 0
+----+----+----+----+----+        +-----------------------+
                                  | hash | key | value    |  entry 1
`.` means empty                   +-----------------------+
numbers point into entries        | hash | key | value    |  entry 2
                                  +-----------------------+

The sparse dk_indices table supports fast lookup. Its cells contain small integer indexes, or markers for empty and previously occupied positions. The dense dk_entries array holds hashes, keys, and values for a normal combined dictionary.

This separation matters for memory locality. The sparse part does not need to repeat full object pointers and hash values in every unused slot. CPython can also choose a smaller integer width for indexes in small dictionaries and widen it as a table grows.

CPython detail. These names and layouts describe CPython 3.14's PyDictKeysObject. They are not part of Python's public API. PyPy or a future CPython release may preserve dictionary behavior with a different representation.

Why insertion order became cheap

For a combined table, CPython mostly appends new items to the dense entry array. Iteration can walk that compact array in insertion order instead of scanning sparse slots. A memory optimization produced fast, predictable iteration.

The historical sequence is worth keeping straight:

  • CPython 3.6 introduced its compact ordered dictionary as an implementation detail.
  • Python 3.7 made insertion ordering a language guarantee for dictionaries.
  • Updating an existing key does not move it.
  • Deleting and reinserting a key places it at the end.
Pyodide / WebAssembly
steps = {"parse": 1, "validate": 2, "store": 3}
steps["validate"] = 20
print("[result] order after value update:", list(steps))

del steps["validate"]
steps["validate"] = 2
print("[result] order after delete and reinsert:", list(steps))

['parse', 'validate', 'store']
['parse', 'store', 'validate']

Order is now safe to rely on when order means insertion order. It does not mean sorted order. Two dictionaries with the same key/value pairs compare equal even if their insertion orders differ.

collections.OrderedDict still has distinct semantics. It supports efficient reordering operations such as move_to_end(), and equality between two OrderedDict instances is order-sensitive. Use it when rearrangement or order-sensitive equality is part of the model, not merely because you need stable iteration.

Deletion leaves a trail

Open-addressed hash tables cannot always turn a deleted slot directly into an ordinary empty slot. A lookup for a colliding key may need to probe through that position. If deletion ended the search prematurely, an existing key farther along the probe sequence could disappear.

CPython therefore has a deleted marker, called a dummy slot in its source. Lookup knows to continue past it. A later resize can rebuild the table without those markers.

You should not manage dummy slots yourself or schedule ritual dictionary copies. The implementation already rebuilds tables as needed. The practical consequences are narrower:

  • deletion does not promise that process memory will immediately fall;
  • a delete/reinsert changes insertion order;
  • mutation during iteration is unsafe and can raise RuntimeError;
  • retaining a huge, mostly emptied dictionary may retain more storage than constructing the small dictionary you actually need.

Growth happens in steps

A dictionary keeps spare capacity so that insertion usually finds an empty slot quickly. Occasionally an insertion triggers allocation and rebuilding. That expensive operation is spread across many cheap insertions, producing amortized constant-time behavior.

We can observe the steps without reaching into private structures:

import sys


mapping = {}
previous = None

for count in range(65):
    if count:
        mapping[count] = None

    shallow_bytes = sys.getsizeof(mapping)
    if shallow_bytes != previous:
        print(f"{count:>2} entries -> {shallow_bytes:>4} bytes")
        previous = shallow_bytes

On 64-bit CPython 3.14.7 in our test environment, this printed:

 0 entries ->   64 bytes
 1 entries ->  224 bytes
 6 entries ->  352 bytes
11 entries ->  632 bytes
22 entries -> 1168 bytes
43 entries -> 2264 bytes

Do not memorize these thresholds. They are evidence of stepped growth, not a portable sizing table. Python version, architecture, build configuration, and key shape can change the numbers.

sys.getsizeof() is shallow: it reports the dictionary object's directly allocated storage, not the recursive size of every referenced key and value. If ten dictionaries point at the same large object, adding that object's size ten times would be wrong. Serious memory investigation needs a clearly defined ownership model and often tracemalloc or a specialized heap tool.

Instance dictionaries can share their shape

Consider ten thousand instances of the same ordinary class. Their attribute dictionaries usually repeat the same names: x and y. Since Python 3.3, CPython can use a split-table representation in which those dictionaries share keys while each instance keeps its own values.

import sys


class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y


points = [Point(i, i) for i in range(10_000)]
standalone = [{"x": i, "y": i} for i in range(10_000)]

instance_bytes = sum(sys.getsizeof(p.__dict__) for p in points)
standalone_bytes = sum(sys.getsizeof(d) for d in standalone)

print(instance_bytes)
print(standalone_bytes)

Our CPython 3.14.7 run reported 880000 shallow bytes for the instance dictionaries and 1840000 for standalone dictionaries. This is not a universal class-versus-dictionary benchmark: it counts only shallow dictionary storage and ignores the Point objects themselves. It demonstrates the optimization PEP 412 introduced: many similarly shaped instances can avoid storing an independent copy of the key layout.

This also explains why "an object's __dict__ is just a normal dictionary" is behaviorally useful but implementation-wise incomplete.

If instance footprint genuinely matters, measure the complete alternatives under a representative workload. Slotted classes, data classes with slots=True, tuples, and packed arrays all trade away different capabilities. A smaller shallow size alone does not choose the right data model.

Dictionary comprehensions and duplicate keys

Construction order and key equality interact in a way that is easy to overlook. If a later item produces a key equal to an earlier one, the later value wins while the original key position remains:

Pyodide / WebAssembly
pairs = [("alpha", 1), ("beta", 2), ("alpha", 3)]
mapping = {key: value for key, value in pairs}

print("[result] mapping after duplicate key:", mapping)
# {'alpha': 3, 'beta': 2}

The update changes the value attached to the existing entry; it does not count as deleting and reinserting the key. The same principle applies to dictionary literals with duplicate keys, although duplicate literal keys are usually a mistake worth catching in review or linting.

One particularly Python-shaped consequence comes from numeric equality:

Pyodide / WebAssembly
mapping = {True: "boolean", 1: "integer", 1.0: "float"}
print("[result] equal numeric keys collapse to:", mapping)
# {True: 'float'}

True, 1, and 1.0 compare equal and have equal hashes, so they describe one dictionary key. The first inserted key object remains visible while each assignment replaces its value. This follows the language's equality and hashing rules, not a special dictionary conversion.

Choosing keys that make good systems

Correctness comes before cleverness. A good dictionary key has stable value semantics that match the lookup you intend.

  • Use immutable built-ins for straightforward identifiers.
  • Use frozen data classes or named tuples for composite domain keys.
  • Keep __eq__ and __hash__ based on the same immutable state.
  • Do not persist or transmit hash() values.
  • Avoid keys whose equality is expensive; collisions may invoke it repeatedly.
  • Remember that holding a key in a dictionary keeps a strong reference to it.
  • Use weakref.WeakKeyDictionary only when key lifetime, not value equality alone, should control entry lifetime.

For caches, the key design is often more important than the cache implementation. A key that accidentally includes a timestamp destroys reuse. A key that omits permissions can return data across security boundaries. A mutable key can make invalidation impossible. Hash-table speed cannot rescue incorrect identity semantics.

When a dictionary is the wrong structure

A dictionary is excellent for mapping unique hashable keys to values. That does not make it the default answer to every collection problem.

  • Need values in sorted-key order? Sort at presentation time, or use a purpose-built sorted mapping if updates and ordered queries dominate.
  • Need repeated values counted? collections.Counter communicates the operation directly.
  • Need a fixed record shape? A data class or typed record makes fields explicit.
  • Need a queue from both ends? Use collections.deque.
  • Need dense numeric storage? Use an array-oriented representation rather than millions of boxed objects in a mapping.
  • Need membership for a tiny collection? A list or tuple may be simpler and can be faster before hash-table setup pays off. Measure the real workload.

The deepest optimization lesson is not a load factor or probing formula. It is to choose a structure whose semantics remove work from the system.

Exercises: test the model

  1. Create two unequal objects with the same constant hash. Instrument __eq__ with a print statement and observe when dictionary construction and lookup call it.
  2. Build a frozen composite key for (tenant_id, resource_id). Explain why both fields belong in equality and hashing.
  3. Predict the order after updating, deleting, and reinserting several keys. Run the code only after writing your prediction.
  4. Repeat the growth experiment on another Python version or implementation. Record the environment and explain which conclusion remains portable.
  5. Compare shallow storage for ordinary instances, slotted instances, and standalone dictionaries. List everything your measurement excludes before drawing a conclusion.

Keep this model

A dictionary is not a magical constant-time box, and a hash is not an address. Python asks a key for a stable hash, uses that hash to navigate a sparse search structure, and confirms candidates through identity or equality. CPython stores compact entries separately from sparse indexes, which reduces wasted space and makes insertion-order iteration natural.

That model is detailed enough to explain collisions, mutable-key failures, ordered iteration, stepped growth, deleted slots, and shared instance shapes. It is also restrained enough not to turn CPython's current constants into false language promises.

When dictionary behavior surprises you, ask three questions:

  1. What are this key's equality and hash semantics?
  2. Is the behavior guaranteed by Python or supplied by this implementation?
  3. Am I measuring the structure I think I am measuring?

Those questions travel farther than any memorized table diagram.

Primary sources