Dictionaries and Sets — cheat sheet — Algorithms & Data Structures with Python

Dictionaries and sets find things by name or membership almost instantly, where a list has to scan.

Dictionaries

A dictionary (dict) holds key-value pairs: the key is the label, the value is the data.
Write with {key: value, ...}; empty is {}.
Lookup, insert, update, delete, and in are all O(1) on average.
d[key] returns the value but raises KeyError if the key is missing.
d.get(key) returns None if missing; d.get(key, default) returns a fallback of your choice.
d[key] = v adds if new, replaces if the key exists (same syntax for both).
Delete with del d[key], or d.pop(key) to get the value back; .pop(key, default) avoids the crash.
in checks keys only, not values.

Looping a dict gives keys; .values() gives values; .items() gives (key, value) pairs.
Since Python 3.7, iteration follows insertion order.

A key must be hashable, meaning immutable (cannot change after creation).
OK: strings, numbers, tuples of immutable things. Not OK: lists, dicts (raise TypeError).
Values have no restriction; anything goes.

A hash function turns a key into a number; the dict jumps straight to that slot instead of scanning.

key 'Alice' -> hash function -> number (e.g. 2) -> slot 2 -> value

Keys must be immutable so the hash stays stable, or the value would be lost in the wrong slot.
A collision (two keys, same slot) adds a little work; rare bad cases degrade toward O(n).

A set is an unordered collection of unique elements (duplicates discarded); like dict keys with no values.
Membership in is O(1) on average, versus O(n) on a list.
Write with bare values {1, 2, 3}. Trap: {} is an empty dict; use set() for an empty set.
set(list) removes duplicates.
.add(x) adds; .discard(x) removes with no error if absent; .remove(x) raises KeyError if absent.
Elements must be hashable (same rule as keys).
Operations return a new set: union a | b, intersection a & b, difference a - b (each ~O(n)).

list: order and position matter, repeats allowed; lookup by value is O(n).
dict: look up by a key; O(1) average.
set: only membership and uniqueness matter; O(1) average.
Rule of thumb: repeatedly writing if x in my_list means a set or dict fits better.