Python Hash Tables

A hash function turns a key into an integer. Python's built-in hash() exposes it:

print(hash(42))           # 42: small ints hash to themselves
print(hash("J4") == hash("J4"))   # True within one run

The hash table is an array of slots. To store a key, Python computes its hash and reduces it to a slot index, roughly hash(key) % number_of_slots. To look the key up later, it computes the same hash and goes straight to that slot instead of scanning every entry. That's where the speed comes from.

A hash is not a unique identifier. There are infinitely many possible strings but only a fixed range of integers, so different keys must sometimes share a hash. String hashes are also randomised per process for security (to stop attackers deliberately creating collisions), so hash("J4") changes between program runs. Never store hash values in files or databases expecting them to match later.

A collision happens when two different keys map to the same slot, either because their hashes are equal or because different hashes reduce to the same index. Collisions are normal, and every hash table has a strategy for them.

Python uses open addressing: if the slot for a key is taken by a different key, it probes other slots in a pseudo-random sequence until it finds the key or an empty slot. To confirm it has found the right entry, it compares the stored hash and then uses == on the keys:

lookup "J4": hash -> slot 5 -> holds "Q2" (different key) -> probe slot 2 -> holds "J4" -> found

Because equality decides the final match, keys that are equal must have equal hashes; otherwise Python would look in the wrong slot. That's the contract Python enforces on hashable objects. Tables are kept partly empty so probe sequences stay short: when a dict gets about two-thirds full, Python allocates a larger table and reinserts everything, which is called resizing.

A key must be hashable: it needs a hash that never changes while it's stored, and an __eq__ consistent with that hash. In practice:

by_table = {("Fri", 7): "Okafor"}       # tuple key: day and table number
by_table[["Fri", 7]] = "Ruiz"           # TypeError: unhashable type: 'list'

A list can't be a key because it can change: if it changed after being stored, its hash would change and the entry would be lost in the wrong slot. A tuple of immutable values is the standard compound key. If you define __eq__ on a class, also define __hash__ from the same immutable fields, or Python sets __hash__ to None, as explained in magic methods.

Dictionary and set operations, such as lookup, insert, delete and in, are O(1) on average. That rests on assumptions:

• the hash function spreads keys evenly across slots;
• the table is kept sparse enough by resizing;
• comparing two keys is cheap.

Resizing costs O(n) when it happens, but it happens rarely and the size grows geometrically, so averaged over many insertions each one is still O(1) (amortised). The worst case for a single lookup is O(n), if very many keys collide, which is why Python randomises string hashes.

codes = [f"R{i}" for i in range(100_000)]
code_set = set(codes)
print("R99999" in codes)      # True, after scanning ~100,000 items
print("R99999" in code_set)   # True, after hashing once

In everyday code the average case holds, which is why the advice "use a set for membership and a dict for lookups by key" is so reliable. Hash tables do use extra memory, and they don't keep keys sorted; for ordered queries, such as ranges, combine them with sorting or bisect.

Task: index reservations by code and explain hashability, collision handling and average versus worst-case cost.

reservations = [("F7", "Okafor", 2), ("J4", "Ruiz", 5), ("Q2", "Chen", 4)]

by_code = {code: (name, seats) for code, name, seats in reservations}
by_slot = {("Fri", 7): "F7", ("Sat", 2): "J4"}     # compound tuple keys

print(by_code["J4"])                                # ('Ruiz', 5)
print(by_code.get("Z9", "no booking"))              # no booking
print(by_code[by_slot[("Fri", 7)]][0])              # Okafor
print(all(hash(k) == hash(k) for k in by_code))     # equal keys, equal hashes

Explain in comments: lookups are O(1) on average because each key's hash leads straight to its slot; collisions are resolved by probing and equality checks; the worst case is O(n) if many keys collide. For the worked check: can different dictionary keys have the same hash? Yes. Collisions are expected and handled by the table.

The documentation defines hashable and the __hash__ method; the Python wiki lists dict and set operation costs. Continue with trees and binary search trees. Practise with the Python exercises and Python quiz.