Solving the hash computation problem when working with dictionaries

Any hash table, including Python's dictionary, must be able to handle the hash computation problem. This is accomplished using either open addressing or chaining techniques. Python uses open addressing.

A new dictionary is initialized with 8 empty slots.

The interpreter first tries to add a new entry at an address that depends on the key's hash.

addr = hash(key) & mask,

where

mask = PyDictMINSIZE - 1

If this address is occupied, the interpreter checks (using ==) both the hash and the key. If both match, it means the entry already exists. Then begins the probing of free slots, which proceeds in a pseudorandom order (the order depends on the key value). The new entry will be added at the first free address found.

Reading from the dictionary happens similarly - the interpreter starts searching from position addr and follows the same pseudorandom path until it reads the needed entry.