Hashing and Hash Tables
A hash table turns a key into an array index by running it through a hash function. That is the whole idea, and it buys average O(1) insert, lookup and delete — which is why a hash map is the single most useful structure to reach for when a problem says "count", "seen before" or "group by".
▶ Start with How hash tables workLessons in order
What you will be able to do
- A hash function turns a key into a bucket index, so lookups skip searching entirely.
- Count, seen-before and group-by cover most hash-map interview questions.
Quiz yourself on Hashing
Reading is not recall. Take a timed quiz on this topic solo, or share a room code and battle friends on it.
⚡ Start the Hashing quizFrequently asked questions
Why is hash table lookup O(1) on average but O(n) in the worst case?
On average, entries are spread across buckets so a lookup examines only a few. If every key hashes to the same bucket, the table degenerates into one long chain and a lookup has to scan all n entries.
What is the load factor of a hash table?
The ratio of stored entries to available buckets. When it exceeds a threshold — 0.75 in Java — the table grows and every entry is rehashed into the larger array.
What happens if you override equals but not hashCode?
Two objects that are equal can produce different hash codes and land in different buckets, so a map lookup with an equal key will fail to find the stored entry.
When should I use a hash map instead of sorting?
When you need O(n) rather than O(n log n), when the original element order matters, or when you need counts rather than order. Sorting wins when the question needs ordering, ranges, or O(1) extra space.
How do you find duplicates in an array efficiently?
Walk the array once, checking membership in a set before inserting. That is O(n) time and O(n) space, against O(n log n) for sorting or O(n squared) for a nested scan.
Why use an array instead of a hash map for character counts?
For a fixed small alphabet, array indexing is direct with no hashing, no boxing and better cache locality. int[26] or int[128] is both faster and simpler than a map.