Dictionary and Container Objects

Relevant source files

• Doc/c-api/dict.rst
• Doc/c-api/object.rst
• Doc/c-api/refcounting.rst
• Doc/library/io.rst
• Doc/library/site.rst
• Include/cpython/dictobject.h
• Include/cpython/object.h
• Include/internal/pycore_dict.h
• Include/internal/pycore_object.h
• Include/internal/pycore_setobject.h
• Include/internal/pycore_typeobject.h
• Lib/test/mapping_tests.py
• Lib/test/test_capi/test_object.py
• Lib/test/test_dict.py
• Lib/test/test_free_threading/test_set.py
• Lib/test/test_set.py
• Modules/_testcapi/object.c
• Objects/clinic/setobject.c.h
• Objects/dictobject.c
• Objects/object.c
• Objects/setobject.c
• Objects/typeobject.c
• Tools/c-analyzer/cpython/ignored.tsv

Purpose and Scope

This page describes the internal implementation of Python's dictionary (dict) and set container types (set, frozenset), including their hash table structures, memory layouts, and optimization strategies. For information about the base object system and type hierarchy, see PyObject and Type System. For memory management and reference counting details, see Reference Counting and Garbage Collection.

Overview

CPython's dictionary and set implementations are built on compact hash tables. Since Python 3.6, dictionaries maintain insertion order while providing O(1) average-case lookup performance. Both dictionaries and sets use open addressing with linear probing for collision resolution.

Key Implementation Files:

• Objects/dictobject.c - Dictionary implementation
• Objects/setobject.c - Set and frozenset implementation
• Include/internal/pycore_dict.h - Internal dictionary structures

Dictionary Architecture

Core Data Structures

Sources: Objects/dictobject.c9-106 Include/cpython/dictobject.h11-33 Include/internal/pycore_dict.h75-85

The dictionary implementation separates hash table management (PyDictKeysObject) from the top-level dictionary object (PyDictObject). This enables key sharing between multiple dictionary instances.

Dictionary Object (PyDictObject):

Field	Type	Purpose
ma_used	Py_ssize_t	Number of active entries in the dictionary
ma_keys	PyDictKeysObject*	Pointer to the keys object (hash table)
ma_values	PyDictValues*	Pointer to values array (NULL for combined tables)
_ma_watcher_tag	uint64_t	Dict watchers, mutation counter, and unique ID

Sources: Include/cpython/dictobject.h11-33

Keys Object (PyDictKeysObject):

Field	Type	Purpose
dk_refcnt	Py_ssize_t	Reference count for key sharing
dk_log2_size	uint8_t	Log2 of hash table size
dk_log2_index_bytes	uint8_t	Log2 of index size in bytes
dk_kind	uint8_t	Kind: GENERAL, UNICODE, or SPLIT
dk_version	uint32_t	Version for cache invalidation
dk_usable	Py_ssize_t	Number of usable slots remaining
dk_nentries	Py_ssize_t	Number of entries currently used
dk_indices[]	variable	Hash table (int8/16/32/64 based on size)

Sources: Include/internal/pycore_dict.h175-219

Dictionary Kinds and Table Types

Sources: Objects/dictobject.c54-89 Include/internal/pycore_dict.h168-172

Combined Tables:

• Both keys and values stored in the dk_entries array within PyDictKeysObject
• Used when dictionary is not shared or contains non-unicode keys
• Reference count (dk_refcnt) is always 1

Split Tables:

• Keys stored in shared PyDictKeysObject (can have dk_refcnt > 1)
• Values stored in separate PyDictValues array pointed to by ma_values
• Only supports unicode keys (DICT_KEYS_UNICODE or DICT_KEYS_SPLIT)
• Used for instance dictionaries to share keys across objects of the same class
• Maximum 30 keys (SHARED_KEYS_MAX_SIZE)

Sources: Objects/dictobject.c54-65 Include/internal/pycore_dict.h222-223

Compact Hash Table Layout

