☕ JavaCollections Framework

HashMap

HashMap is the most widely used Map implementation in Java. It stores key-value pairs in a hash table, providing average O(1) performance for get, put, remove, and containsKey operations. Keys are stored in no guaranteed order. HashMap permits one null key and multiple null values. It is not thread-safe. Understanding how HashMap uses hash codes, handles collisions, and resizes is foundational knowledge for writing efficient Java code.

How HashMap Works Internally

HashMap stores entries in an array of buckets (Node[] table). When you call put(key, value), Java computes the key's hash code, applies a supplemental hash function to reduce clustering, and uses the result modulo the array length to determine the bucket index. If two keys map to the same bucket (a hash collision), entries are chained in the same bucket. In Java 7 and earlier, collision chains were singly linked lists. Java 8 introduced a critical optimisation: when a bucket's chain grows beyond 8 entries (TREEIFY_THRESHOLD), it converts to a red-black tree, reducing worst-case lookup in that bucket from O(n) to O(log n). When the bucket shrinks below 6 entries (UNTREEIFY_THRESHOLD), it converts back to a linked list. The load factor (default 0.75) controls when the map resizes. When the number of entries exceeds capacity × loadFactor, the map doubles its capacity and rehashes all entries. The load factor balances memory use against lookup performance: a lower load factor means fewer collisions but more memory and more frequent resizing; a higher load factor saves memory but increases collision probability and slows lookups. HashMap uses hashCode() and equals() of the key to determine where to store an entry and how to find it. This is why the equals-hashCode contract is critical: if two objects that are logically equal have different hashCodes, the same key can be "put" twice into the map producing two entries that can never be retrieved because get() will compute a different bucket for the same logical key. If you use a custom class as a HashMap key, you must override both equals() and hashCode() correctly.

Java

// ── HashMap internal structure (Java 8+): ────────────────────────────
// HashMap<K,V> {
//   Node<K,V>[] table;      // the bucket array
//   int size;               // number of key-value mappings
//   int threshold;          // size * loadFactor — resize when exceeded
//   float loadFactor;       // default 0.75
// }
//
// Node<K,V> {
//   int hash;
//   K key;
//   V value;
//   Node<K,V> next;         // linked list chain or tree node
// }
//
// put("Alice", 90):
//   hash = "Alice".hashCode()  (= some int, e.g. 63557208)
//   spread = hash ^ (hash >>> 16)
//   bucket = spread & (capacity-1)  e.g. spread & 15 = bucket 8
//   table[8] = new Node(hash, "Alice", 90, null)

// ── Creating HashMap: ────────────────────────────────────────────────
Map<String, Integer> map = new HashMap<>();
Map<String, Integer> withCapacity = new HashMap<>(32);        // initial capacity
Map<String, Integer> withBoth     = new HashMap<>(32, 0.5f);  // capacity + load factor
Map<String, Integer> fromMap      = new HashMap<>(existingMap);

// ── Basic operations: ─────────────────────────────────────────────────
map.put("Alice", 90);
map.put("Bob",   85);
map.put("Carol", 92);
map.put("Alice", 95);    // replaces existing — returns old value 90

Integer score  = map.get("Alice");        // 95
Integer absent = map.get("Dave");         // null — key not present
boolean hasBob = map.containsKey("Bob");  // true
boolean has85  = map.containsValue(85);   // true
int     size   = map.size();              // 3
map.remove("Carol");                      // removes entry
Integer old    = map.remove("Bob", 85);   // conditional remove — only if value matches

HashMap Methods — Complete Reference

HashMap's API extends beyond basic put/get/remove to include a rich set of functional methods added in Java 8. These methods enable atomic compound operations that would otherwise require explicit locking in concurrent code, and they provide cleaner idioms for common patterns like compute-if-absent, merge, and conditional update. getOrDefault() is the safest way to retrieve a value when the key might not be present — it returns a specified default rather than null, eliminating null checks. putIfAbsent() adds an entry only if the key is not already present, returning the existing value if it is. These two methods together support a common pattern: initialise a value if not present, then retrieve it. computeIfAbsent() computes a value using a function only if the key is absent, then inserts the result. This is the correct way to implement a lazily computed map value or a map of lists — computeIfAbsent(key, k -> new ArrayList<>()) ensures the list exists before adding to it. computeIfPresent() updates an existing value only if the key is present. compute() updates unconditionally, receiving both key and current value (null if absent) and setting the new value. merge() is the most powerful of these methods. It applies a BiFunction to the old and new values if the key is present, or inserts the new value if the key is absent. This is the idiomatic way to implement count maps (merge(word, 1, Integer::sum)) and accumulation patterns.

Java

Map<String, Integer> scores = new HashMap<>();
scores.put("Alice", 90);
scores.put("Bob",   85);

// ── Safe retrieval: ───────────────────────────────────────────────────
System.out.println(scores.getOrDefault("Carol", 0));   // 0 — not in map
System.out.println(scores.getOrDefault("Alice", 0));   // 90 — in map

// ── Conditional put: ─────────────────────────────────────────────────
scores.putIfAbsent("Carol", 78);   // adds Carol=78 (not present)
scores.putIfAbsent("Alice", 100);  // no change — Alice already present
System.out.println(scores.get("Carol")); // 78
System.out.println(scores.get("Alice")); // 90 — unchanged

