<code>HashMap</code> in Java — Key/Value Lookup in O(1)

HashMap is Java's main key→value lookup table. Average-case O(1) for get, put, containsKey and remove. Iteration order is not guaranteed and has changed between JDK versions — if order matters, use LinkedHashMap or TreeMap.

Basics

var votes = new HashMap<String, Integer>();
votes.put("Alice", 1);
votes.put("Bob",   2);

Integer a = votes.get("Alice");           // 1
Integer z = votes.get("unknown");          // null
int v = votes.getOrDefault("unknown", 0);  // 0 — no null
votes.containsKey("Alice");                // true
votes.remove("Bob");
votes.size();

Modern helpers (Java 8+)

// Increment-or-create
votes.merge("Alice", 1, Integer::sum);

// Lazy init of a value
var index = new HashMap<String, List<User>>();
index.computeIfAbsent(user.city(), k -> new ArrayList<>()).add(user);

// Conditional update
votes.replace("Alice", 5);                 // only if key exists
votes.putIfAbsent("Carol", 0);              // only if absent

How it works

1. put(k, v) computes k.hashCode(), mixes it, and mods into a bucket index.
2. The bucket holds a linked list (or a balanced tree for large buckets since Java 8).
3. On collision, the list/tree is scanned with equals().
4. If the map's size exceeds capacity × load factor (default 0.75), the buckets are doubled and everything is rehashed.

The equals/hashCode contract

Any custom key must override equals and hashCode consistently:

// ❌ Broken custom key — no hashCode override
class Bad {
    final int id;
    Bad(int id) { this.id = id; }
    public boolean equals(Object o) {
        return o instanceof Bad b && b.id == id;
    }
    // hashCode from Object — same-id objects get different hashes
}
var m = new HashMap<Bad, String>();
m.put(new Bad(1), "hi");
m.get(new Bad(1));          // null — ended up in a different bucket

Records give you both for free. Use a record or Lombok's @EqualsAndHashCode.

Mutable keys — don't

var key = new StringBuilder("a");
map.put(key, 1);
key.append("b");                            // hashCode changed
map.get(key);                               // null — lookup goes to the wrong bucket

Iteration

for (var e : map.entrySet()) {
    System.out.println(e.getKey() + "=" + e.getValue());
}

map.forEach((k, v) -> System.out.println(k + "=" + v));

// By entries, sorted by key
map.entrySet().stream()
    .sorted(Map.Entry.comparingByKey())
    .forEach(e -> System.out.println(e.getKey() + "=" + e.getValue()));

HashMap vs alternatives

Common mistakes

• Using HashMap across threads — corruption, infinite loops. Use ConcurrentHashMap.
• Custom key without hashCode — silent data loss. Use records.
• Assuming insertion order — use LinkedHashMap.
• get() returning null — easy to NPE on auto-unbox. Use getOrDefault.

Related

Pillar: Java collections. Siblings: LinkedHashMap, TreeMap, equals & hashCode.