Sources: Objects/dictobject.c9-50 Objects/dictobject.c786-838

The compact design (introduced in Python 3.6) separates the hash table indices from the actual key-value entries:

1. dk_indices[]: Sparse hash table that maps hash values to entry indices

   • Size is always a power of 2: 2^dk_log2_size
   • Index type depends on table size (8/16/32/64-bit integers)
   • Contains DKIX_EMPTY (-1), DKIX_DUMMY (-2), or valid indices >= 0

2. dk_entries[]: Dense array of actual entries

   • Size is USABLE_FRACTION(dk_size) where USABLE_FRACTION(n) = (n * 2) / 3
   • Entries are append-only, preserving insertion order
   • Contains PyDictKeyEntry (general) or PyDictUnicodeEntry (unicode keys)

Sources: Objects/dictobject.c33-50 Objects/dictobject.c507-558

Hash Table Probing

Sources: Objects/dictobject.c320-412 Objects/dictobject.c220-248

Probing Algorithm:

1. Initial probe: i = hash(key) & mask where mask = size - 1
2. Linear probing: Check up to 9 consecutive slots for cache locality
3. Perturbation: Use upper bits of hash to jump to different table regions
   • Formula: i = ((5*i) + 1 + perturb) & mask where perturb >>= PERTURB_SHIFT
   • PERTURB_SHIFT = 5

This hybrid approach combines:

• Linear probing: Fast for consecutive keys, good cache performance
• Randomized probing: Breaks up collision chains, uses all hash bits

Sources: Objects/dictobject.c320-412

Dictionary Operations

Sources: Objects/dictobject.c1847-2040 Objects/dictobject.c2042-2154

Insertion (setitem_lock_held):

• Compute key hash (cached for unicode strings)
• Probe hash table to find existing key or empty slot
• If key exists, update value in place
• If new key, append entry to dk_entries[] and update dk_indices[]
• Resize if load factor exceeds 2/3 (USABLE_FRACTION)

Deletion (delitem_lock_held):