// ── computeIfAbsent — lazily initialise: ─────────────────────────────
Map<String, List<String>> groups = new HashMap<>();
groups.computeIfAbsent("team-a", k -> new ArrayList<>()).add("Alice");
groups.computeIfAbsent("team-a", k -> new ArrayList<>()).add("Bob");
groups.computeIfAbsent("team-b", k -> new ArrayList<>()).add("Carol");
System.out.println(groups); // {team-a=[Alice, Bob], team-b=[Carol]}

// ── merge — count word frequencies: ─────────────────────────────────
String text = "the quick brown fox the fox";
Map<String, Integer> freq = new HashMap<>();
for (String word : text.split(" ")) {
    freq.merge(word, 1, Integer::sum);
}
System.out.println(freq); // {the=2, quick=1, brown=1, fox=2}

// ── compute — update with logic: ──────────────────────────────────────
scores.compute("Alice", (k, v) -> v == null ? 0 : v + 5); // 90 → 95
scores.compute("Dave",  (k, v) -> v == null ? 50 : v + 5); // null → 50

// ── replaceAll — transform all values: ────────────────────────────────
scores.replaceAll((k, v) -> v + 10);   // add 10 to every score

// ── Iteration patterns: ───────────────────────────────────────────────
for (Map.Entry<String, Integer> entry : scores.entrySet()) {
    System.out.printf("%-10s → %d%n", entry.getKey(), entry.getValue());
}

scores.forEach((name, score) -> System.out.printf("%s: %d%n", name, score));

scores.keySet().forEach(System.out::println);
scores.values().forEach(System.out::println);

HashMap Performance, Pitfalls, and Best Practices

HashMap's O(1) average performance comes from the assumption that hash codes are well distributed and that the equals-hashCode contract is correctly implemented by the key type. Violations of either assumption degrade performance severely. A pathological hash function — one that maps many keys to the same hash code — causes many keys to land in the same bucket, degrading all operations to O(n). This can happen accidentally when using custom objects with a poor or constant hashCode(), or deliberately as a hash collision denial-of-service attack. Java 8's tree-bucket conversion mitigates this, degrading to O(log n) instead of O(n). Null keys are permitted in HashMap — one per map. null is handled as a special case: its hash is treated as 0, placing it in bucket 0. Null values are also permitted and may cause confusion: map.get(key) returns null both when the key is not present and when the key is mapped to null. Use containsKey() to distinguish the two cases. Iterating over a HashMap's entrySet() while modifying the map (adding or removing entries) throws ConcurrentModificationException. Use an explicit iterator with iterator.remove() for removal during iteration, or use removeIf() on the entrySet. Never use map.remove() inside a for-each over the map's collection views. Choosing initial capacity correctly avoids expensive rehashing. If you know you will add n entries, set the initial capacity to n / 0.75 + 1 (or simply use a round number slightly above n / 0.75). Creating new HashMap<>(16) and then adding 1000 entries causes approximately seven rehash operations.

Java

// ── equals-hashCode contract — using custom key: ─────────────────────
public class Point {
    private final int x, y;

    public Point(int x, int y) { this.x = x; this.y = y; }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Point p)) return false;
        return x == p.x && y == p.y;
    }

    @Override
    public int hashCode() {
        return Objects.hash(x, y);   // MUST match equals() fields
    }
}

Map<Point, String> map = new HashMap<>();
map.put(new Point(1, 2), "origin-ish");
System.out.println(map.get(new Point(1, 2)));  // "origin-ish" — works!
// Works because Point correctly overrides both equals() and hashCode().

// ── Null key: ─────────────────────────────────────────────────────────
Map<String, Integer> m = new HashMap<>();
m.put(null, 42);
System.out.println(m.get(null));           // 42
System.out.println(m.containsKey(null));   // true

// Distinguish null-mapped from absent:
m.put("present-null", null);
System.out.println(m.get("present-null"));   // null — key IS present
System.out.println(m.get("absent-key"));     // null — key NOT present
System.out.println(m.containsKey("present-null"));  // true — is present
System.out.println(m.containsKey("absent-key"));    // false — not present

// ── Correct removal during iteration: ────────────────────────────────
Map<String, Integer> scores = new HashMap<>();
scores.put("Alice", 90); scores.put("Bob", 45); scores.put("Carol", 78);

// Remove low scores using entrySet().removeIf():
scores.entrySet().removeIf(entry -> entry.getValue() < 60);
System.out.println(scores);  // {Alice=90, Carol=78}

// ── Sizing for known capacity: ────────────────────────────────────────
// Expect 1000 entries — compute initial capacity to avoid rehashing:
int expectedSize = 1000;
int initialCapacity = (int) (expectedSize / 0.75) + 1;  // ~1334
Map<String, String> sized = new HashMap<>(initialCapacity);
// This map will not resize until >1000 entries are added.

HashMap

How HashMap Works Internally

HashMap Methods — Complete Reference

HashMap Performance, Pitfalls, and Best Practices

Related Topics in Collections Framework