HashMap
IntermediateUnderstand how HashMap works internally — hashing, buckets, collision resolution, treeification, and load factor — and use its modern API.
Overview
HashMap is Java's most-used Map implementation. It stores entries in a hash table: an array of buckets indexed by hash(key) % capacity. Average get/put/remove is O(1). Collisions (two keys landing in the same bucket) are resolved first with linked lists; from Java 8+, buckets with ≥ 8 entries and table size ≥ 64 are converted to balanced Red-Black trees, making worst-case O(log n) instead of O(n). Correct hashCode() and equals() on keys is non-negotiable — bad hashing causes all entries to land in one bucket, degrading to O(n).
Internal Mechanics — Buckets, Hashing & Treeification
HashMap internalises an array Node<K,V>[] table. Each Node holds hash, key, value, and a next pointer (for chaining). put(key, value) computes index = (n-1) & hash(key) where n is the table length (always a power of 2). If the bucket is empty, a new node is placed there. If occupied (collision), Java walks the chain comparing with equals() and either updates or appends.
Default initial capacity: 16. Load factor: 0.75. When size > capacity × loadFactor, the table doubles (rehash — expensive, O(n)). Treeification threshold: 8 entries in a bucket → Red-Black tree. Untreeification threshold: 6 entries → back to linked list.
import java.util.HashMap;
import java.util.Map;
public class HashMapInternals {
// Bad hashCode — all keys land in bucket 0 → O(n) performance
static class BadKey {
int value;
BadKey(int v) { value = v; }
@Override public int hashCode() { return 0; } // always 0!
@Override public boolean equals(Object o) {
return o instanceof BadKey bk && bk.value == value;
}
}
// Good hashCode — spreads keys across buckets
static class GoodKey {
int value;
GoodKey(int v) { value = v; }
@Override public int hashCode() { return Integer.hashCode(value); }
@Override public boolean equals(Object o) {
return o instanceof GoodKey gk && gk.value == value;
}
}
public static void main(String[] args) {
// Basic operations
Map<String, Integer> map = new HashMap<>();
map.put("Alice", 90);
map.put("Bob", 85);
map.put("Carol", 92);
map.put("Alice", 95); // update existing key
System.out.println(map.get("Alice")); // 95
System.out.println(map.containsKey("Dave")); // false
System.out.println(map.containsValue(85)); // true
System.out.println(map.size()); // 3
// null key and null value are allowed (one null key)
map.put(null, 0);
System.out.println(map.get(null)); // 0
// Pre-size to avoid rehash — new HashMap<>(expectedSize / 0.75 + 1)
Map<String, String> presized = new HashMap<>(100); // for ~75 entries
// Internal bucket count is always power of 2
// HashMap capacity 16 → threshold 12 → at 13 entries, doubles to 32
}
}Modern HashMap API (Java 8+)
Java 8 added a rich set of Map methods that eliminate verbose if-null-then-put patterns:
getOrDefault(key, default) — safe read putIfAbsent(key, value) — write only if key absent computeIfAbsent(key, fn) — compute and store if absent (great for building group maps) computeIfPresent(key, fn) — update only if key present compute(key, fn) — compute unconditionally (can return null to remove) merge(key, value, fn) — upsert with merge function (great for counting) forEach(BiConsumer) — iterate without for-each boilerplate replaceAll(BiFunction) — transform all values in-place
import java.util.*;
public class ModernHashMap {
public static void main(String[] args) {
// ── Counting words ───────────────────────────────────────────
String[] words = {"the", "quick", "brown", "fox", "the", "quick", "the"};
Map<String, Integer> freq = new HashMap<>();
for (String w : words) {
freq.merge(w, 1, Integer::sum); // if absent → 1; else → old + 1
}
System.out.println(freq); // {the=3, quick=2, brown=1, fox=1}
// ── Grouping into lists ──────────────────────────────────────
String[] names = {"Alice", "Bob", "Anna", "Brian", "Charlie"};
Map<Character, List<String>> byLetter = new HashMap<>();
for (String name : names) {
byLetter.computeIfAbsent(name.charAt(0), k -> new ArrayList<>())
.add(name);
}
System.out.println(byLetter);
// {A=[Alice, Anna], B=[Bob, Brian], C=[Charlie]}
// ── Other modern methods ─────────────────────────────────────
Map<String, Integer> scores = new HashMap<>(Map.of("Alice", 80, "Bob", 70));
scores.putIfAbsent("Carol", 90); // added
scores.putIfAbsent("Alice", 100); // NOT updated — key exists
System.out.println(scores.get("Alice")); // 80
scores.computeIfPresent("Bob", (k, v) -> v + 10); // Bob: 80
System.out.println(scores.get("Bob")); // 80
scores.replaceAll((k, v) -> v + 5); // +5 to everyone
System.out.println(scores);
scores.forEach((k, v) -> System.out.println(k + ": " + v));
// getOrDefault — safe read without null check
System.out.println(scores.getOrDefault("Dave", 0)); // 0
}
}HashMap vs Hashtable vs LinkedHashMap vs ConcurrentHashMap
HashMap — not thread-safe; allows one null key; O(1) average Hashtable — legacy; thread-safe with synchronized; no null keys; do not use in new code LinkedHashMap — extends HashMap; maintains insertion order (or access order); O(1) average; slightly more memory ConcurrentHashMap — thread-safe without locking the entire map; no null keys or values; segment/bin locking (Java 8+: CAS + synchronized on individual bins); use for concurrent code WeakHashMap — keys are weakly referenced; entries GC'd when key has no other references; useful for caches
import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
public class MapVariants {
public static void main(String[] args) {
// LinkedHashMap — insertion order
Map<String, Integer> linked = new LinkedHashMap<>();
linked.put("banana", 2);
linked.put("apple", 1);
linked.put("cherry", 3);
System.out.println(linked); // {banana=2, apple=1, cherry=3} — insertion order
// Access-order LinkedHashMap — LRU cache base
Map<String, String> lruCache = new LinkedHashMap<>(16, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry<String, String> e) {
return size() > 3; // evict when more than 3 entries
}
};
lruCache.put("a", "1"); lruCache.put("b", "2"); lruCache.put("c", "3");
lruCache.get("a"); // access "a" — moves it to most-recently-used
lruCache.put("d", "4"); // triggers eviction of LRU entry ("b")
System.out.println(lruCache.keySet()); // [c, a, d]
// ConcurrentHashMap — thread-safe, no null keys/values
Map<String, Integer> concurrent = new ConcurrentHashMap<>();
concurrent.put("key", 1);
concurrent.merge("key", 1, Integer::sum); // atomic
System.out.println(concurrent.get("key")); // 2
// ConcurrentHashMap atomic operations
concurrent.putIfAbsent("newKey", 42);
concurrent.computeIfAbsent("list", k -> 0);
}
}Interactive Visualization
Key Points to Remember
- HashMap uses hash table with chaining; Java 8+ treeifies buckets with ≥8 entries to O(log n)
- Default capacity 16, load factor 0.75 — rehash doubles the table; pre-size for large maps
- Keys must correctly implement hashCode() + equals() — bad hashing degrades all ops to O(n)
- merge() is the cleanest way to count/aggregate; computeIfAbsent() is best for group-by maps
- Null allowed: one null key, any number of null values — ConcurrentHashMap forbids both
- For thread safety: ConcurrentHashMap (concurrent reads/writes), not the legacy Hashtable
Practice HashMap in the Playground
Run and modify code directly in your browser - no setup needed.
Interview Questions
Sign in to ask AriaHow does HashMap work internally?
What is the default load factor of HashMap and why 0.75?
What improvements were made to HashMap in Java 8?
What happens if two keys have the same hashCode()?
What is the difference between HashMap and ConcurrentHashMap?
Ask Aria about HashMap
Your personal AI tutor — ask anything about this concept