Hash tables (dicts)

O(1) average insert/lookup/delete. The workhorse of fast Python code.

Code example

session = {}  # dict = hash table
session['user_id'] = 1           # O(1) insert
uid = session['user_id']          # O(1) lookup
'session_id' in session           # O(1) membership

del session['user_id']            # O(1) delete

How it works

A hash table (Python dict) maps keys to values in O(1) average time. The trick: a hash function converts the key to an integer, which is used as an array index. Collisions (two keys hashing to the same index) are handled by chaining. Python's dict is one of the most optimised hash tables in any language. The notebook uses a dict for the per-user namespace — variable lookup is O(1) no matter how many variables you've defined.