Introduction

Python dictionaries are hash tables optimized for fast average lookup, insertion, and deletion. The speed comes from computing a hash of the key, mapping that hash to an internal slot, and resolving collisions efficiently. Understanding this model helps explain performance behavior, key requirements, and common bugs with mutable keys.

Core Sections

Hash and equality decide key identity

A dictionary lookup computes hash(key) and then probes table slots. If hashes match, Python confirms key equality with == before returning a value.

d = {"apple": 10, "banana": 20}
print(hash("apple"))
print(d["apple"])

Two different keys can share a hash, so equality checks are essential for correctness.

Collision handling with open addressing

Python uses open addressing and a probing sequence to find free or matching slots. In average cases this remains close to constant time. In heavy collision scenarios, probe length grows and performance degrades.

You usually do not need to manage this directly, but it explains why dictionary operations are average O one and not guaranteed constant in worst-case adversarial data patterns.

Why keys must be hashable and stable

Dictionary keys must have a stable hash and stable equality semantics while in the dictionary. Immutable built-in types like strings, integers, and tuples of immutables are safe.

d = {}
d[("user", 42)] = "ok"
print(d[("user", 42)])

Lists are unhashable because their contents can change.

# d[[1, 2, 3]] = "bad"  # TypeError

Custom class keys

Custom objects can be keys if they define consistent __hash__ and __eq__ behavior.

1class UserKey:
2    def __init__(self, user_id: int):
3        self.user_id = user_id
4
5    def __hash__(self):
6        return hash(self.user_id)
7
8    def __eq__(self, other):
9        return isinstance(other, UserKey) and self.user_id == other.user_id
10
11
12d = {UserKey(1): "alice"}
13print(d[UserKey(1)])

If hash and equality disagree, lookups may fail unexpectedly.

Resizing and performance behavior

As dictionaries grow, Python resizes internal storage to keep load factors healthy. Resizing has occasional cost spikes, but amortized performance remains very good for most workloads. This is why bulk insert benchmarks may show periodic jumps.

For high-throughput code, prefer direct membership checks and avoid repeated failed lookups that recompute expensive keys. If key computation itself is costly, cache normalized keys before dictionary access.

Security note and randomized hashing

Python uses hash randomization for some key types, helping protect against certain collision attacks in untrusted-input scenarios. This means hash values can differ across process runs. Do not persist raw hash values as stable identifiers.

Practical performance habits

Dictionary speed depends on key design as much as table internals. Normalize keys once at ingestion, not on every lookup. For example, if lookups are case-insensitive, call casefold once and store normalized keys. This removes repeated string work from hot paths.

1store = {}
2for raw_key, value in [("UserA", 1), ("userb", 2)]:
3    store[raw_key.casefold()] = value
4
5print(store.get("USERA".casefold()))

For large in-memory datasets, measure memory and CPU together. A faster lookup structure is not always better if it dramatically increases memory pressure and triggers more garbage collection overhead.

Keep key schemas simple and documented so lookup behavior stays predictable as code evolves.

Common Pitfalls

• Using mutable objects as keys or mutating key state after insertion.
• Implementing __eq__ without a compatible __hash__ in custom classes.
• Assuming dictionary order implies hash order semantics.
• Persisting hash output and expecting cross-run stability.
• Treating average O one behavior as guaranteed worst-case constant time.

Summary

• Dictionary lookup uses hash first, then equality checks for final key match.
• Hashable and stable keys are required for reliable dictionary behavior.
• Collision handling and resizing keep average performance fast.
• Custom key classes must maintain hash and equality consistency.
• Understand internal behavior to avoid subtle correctness and performance bugs.