A hash table stores key-value pairs and lets you insert, look up or delete by key in O(1) average time. The problem it solves is slow lookup. Searching an unsorted array means checking every element, which is O(n).
An array finds an element in one step only when you know its index. A hash table computes that index from the key. A hash function turns the key into a bucket number, and a lookup recomputes it to jump straight there.
Python's dict and Java's HashMap are both hash tables.
Rewriting in plainer words…
This answer doesn't lend itself to a diagram - it reads best . No credits were charged.
A hash table stores key-value pairs and lets you insert, look up or delete by key in O(1) time on average.
The problem it solves is slow lookup, because finding a value in an unsorted array means checking every element, which is O(n).
An array finds something in one step only when you already know its index, and a hash table works out that index from the key.
A hash function turns the key into a bucket number, and a lookup runs the same function again to jump straight to that bucket.
You're using one every time you reach for a Python dict or a Java HashMap.
The catch is that O(1) is only the average, because keys can collide in one bucket, and the table keeps no sorted order, so it can't answer range queries.
Weak answers to avoid
Says O(1) without the word 'average'Collisions can slow lookups, up to O(n) in the worst case. Say O(1) on average and name collisions as the reason.
Defines it but skips the problem it solvesThe question asks what it solves. Contrast it with an O(n) scan of an unsorted array, then show how computing the index from the key avoids that scan.
Treats the hash function as magic'It hashes the key' explains nothing. Say the function turns the key into a bucket number, and a lookup recomputes it to jump there.
Implies the keys come back sortedA hash table places keys by their hash value, so there is no sorted order. If you need sorted keys or ranges, say a tree map fits better.
Interview lens
Likely follow-ups, what you can say, and the weak answers to avoid.
