Dictionaries Basic & Hash Table Mechanics
Master hash collisions, view objects, mutation traps, shallow vs deep copying, and dictionary comprehension scope.
Theoretical Mechanics & Memory Architecture
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.
Interactive Dry-Run Execution Workspace
Hash Collision: Bool, Int, and Float Keys
Trace CPython execution step-by-step and deduce the exact stdout string emitted by this snippet.
d = {True: 'a', 1: 'b', 1.0: 'c'}
print(len(d), d[1])Frequently Asked Questions on 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.