Lesson 4.1 · Hashing
How a HashMap Works Inside
Buckets, hash codes, equals, collisions and resizing: why lookups are O(1) on average and what can make them slow.
15 min
Think of it like this
A cloakroom with 16 numbered hooks. When you hand in your coat, the attendant turns your ticket name into a hook number with a quick formula and hangs it there. To get it back, they apply the same formula and go straight to that hook. If two coats land on the same hook, they hang them together and check the tickets.
1.From key to bucket
A HashMap holds an array of buckets. To store a key, it calls key.hashCode() (an int), mixes the bits, and takes it modulo the number of buckets to pick one. Lookup repeats the calculation and only searches that single bucket.
Inside a bucket there may be several entries (a collision). The map compares keys with equals to find the right one. With a good spread, buckets hold about one entry each, so get, put and remove are O(1) on average.
2.Resizing and the load factor
When the number of entries passes 75% of the bucket count (the load factor 0.75), the map doubles its buckets and re-places every entry. That single step is O(n), but it's rare, so put stays O(1) amortised.
If you know roughly how many entries you'll store, new HashMap<>(capacity) avoids repeated resizing.
3.When buckets get crowded
Many keys with the same hash code would pile into one bucket and make lookups O(n). Since Java 8, a bucket with more than 8 entries (in a big enough map) becomes a small balanced tree, so the worst case is O(log n). With ordinary keys (numbers, strings) you can treat operations as O(1).
Quick check
Why must two keys that are equals also have the same hashCode?
Remember
- hashCode picks the bucket; equals finds the key inside it.
- Average O(1) get, put, remove; resize keeps put amortised O(1).
- Equal keys must have equal hash codes.
- Java turns crowded buckets into trees, capping the worst case at O(log n).
Common mistakes
- Overriding equals without hashCode in your own key class.
- Assuming HashMap iterates in insertion order.
Words used in this lesson
- Hash code
- An int computed from a key, used to choose its bucket.
- Bucket
- One slot of the map's internal array, holding the entries whose hash lands there.
- Collision
- Two different keys landing in the same bucket.
- Load factor
- How full the map may get (entries ÷ buckets) before it resizes; 0.75 in Java.