Hash Tables (Concept, Collisions, Average O(1))

A hash table maps keys through a hash function to buckets; average O(1) get/put relies on low collision rate and dynamic resizing when load factor grows.

Why this shows up in the real world

Databases use hash joins; cryptography uses different families (never confuse with hash() for security).

Core idea (explained for students)

Python dict is a highly optimized hash table: iteration order is insertion-ordered (3.7+). Understand equality vs identity for keys.

Try this in Python

d = {}
d['a'] = 1
d['b'] = 2
print(list(d.keys()), d.get('c', 0))

Common mistakes

• Using unhashable keys (list, dict).
• Assuming worst-case O(1)—adversarial hashing exists in theory; not CP focus.

Key takeaways

• Know open addressing vs chaining conceptually even if you only use dict.
• hash((1,2)) works; hash([1,2]) raises.