Dictionaries and Hash Table Mechanics

Updated

September 7, 2026

Dictionaries and Hash Table Mechanics

After reading this chapter, you will master Python’s compact hash table implementation, understand open-addressing collision resolution and insertion-order preservation, execute non-destructive dictionary merges with |, leverage dynamic dictionary views, and avoid mutation-during-iteration errors.

Mental model

In CPython 3.6+, a dictionary (PyDictObject) uses a compact hash table layout consisting of two separate arrays: 1. Sparse Indices Array: An array of small integers (indices into the dense entries array) indexed by hash(key) % table_size. Empty slots contain -1. 2. Dense Entries Array: Stores entries in exact insertion order. Each row contains [hash_value, key_pointer, value_pointer].

CPython Compact Dictionary Architecture:
Key: "auth", hash("auth") % 8 = 1
Key: "api",  hash("api")  % 8 = 4

1. Sparse Indices Array (Table size: 8):
  Slot:     0    1    2    3    4    5    6    7
  Value: [ -1,   0,  -1,  -1,   1,  -1,  -1,  -1 ]
                 │              │
                 ▼              ▼
2. Dense Entries Array (Appended sequentially in insertion order):
  Index 0: [ 0x38fa, &"auth", &"http://auth.internal" ]
  Index 1: [ 0x7c12, &"api",  &"http://api.internal"  ]

Key Advantages

Memory Efficiency: The dense entries array stores 24 bytes per entry (hash, key*, value*) with zero wasted slots. The sparse array uses only 1 byte per slot for small dictionaries (int8_t). This saves 20%–25% memory compared to legacy sparse tables.
Deterministic Insertion Order: Because entries are appended to the dense array in the order they arrive, iterating over a dictionary always produces keys in insertion order.
Collision Handling: When two keys hash to the same sparse index, CPython uses open addressing with pseudo-random perturbation (index = (5*index + 1 + perturb) % size) to probe for the next available slot.

Minimal example

Save as dict_mechanics.py:

# dict_mechanics.py
def main() -> None:
    # 1. Dictionary creation and insertion-order preservation
    service_endpoints: dict[str, str] = {
        "auth": "http://10.0.1.10:8080",
        "orders": "http://10.0.1.20:8080",
        "billing": "http://10.0.1.30:8080",
    }

    # Insertion order is strictly preserved
    print("--- Service Endpoints (Insertion Order) ---")
    for service, url in service_endpoints.items():
        print(f"  {service:8} -> {url}")

    # 2. Modern Merge Operators (| and |= introduced in PEP 584)
    default_config = {"timeout": 30, "retries": 3, "debug": False}
    env_overrides  = {"debug": True, "log_level": "DEBUG"}

    # Non-destructive merge: right-hand keys override left-hand keys
    active_config = default_config | env_overrides
    print("\n--- Merged Configuration ---")
    print(f"  Default: {default_config}")
    print(f"  Active:  {active_config}")

    # In-place update with |=
    default_config |= {"retries": 5}
    print(f"  Updated in-place retries: {default_config['retries']}")

if __name__ == "__main__":
    main()

Run via uv run python dict_mechanics.py:

--- Service Endpoints (Insertion Order) ---
  auth     -> http://10.0.1.10:8080
  orders   -> http://10.0.1.20:8080
  billing  -> http://10.0.1.30:8080

--- Merged Configuration ---
  Default: {'timeout': 30, 'retries': 3, 'debug': False}
  Active:  {'timeout': 30, 'retries': 3, 'debug': True, 'log_level': 'DEBUG'}
  Updated in-place retries: 5

Worked examples

Case 1: Grouping with `.setdefault()` vs Explicit Checking

A common task in log and metrics aggregation is grouping values into lists keyed by an identifier. While checking if key not in d: requires two hash table lookups, .setdefault() handles the initialization in a single step:

# log_aggregator.py
def main() -> None:
    raw_events = [
        ("auth-svc", "User 'alice' logged in"),
        ("db-svc",   "Connection pool initialized"),
        ("auth-svc", "Token refresh granted"),
        ("api-svc",  "GET /health 200 OK"),
        ("auth-svc", "User 'bob' logged in"),
        ("db-svc",   "Query execution timeout"),
    ]

    # Group events by service name
    grouped_events: dict[str, list[str]] = {}
    for service, message in raw_events:
        # setdefault checks key: if absent, inserts empty list; returns existing or new list
        grouped_events.setdefault(service, []).append(message)

    print("--- Aggregated Service Events ---")
    for service, messages in grouped_events.items():
        print(f"Service [{service}] ({len(messages)} events):")
        for msg in messages:
            print(f"  - {msg}")

if __name__ == "__main__":
    main()

Run:

uv run python log_aggregator.py

Output:

--- Aggregated Service Events ---
Service [auth-svc] (3 events):
  - User 'alice' logged in
  - Token refresh granted
  - User 'bob' logged in
Service [db-svc] (2 events):
  - Connection pool initialized
  - Query execution timeout
Service [api-svc] (1 events):
  - GET /health 200 OK

Case 2: Multi-Layer Configuration Cascades with Dict Merges

Infrastructure applications typically load configuration from multiple hierarchical layers (Defaults \(\rightarrow\) File \(\rightarrow\) Environment \(\rightarrow\) CLI flags). Using the | operator cleanly implements precedence cascades:

