1ages = {}2ages["ann"] = 313ages["ben"] = 274ages["ben"]5ages["eve"] = 456ages["bob"] = 527ages["amy"] = 198ages["zoe"] = 239list(ages)10ages[["ann"]] = 1hash()0123456789101112131415123456TypeError
Code card: the program; the highlighted line is the one runningHash function: turns a key into a number, then picks a slotSlots (buckets): where each key and its value are keptKey card: the key travelling to its slotA key card hops from a line of code into the hash function, which turns the key into a number; the remainder after dividing by the table size picks the slot. When two keys pick the same slot, the second tries the next slot until one is free, and a lookup follows exactly the same path. When 5 of the 8 slots are used, adding a sixth key builds a table of 16 slots and every key moves to its new place. Numbered badges show that the dict still remembers the order keys were added. The figure uses a toy hash (add up letter positions) so you can check the sums. Python's real hash() for text gives a huge number, and it changes every time Python starts, so never rely on its value.

Store by key

  1. ages = {} makes an empty dictionary. It will map keys (here, names) to values (ages). When the first key goes in, Python makes a table of 8 slots, often called buckets, numbered 0 to 7.

Collisions

Growing and rules

Try it in the Python prompt

;; step 1/10 · line 1: ages = {}
>>> ages = {}
>>> len(ages)
0
>>> type(ages)
<class 'dict'>

The figure uses a toy hash (add up letter positions) so you can check the sums. Python's real hash() for text gives a huge number, and it changes every time Python starts, so never rely on its value. On a collision the figure tries the next slot (called linear probing). CPython also uses open addressing, but its search jumps around the table in a fixed pattern based on the hash, which spreads crowded keys out. The sizes are CPython's: the first key added gets a table of 8 slots (an empty {} holds no table yet), and Python lets at most two thirds of them be used (5 of 8, 10 of 16). Adding the 6th key builds a table of 16.