• Probe to find the key
• Mark index as DKIX_DUMMY (can't use DKIX_EMPTY or probing breaks)
• Decrement ma_used but not dk_nentries (entries array stays dense)
• In free-threaded builds, dummy slots are not reused for lock-free reads

Resizing:

• Growth rate: used * 3 (or used * 4 for large dicts > 50000)
• New size must accommodate existing entries plus expected growth
• Creates new PyDictKeysObject, rehashes all entries

Sources: Objects/dictobject.c414-619 Objects/dictobject.c1427-1574

Unicode Key Optimization

Sources: Include/internal/pycore_dict.h82-85 Objects/dictobject.c432-436

When all dictionary keys are unicode strings, CPython uses PyDictUnicodeEntry instead of PyDictKeyEntry:

• No me_hash field: Hash is retrieved from the unicode object via unicode_get_hash()
• Smaller entries: 16 bytes vs 24 bytes per entry (on 64-bit systems)
• Fast equality: Uses optimized unicode_eq() for string comparison
• Split table eligible: Only unicode-key dicts can use split tables

This optimization is particularly beneficial for instance dictionaries (__dict__), which almost always have string keys (attribute names).

Sources: Objects/dictobject.c432-436 Include/internal/pycore_dict.h82-85

Split Tables for Instance Dictionaries

Sources: Objects/dictobject.c56-65 Include/internal/pycore_dict.h231-237

Split Table Mechanism:

• Type object maintains ht_cached_keys pointing to a shared keys object
• All instances of the type reference the same keys object (dk_refcnt > 1)
• Each instance has its own ma_values array containing the attribute values
• Keys array stores only attribute names (strings)
• Insertion order tracked via bit vector (max 16 keys, 4 bits per index)

Benefits:

• Memory efficiency: N instances share one keys object instead of N separate ones
• Cache performance: Keys are read-only, enabling lock-free lookups in free-threaded build
• Predictable layout: Values array index matches keys array index

Limitations:

• Maximum 30 entries (SHARED_KEYS_MAX_SIZE)
• Only unicode keys allowed
• Adding non-string keys or exceeding max size converts to combined table

Sources: Objects/dictobject.c102-106 Include/internal/pycore_dict.h222-223

Version Tagging and Watchers

Sources: Include/internal/pycore_dict.h263-274 Objects/dictobject.c1087-1161

Version Tag (dk_version):

• 32-bit unsigned integer incremented on any dictionary modification
• Used by specializing interpreter to validate inline caches
• Reset to 0 when dictionary structure changes

Watcher Tag (_ma_watcher_tag):

• Low 8 bits: Bitmask of registered watchers (up to 8)
• Bits 8-11: Watched mutation counter for Tier 2 optimization
• High 32 bits: Unique dictionary ID for per-thread refcounting (free-threaded build)

Dictionary Watchers:

• Callbacks triggered on dict modifications: PyDict_EVENT_ADDED, PyDict_EVENT_MODIFIED, PyDict_EVENT_DELETED
• CPython reserves first 3 watcher IDs for builtins, globals, and modules
• Used by debuggers, profilers, and optimization tiers

Sources: Include/internal/pycore_dict.h269-282 Objects/dictobject.c1087-1161

Set and Frozenset Implementation

Set Data Structure

Sources: Objects/setobject.c1-32 Objects/setobject.c66-70

Set Structure:

Field	Type	Purpose
fill	Py_ssize_t	Total used slots (active + dummy)
used	Py_ssize_t	Number of active elements
mask	Py_ssize_t	Hash table size minus 1
table	setentry*	Pointer to hash table
hash	Py_hash_t	Cached hash (frozenset only, -1 if not computed)
weakreflist	PyObject*	List of weak references

Set Entry:

• hash: Hash value of the key
• key: Pointer to the Python object

Unlike dictionaries, sets don't need value storage, only keys.

Sources: Objects/setobject.c66-70 Include/setobject.h

Set Probing and Operations

Sources: Objects/setobject.c220-248 Objects/setobject.c252-335

Probing Strategy:

• Identical to dictionary probing algorithm
• Linear probing for 9 consecutive slots
• Perturbation for randomized jumps: i = (i*5 + 1 + perturb) & mask

Set Operations:

• Add: Probe for empty or dummy slot, insert new entry
• Remove: Probe to find entry, mark as dummy (hash = -1)
• Lookup: Probe until found, empty slot, or changed

Free-Threaded Considerations:

• Sets can be marked shared (SET_MARK_SHARED) for concurrent access
• Thread-safe comparison mode uses atomic loads and validates table consistency
• Frozensets don't need locking since they're immutable

Sources: Objects/setobject.c75-136 Objects/setobject.c413-465

Set vs Frozenset

Sources: Objects/setobject.c171-193 Objects/setobject.c417-420

Key Differences:

Feature	set	frozenset
Mutability	Mutable	Immutable
Hashable	No (__hash__ is None)	Yes (hash cached)
Dict key	Cannot be used	Can be used
Thread safety	Requires locking	Lock-free reads
Operations	Add, remove, update, etc.	Query only

Frozenset Hash Computation:

• Hash computed on first request, cached in set->hash
• Uses XOR of element hashes with salt
• Enables use as dictionary key or set element

Sources: Objects/setobject.c728-773

Thread Safety in Free-Threaded Build

Dictionary Locking Strategy

Sources: Objects/dictobject.c158-286 Objects/dictobject.c1161-1225

Locking Strategy:

1. Combined Tables:

   • All operations require locking the dict object
   • Uses Py_BEGIN_CRITICAL_SECTION(dict)

2. Split Tables:

   • Keys: Protected by dk_mutex, shared read-only access
   • Values: Protected by per-instance dict lock
   • Lock-free reads possible when table is shared

3. QSBR (Quiescent State-Based Reclamation):

   • When resizing shared dicts, old tables freed via _PyMem_FreeDelayed()
   • Ensures no thread is accessing old table before freeing

Atomic Operations:

• STORE_INDEX, LOAD_INDEX: Atomic index array access
• FT_ATOMIC_STORE_PTR_RELEASE, FT_ATOMIC_LOAD_PTR_ACQUIRE: Entry pointers
• Version tags updated atomically

Sources: Objects/dictobject.c158-286 Objects/dictobject.c177-178

Set Concurrency

Sources: Objects/setobject.c75-95 Objects/setobject.c436-464

Set Thread Safety:

1. Mutable Sets:

   • Write operations lock the set object
   • First read from non-owning thread marks set as shared
   • Shared sets delay table freeing using QSBR

2. Frozensets:

   • No locking needed (immutable)
   • Direct memory access safe
   • Uses set_compare_frozenset() without locks

3. Lock-Free Reads:

   • Atomic loads of table pointer, mask, and entries
   • Compare mode validates table consistency during lookup
   • Retry if table changes during operation

Sources: Objects/setobject.c75-136 Objects/setobject.c436-464

Performance Characteristics

Time Complexity

Operation	Average Case	Worst Case	Notes
dict[key]	O(1)	O(n)	With good hash function
dict[key] = val	O(1)	O(n)	May trigger resize
del dict[key]	O(1)	O(n)	No reordering
key in dict	O(1)	O(n)	Hash lookup
dict.get(key)	O(1)	O(n)	Same as __getitem__
set.add(x)	O(1)	O(n)	May trigger resize
set.remove(x)	O(1)	O(n)	Must find element
x in set	O(1)	O(n)	Hash lookup

Sources: Objects/dictobject.c320-412 Objects/setobject.c220-248

Space Complexity

Dictionary:

• Overhead: ~64 bytes for PyDictObject + PyDictKeysObject header
• Per entry:
  • General: 24 bytes (PyDictKeyEntry)
  • Unicode: 16 bytes (PyDictUnicodeEntry)
  • Split table values: 8 bytes per value
• Load factor: Maximum 2/3 full before resize
• Index array: 1/2/4/8 bytes per slot depending on table size

Set:

• Overhead: ~48 bytes for PySetObject
• Per entry: 16 bytes (setentry: hash + key pointer)
• Load factor: Same 2/3 limit as dictionaries

Memory Sharing:

• Split tables can save ~40% memory for instance dictionaries
• N instances with same keys: 1 keys object + N value arrays

Sources: Objects/dictobject.c786-838 Objects/setobject.c483-501

Specialization and Optimization

Sources: Include/internal/pycore_dict.h90-104 Objects/typeobject.c40-56

Version-Based Specialization:

• Dictionary operations cache dk_version in inline caches
• Specialized opcodes bypass generic lookup machinery
• Type attribute lookup caches use both type version and dict version
• Tier 2 optimizer generates guards checking version tags

Split Key Optimization:

• LOAD_ATTR_SPLIT_KEYS: Direct index into ma_values array
• STORE_ATTR_SPLIT_KEYS: Direct assignment without hash lookup
• Requires validating keys object version matches cached version

Sources: Include/internal/pycore_dict.h90-104

---

Summary

CPython's dictionary and set implementations leverage sophisticated hash table techniques:

• Compact, ordered design (since 3.6) separating indices from entries
• Unicode key optimization reducing memory overhead for common cases
• Split tables enabling memory sharing across instance dictionaries
• Hybrid probing combining linear and randomized strategies
• Version tagging for specialization and optimization
• Lock-free reads in free-threaded build for immutable/shared structures

These optimizations make dictionaries and sets extremely efficient for typical Python workloads while maintaining O(1) average-case performance.

Key Implementation Files:

• Objects/dictobject.c1-6000 - Dictionary implementation
• Objects/setobject.c1-2500 - Set implementation
• Include/internal/pycore_dict.h1-400 - Internal structures
• Include/cpython/dictobject.h1-100 - Public API