# config_cascade.py
def resolve_app_config(
    cli_flags: dict[str, str | int],
    env_vars: dict[str, str | int],
) -> dict[str, str | int]:
    """Merge configuration layers in strict precedence order: defaults < env < cli."""
    base_defaults: dict[str, str | int] = {
        "bind_address": "0.0.0.0",
        "port": 8080,
        "workers": 4,
        "log_level": "INFO",
    }

    # Precedence: cli_flags overrides env_vars, which overrides base_defaults
    resolved = base_defaults | env_vars | cli_flags
    return resolved

def main() -> None:
    env = {"port": 9000, "log_level": "WARN"}
    cli = {"workers": 8}

    config = resolve_app_config(cli_flags=cli, env_vars=env)
    print("Resolved Hierarchical Configuration:")
    for key, value in sorted(config.items()):
        print(f"  {key:14} = {value}")

if __name__ == "__main__":
    main()

Run:

uv run python config_cascade.py

Output:

Resolved Hierarchical Configuration:
  bind_address   = 0.0.0.0
  log_level      = WARN
  port           = 9000
  workers        = 8

Case 3: Dynamic Dictionary Views vs Static Snapshots

The methods .keys(), .values(), and .items() do not return independent lists; they return dynamic view objects (dict_keys, dict_values, dict_items) that reflect underlying dictionary mutations in real time:

# dict_views.py
def main() -> None:
    inventory = {"nodes": 10, "cores": 64}

    # Obtain a view
    keys_view = inventory.keys()
    # Create a static snapshot by converting to list
    static_keys = list(inventory.keys())

    print(f"Initial keys view:   {list(keys_view)}")
    print(f"Static keys list:    {static_keys}")

    # Mutate the underlying dictionary
    inventory["memory_gb"] = 256

    print("\nAfter adding 'memory_gb':")
    # Dynamic view immediately reflects the change!
    print(f"Dynamic keys view:   {list(keys_view)}")
    # Static snapshot remains unchanged
    print(f"Static keys list:    {static_keys}")

if __name__ == "__main__":
    main()

Run:

uv run python dict_views.py

Output:

Initial keys view:   ['nodes', 'cores']
Static keys list:    ['nodes', 'cores']

After adding 'memory_gb':
Dynamic keys view:   ['nodes', 'cores', 'memory_gb']
Static keys list:    ['nodes', 'cores']

Pitfalls

Pitfall 1: Modifying a Dictionary During Iteration

CPython tracks dictionary version counters. If you add or delete keys from a dictionary while iterating over it, CPython detects the structural modification and raises RuntimeError:

# THE TRAP:
metrics = {"cpu": 95, "disk": 40, "ram": 85, "network": 10}

try:
    for key in metrics:
        if metrics[key] < 50:
            del metrics[key]  # BUG: Structural mutation during iteration!
except RuntimeError as err:
    print(f"Caught expected crash: {err}")

Output:

Caught expected crash: dictionary changed size during iteration

# THE FIX: Iterate over a list snapshot of the keys
metrics = {"cpu": 95, "disk": 40, "ram": 85, "network": 10}
for key in list(metrics.keys()):
    if metrics[key] < 50:
        del metrics[key]

print(f"Cleaned metrics: {metrics}")  # {'cpu': 95, 'ram': 85}

Pitfall 2: Direct Subscripting on Optional Keys (`KeyError`)

Accessing a missing key via d[key] raises KeyError. Always distinguish between mandatory keys and optional defaults:

# THE TRAP:
params = {"host": "localhost"}
# port = params["port"]  # KeyError: 'port'

# THE FIX: Use .get() with an explicit default
port = params.get("port", 8080)
print(f"Resolved port: {port}")  # 8080

Pitfall 3: Mutable Objects as Dictionary Keys

A dictionary key must be hashable. Trying to use a list, set, or another dictionary as a key raises TypeError:

# THE TRAP:
try:
    bad_dict = {[1, 2]: "invalid"}
except TypeError as err:
    print(f"Invalid key error: {err}")  # TypeError: unhashable type: 'list'

# THE FIX: Convert mutable sequences to immutable tuples
good_dict = {(1, 2): "valid"}
print(f"Valid tuple key lookup: {good_dict[(1, 2)]}")

Exercises

Construct a frequency map from a list of status codes [200, 404, 200, 500, 200, 404] using a standard dictionary and .get().
Given two dictionaries primary and fallback, use the | operator to create an active configuration where primary values take precedence over fallback.
Demonstrate the RuntimeError: dictionary changed size during iteration exception by attempting to delete keys with values below 0 inside a for k in d: loop.
Implement an inverted dictionary function that swaps keys and values, raising ValueError if duplicate values are detected.
Benchmark the execution time of looking up 100,000 random integers in a list of 10,000 integers vs a dictionary containing the same 10,000 keys.

Dictionaries and Hash Table Mechanics

Mental model

Key Advantages

Minimal example

Worked examples

Case 1: Grouping with .setdefault() vs Explicit Checking

Case 2: Multi-Layer Configuration Cascades with Dict Merges

Case 3: Dynamic Dictionary Views vs Static Snapshots

Pitfalls

Pitfall 1: Modifying a Dictionary During Iteration

Pitfall 2: Direct Subscripting on Optional Keys (KeyError)

Pitfall 3: Mutable Objects as Dictionary Keys

Exercises

Further reading

Case 1: Grouping with `.setdefault()` vs Explicit Checking

Pitfall 2: Direct Subscripting on Optional Keys (`KeyError`)