Dictionaries: Hash Tables in Practice

Fast lookups by key

A dict is a hash table: each key's hash() chooses a slot, so lookup, insertion and deletion are O(1) on average. CPython uses open addressing with a compact layout: a sparse index table pointing into a dense array of entries, which saves memory and preserves insertion order, guaranteed by the language since Python 3.7. Tables resize when about two-thirds full, so inserts are amortised O(1). Worst-case operations are O(n) if many keys collide, which is why string hashing is randomised per process (hash randomisation) to resist collision attacks. Keys must be hashable: an object's hash must not change during its lifetime, and objects that compare equal must have equal hashes. When you define __eq__ on a class, also define __hash__ (or make it unhashable), and never mutate a key in a way that changes its hash. Useful operations: get(key, default), setdefault, pop, items() views, dict comprehensions, merging with | and |= (Python 3.9+), and dict.fromkeys. Dict views (keys(), items()) are live and support set operations.

A compact hash table

A sparse index array points into a dense, insertion-ordered entries array.

Counting, grouping and the hash contract

Dicts as indexes, and a class that is safe to use as a key.

orders = [
    {"id": "o1", "city": "Pune", "total": 1200},
    {"id": "o2", "city": "Delhi", "total": 300},
    {"id": "o3", "city": "Pune", "total": 800},
]

by_id = {o["id"]: o for o in orders}           # index for O(1) lookups
print(by_id["o3"]["total"])                     # 800

revenue = {}
for o in orders:
    revenue[o["city"]] = revenue.get(o["city"], 0) + o["total"]
print(revenue)                                  # {'Pune': 2000, 'Delhi': 300} (insertion order)

defaults = {"currency": "INR", "gst": 18}
overrides = {"gst": 5}
print(defaults | overrides)                     # {'currency': 'INR', 'gst': 5}

class Sku:
    def __init__(self, code: str):
        self.code = code.upper()
    def __eq__(self, other):
        return isinstance(other, Sku) and self.code == other.code
    def __hash__(self):                         # equal objects must hash equally
        return hash(self.code)

stock = {Sku("pen"): 120}
print(stock[Sku("PEN")])                        # 120: equal key, same hash

print(revenue.keys() & {"Pune", "Mumbai"})      # {'Pune'}: views support set operations

Do not mutate keys

If a key object's hash changes after insertion, the dict looks in the wrong slot and the entry becomes unreachable. Use immutable keys (strings, numbers, tuples, frozen dataclasses).

Quick check: Since which Python version is dict insertion order guaranteed by the language?

• 3.7
• 2.7
• 3.5
• 3.12