Buckets are not identities
A hash function maps a key to a number, from which a table chooses a bucket. Different keys can select the same bucket: this is a collision, not an equality result. A lookup must still compare candidate keys. Expected constant-time behavior assumes a useful distribution and reasonably bounded equality/hash computation. Hashing a long string or comparing a large compound key has its own cost.
Load factor and resizing
As entries accumulate relative to buckets, collisions become more likely. A table may resize and redistribute entries to manage that load. The occasional resize makes insertion costs different from a strict per-operation bound. Java HashMap can use tree-shaped bins in certain collision-heavy cases, but this implementation detail should not become a claim that every hash table offers the same guarantee. A sorted range query usually needs a different structure.
Equality must remain coherent
Java requires equal objects to have equal hash codes. Store an immutable identity as the key when possible. If fields used in equality change after insertion, the key can remain in its old bucket while future lookups choose another. A thread-safe map also cannot repair a mutable key contract. For concurrent compound updates, choose methods with the required atomicity instead of assuming get followed by put is one action.
Worked Java example
Illustrative snippet: imports, surrounding types or collaborators may be omitted. Read the assumptions before adapting it.
Map<String, Integer> counts = new HashMap<>();
for (String word : words) {
counts.merge(word, 1, Integer::sum);
}
int occurrences = counts.getOrDefault("java", 0);Walkthrough
For [java, spring, java], the first java creates value 1, spring creates another entry, and the second java replaces its value with 2. The map retains two distinct keys. HashMap is suitable here only when the loop is not concurrently mutating that shared instance; ConcurrentHashMap can supply atomic per-key merge when that requirement changes.
Practice it yourself
Create an immutable customer ID key and demonstrate that two separately constructed but equal IDs retrieve the same value. Then explain what changes if the ID is mutable.
Check your reasoning
A value record with stable immutable components is one option. Two equal records have compatible generated equality/hashCode. A mutable key can change its hash or equality after insertion, so it should not be used this way.
Recall checklist
- Explain the main invariant or contract without looking.
- Trace the example and test an edge case.
- State time, space, input variables and assumptions where relevant.
- Explain one alternative and when you would choose it.