Java HashMap: keys, collisions, and update operations

Lookup is a two-part contract

Hashing narrows the search. Equality finishes it. Two keys can share a hash without being equal, so a collision does not mean one entry overwrites the other. Read equals and hashCode before introducing an application object as a key.

A receipt counter needs one entry per payment status. Updating an existing status should change its count, not append another row. A map expresses that requirement directly; a list would require a search before each update.

HashMap does not promise iteration order. An observed order in a small test is not an API contract. Use LinkedHashMap for encounter order or TreeMap for key ordering. Sorting the display and choosing the storage structure are separate decisions.

Update without an unnecessary second lookup

merge supplies the first value when a key is absent and combines it with the existing non-null value otherwise. The counter uses Integer::sum. The merge operation on a plain HashMap is not an atomic update shared safely among threads.

Null needs care. get returns null for both a missing mapping and an entry explicitly mapped to null; containsKey distinguishes those states. This counter never stores null, which removes that ambiguity from its caller contract.

The counters describe an in-memory batch. They are not an audit ledger: process exit loses them, repeated delivery increments them again, and concurrent updates need a different ownership model.

Internal working: a Java 8 implementation view

The Java 8 implementation stores entries in a bucket array. It spreads a key hash with a shifted portion of the hash and selects a bucket using a mask against the current power-of-two capacity. Equality is still checked inside that bucket. These are implementation details of the inspected Java 8 source, not extra promises made by the Map interface.

The default load factor is 0.75. Capacity and load factor determine when growth is needed, but an initial capacity is not a fixed maximum number of mappings. During a resize, stored hash bits decide whether an entry remains at its old index or moves by the old capacity. Keys still need stable equality and hash behavior; growth cannot repair a mutated key.

The inspected Java 8 source declares a treeification threshold of eight and a minimum treeification capacity of sixty-four. A collision-heavy bucket can trigger growth rather than tree conversion when the array is smaller. Treating eight colliding insertions as a portable guarantee of a tree is therefore wrong. The insertion path, current capacity and release matter.

Tree bins limit many collision cases, but a blanket claim that every hostile key set gives logarithmic lookup is too broad. Equal-hash keys and their comparability affect how the implementation searches. Iteration also visits capacity and stored mappings, so allocating a huge sparse map can make scanning expensive even when lookups are usually quick. Validate adversarial keys and measure the application distribution before choosing a capacity.

Working program

import java.util.HashMap;
import java.util.Map;

public class ReceiptCounter {
    public static void main(String[] args) {
        Map<String, Integer> counts = new HashMap<>();
        String[] statuses = {"paid", "declined", "paid", "pending", "paid"};
        for (String status : statuses) {
            counts.merge(status, 1, Integer::sum);
        }
        System.out.println("paid=" + counts.getOrDefault("paid", 0));
        System.out.println("refunded=" + counts.getOrDefault("refunded", 0));
        System.out.println("statuses=" + counts.size());
    }
}

Output

paid=3
refunded=0
statuses=3

Cost and design choices

For well-distributed hashes, each map update has expected constant lookup cost. With n input statuses and k distinct statuses, the batch requires expected O(n) time and O(k) stored entries. String hashing and equality themselves depend on key length, so treating arbitrarily long keys as free work would be misleading.

Capacity is the bucket budget, not the number of mappings already present. Growth allocates storage and moves entries. Excessive preallocation also costs memory and can make iteration expensive. Measure the actual batch size before selecting a capacity.

A key whose equality-relevant fields change after insertion may no longer be found by a later lookup. Store stable identifiers or immutable key objects. Resizing a map does not repair a broken key contract.

Common Mistakes

• Do not depend on HashMap iteration order in tests or API responses.
• Do not mutate keys after inserting them.
• Do not assume merge on HashMap is safe for simultaneous writers.
• Do not let Integer counters wrap silently when batch totals can exceed their range.

Continue with collection and web contracts

Continue with Java Map.merge: combine a value or remove its mapping, Java computeIfAbsent: null means no new mapping.

Continue with ownership and failure checks

Continue with Java IdentityHashMap: reference identity is not value equality.