Dictionaries Basic & Hash Table Mechanics Practice & CPython Execution Tracing
Master hash collisions, view objects, mutation traps, shallow vs deep copying, and dictionary comprehension scope.
CPython Runtime Semantics: Dictionaries Basic & Hash Table Mechanics
Since Python 3.6 (standardized in PEP 468), CPython dictionaries (PyDictObject) utilize a compact, insertion-ordered hash table architecture. Storage is decoupled into a sparse integer hash indices table and a dense array of entries containing the cached hash code, key pointer, and value pointer. Hash collisions are resolved via open addressing with pseudo-random perturbation (perturb >>= 5), avoiding clustering and guaranteeing O(1) average lookup latency.
When searching for a key, CPython hashes the key and masks it with the table size to determine an initial index in the sparse indices table. If a collision occurs, probing calculates i = (5 * i + 1 + perturb) & mask. When the table's load factor exceeds 2/3, CPython resizes the hash table, doubling capacity and re-indexing the dense entry array.
CPython maintains a version counter (ma_version_tag) on each PyDictObject. Inserting or deleting keys during iteration increments this tag, causing the dictionary iterator to raise RuntimeError: dictionary changed size during iteration. Additionally, mutable objects (like lists or sets) cannot serve as dictionary keys because they do not implement immutable hash contracts.
Worked Dictionaries Basic & Hash Table Mechanics Trace Walkthroughs
Before launching the interactive sandbox, study these worked execution traces. Predict the state mutation for every instruction, then inspect the line-by-line execution table to understand why CPython produces each result.
Walkthrough 1: Hash Collision: Bool, Int, and Float Keys
Difficulty: hardd = {True: 'a', 1: 'b', 1.0: 'c'}
print(len(d), d[1])1 cTrue, 1, and 1.0 are considered identical keys in a hash table. The dictionary processes them in order, overwriting the value each time. The final value for this single key is 'c'. The length is 1.
Walkthrough 2: The dict.fromkeys() Mutable Default Trap
Difficulty: hardd = dict.fromkeys(['a', 'b'], [])
d['a'].append(1)
print(d){'a': [1], 'b': [1]}The empty list [] is evaluated once. Both 'a' and 'b' point to this exact same list in memory. Appending 1 to 'a' modifies the shared list, so 'b' reflects the change.
Walkthrough 3: Dictionary View Objects Reflect Changes
Difficulty: mediumd = {'a': 1}
keys = d.keys()
d['b'] = 2
print('b' in keys, list(keys))True ['a', 'b']The view object maintains a live link to the dictionary's internal hash table. Adding 'b' to the dictionary makes it instantly visible in the 'keys' view.
Static Problem Bank & Code Walkthrough Preview
The following 8 real problems evaluate core Dictionaries Basic & Hash Table Mechanics execution behaviors directly from our CPython test suite. Trace each code snippet manually, predict the terminal output, and compare your mental model with the verified output and technical explanation before testing variations in the interactive workspace.
Basic Expression Completion
# Complete expression so result equals the sum of x and y (15)
x = 5
y = 10
result = ___
print(result)x + yx + y evaluates to 15, which is stored in result and printed.
Insertion Order After Deletion (Python 3.7+)
d = {'a': 1, 'b': 2, 'c': 3}
del d['b']
d['b'] = 4
print(list(d.keys()))['a', 'c', 'b']The initial order is a, b, c. Deleting 'b' leaves a, c. Reinserting 'b' places it at the end of the insertion sequence, resulting in a, c, b.
setdefault() Return Value and Side Effects
d = {}
res = d.setdefault('k', []).append(1)
print(res, d)None {'k': [1]}d.setdefault('k', []) inserts and returns the empty list. .append(1) modifies that list to [1] but evaluates to None. Thus, res is None, and d contains {'k': [1]}.
Check if a String is a Palindrome
# Problem: Determine if a string reads the same forwards and backwards
# Ignore case and non-alphanumeric characters
def is_palindrome(s):
"""
Check if a string is a palindrome.
Args:
s: Input string
Returns:
bool: True if palindrome, False otherwise
"""
# Your implementation heredef is_palindrome(s):
cleaned = ''.join(c.lower() for c in s if c.isalnum())
return cleaned == cleaned[::-1]Clean the string by keeping only alphanumeric chars in lowercase, then compare with its reverse.
Dictionary Unpacking Collision Resolution
d1 = {'a': 1, 'b': 2}
d2 = {'b': 3, 'c': 4}
print({**d1, **d2}){'a': 1, 'b': 3, 'c': 4}d1 is unpacked first, then d2. The key 'b' exists in both. The value from d2 (3) overwrites the value from d1 (2).
Set Operations on Dictionary Views
d1 = {'a': 1, 'b': 2, 'c': 3}
d2 = {'b': 2, 'c': 9, 'd': 4}
print(d1.keys() & d2.keys())
print(d1.items() & d2.items()){'c', 'b'}
{('b', 2)}The intersection of keys is {'b', 'c'}. The intersection of items requires both key and value to match. Only ('b', 2) matches, as 'c' has different values (3 vs 9).
Dict insertion order preservation
d = {}
d['z'] = 1
d['a'] = 2
d['m'] = 3
print(list(d.keys()))['z', 'a', 'm']In Python 3.7+, dictionaries maintain insertion order. The keys are added in the sequence 'z', 'a', 'm', and this order is preserved when calling d.keys(). The list() constructor converts the view object to a list while maintaining the original insertion order.
The get() Truthiness Trap vs 'in' Operator
d = {'a': 0, 'b': False, 'c': None}
print(bool(d.get('a')))
print('c' in d)
print(bool(d.get('c')))False True False
d.get('a') returns 0, which is falsy. 'c' is in d, so 'in' returns True. d.get('c') returns None, which is falsy. Using 'if d.get(key):' is a common bug when valid values can be falsy.
How to use this tool
Study the verified Dictionaries Basic & Hash Table Mechanics worked examples above, predict the variable mutations and output on paper, then run variations in the interactive workspace below.
Worked example
# Quick verification check for Dictionaries Basic & Hash Table Mechanics x = 10 y = x print(x, y)
Static result: 10 10
Controls
Review the test snippet in the editor, click Run to execute in the local Pyodide sandbox, and inspect the stdout console and state changes below.
Honest limits
Exercises for Dictionaries Basic & Hash Table Mechanics run client-side via WebAssembly (Pyodide). Standard library features are supported; GUI and external network calls are disabled for sandboxing.
Continue with the Python Mastery Hub.
Interactive Dry-Run Execution Workspace
Floating Point Precision in Key Lookup
Trace CPython execution step-by-step and deduce the exact stdout string emitted by this snippet.
d = {1.1 + 2.2: 'x'}
print(d.get(3.3))CPython Dictionary Iteration & Mutation Pitfalls
Understand hash table sizing, load factor thresholds, and why mutating dictionary keys during iteration triggers runtime size-change exceptions.
Frequently Asked Questions: Dictionaries Basic & Hash Table Mechanics
How did Python 3.6+ reduce dictionary memory consumption by 20% to 25%?
Traditional hash tables stored 24-byte entries (hash, key, value) directly in a sparse table with empty slots. The compact layout uses a small sparse array of 1-byte or 2-byte integers pointing into a dense entries array, eliminating empty 24-byte bucket overhead.
Why can a tuple containing a list NOT be used as a dictionary key?
Although tuples are immutable containers, hashability requires all contained elements to be immutable and hashable. If a tuple contains a mutable list, computing an invariant hash is impossible, raising TypeError: unhashable type: 'list'.
What is the difference between dict.get(key, default) and dict.setdefault(key, default)?
dict.get() retrieves the value without modifying the dictionary. dict.setdefault() checks if the key exists: if present, it returns the current value; if absent, it inserts the key bound to default into the dictionary and returns default.