Instead of searching for a key, it computes where the key belongs. A hash function maps the key to an array index, so you go directly to table[hash(key)] rather than scanning. With a good hash that distributes keys uniformly across enough buckets, each bucket holds only a small constant number of keys on average, so insert, lookup, and delete are all O(1) on average, independent of the total number of keys. The "average" qualifier is load-bearing: it assumes a uniform hash and a controlled load factor. The cost you pay for that speed is memory (a sparse table with empty slots) and the loss of any ordering, a hash table can't answer "what's the next-largest key" the way a sorted structure can.
Data Structures & Algorithms · Interview question
How does a hash table achieve O(1) average lookup?
A strong answer
What a weak answer sounds like
You know the answer. Do you know what gets you dinged?
Pro breaks down the answer most candidates actually give to this question — and the specific reason an interviewer marks it down. It’s the difference between sounding correct and sounding senior, on all 472 questions.
From the lesson
Hash Tables
O(1)-average keyed lookup by mapping keys to array slots: collisions, load factor, and why open addressing into a fixed array beats chaining when you have no heap.