Hand your coat to the attendant and get ticket 42; later you show 42 and your coat appears instantly — no searching the whole rack. A hash table works like that ticket system, jumping straight to a stored item by its key.
Turn a key into an address
A hash table stores key–value pairs and finds them fast. A hash function converts a key into an array index (a bucket). To look up a key you re-hash it and jump straight to its bucket, giving average O(1) lookup, insertion, and deletion — far faster than scanning a list.
Two keys can hash to the same bucket. Common fixes: chaining (store a small list per bucket) or open addressing (probe for the next free slot). Too many collisions degrade performance toward O(n).
A dictionary/map in most languages is a hash table: phone['Ada'] finds Ada's number without checking every entry.
- You have one million keys and want the value for one of them.
- Compare scanning a list versus hashing the key to its bucket.
- State the average cost of the hash-table lookup.
What you should see: Scanning is O(n) — up to a million checks; hashing jumps to the bucket in O(1) on average, independent of size.