6.1. Mapping About

How are dictionaries implemented in CPython? [1]

CPython's dictionaries are implemented as resizable hash tables. Compared to B-trees, this gives better performance for lookup (the most common operation by far) under most circumstances, and the implementation is simpler.

Dictionaries work by computing a hash code for each key stored in the dictionary using the hash() built-in function. The hash code varies widely depending on the key and a per-process seed; for example, "Python" could hash to -539294296 while "python", a string that differs by a single bit, could hash to 1142331976. The hash code is then used to calculate a location in an internal array where the value will be stored. Assuming that you're storing keys that all have different hash values, this means that dictionaries take constant time – O(1), in Big-O notation – to retrieve a key.

../../_images/mappings-dict-hashmap.png

6.1.1. Scalar

  • Scalar

>>> 'Mark'  
>>> 'Watney'  
>>> 42  
>>> 178.0  
>>> 75.5

6.1.2. Value

  • Identifier + scalar = value

>>> firstname = 'Mark'
>>> lastname = 'Watney'
>>> age = 42
>>> height = 178.0
>>> weight = 75.5

6.1.3. Data

  • Value + relation = data

>>> astronaut = ('Mark', 'Watney', 42, 178.0, 75.5)

6.1.4. Information

  • Data + context = information

>>> astronaut = {
...     'firstname': 'Mark',
...     'lastname': 'Watney',
...     'age': 42,
...     'height': 178.0,
...     'weight': 75.5,
... }

6.1.5. References