Hash Tables
Beginner · 16 min read · Data Structures Basics, Linear Structures
Hash functions, buckets, collisions and resizing: why lookups are O(1) on average.
A hash table answers "where is the value for this key?" in O(1) on average, without searching and without sorting. It's the most useful data structure in interviews: a large share of O(n²) brute forces become O(n) once you add one. The idea is simple.
Picture it
How it works
Two different keys can land in the same bucket. That's a collision, and it can't be avoided, because there are far more possible keys than buckets. There are two classic ways to handle it:
The equals/hashCode contract
If two keys are equals, they must have the same hashCode. Otherwise a lookup computes a different bucket and never finds the entry. String, Integer, List and records follow the rule. For your own key class:
Types
Operations and their cost
In an interview, say "O(1) average" for hash operations. It shows you know the worst case exists.
Idioms you'll use constantly
Patterns that use hash tables
Interview questions
- How does a hash map achieve O(1) average lookups, and what is the worst case?
- What happens if you override equals but not hashCode for a key class?
Further reading
Key takeaways
- A hash table turns a key into an array index: hashCode, then & 0x7fffffff, then % capacity.
- Collisions are normal: chaining keeps a small list per bucket; resizing keeps the load factor below 0.75.
- O(1) average for put, get and remove; worst case O(n) (O(log n) for Java's tree bins).
- Equal keys must have equal hash codes; don't mutate keys; don't rely on HashMap order.
- HashMap and HashSet for lookups, LinkedHashMap for order, TreeMap for sorted keys.