HashMap

HashMap<K, V> is the default key-value store in Java. It provides average constant-time O(1) lookups with no iteration-order guarantees.

Internal Bucket ArchitectureCopy Anchor Link

• Initial Capacity: 16 buckets.
• Load Factor: 0.75 (doubles table capacity when 75% full).
• Treeification Threshold: When a single bucket index accumulates >= 8 colliding entries and the total table capacity is >= 64, that linked chain transforms into a balanced Red-Black Tree (TreeNode). This bounds worst-case collision lookup at O(log n) instead of O(n), mitigating Hash-DoS vulnerabilities.

Map<Integer, String> map = new HashMap<>();

String prev = map.put(1, "Alice"); // returns null
String updated = map.put(1, "Bob"); // returns "Alice" (previous value)

String val = map.get(1);            // "Bob" (null if absent)
boolean hasK = map.containsKey(1);   // true (O(1))
boolean hasV = map.containsValue("Bob"); // true (O(n) scan)

String removed = map.remove(1);     // returns "Bob"

Complexity & Null HandlingCopy Anchor Link

• Null Keys: Allows exactly one null key (stored in bucket 0).
• Null Values: Allows multiple null values.
• Thread Safety: Not thread-safe. Use ConcurrentHashMap for concurrent multi-threaded access.

Iteration & Traversal PatternsCopy Anchor Link

Because Map does not implement Iterable, traversal is performed via its collection views (entrySet(), keySet(), values()) or the forEach method:

// Recommended default: single-pass extraction of both key and value
for (Map.Entry<Integer, String> entry : map.entrySet()) {
    Integer id = entry.getKey();
    String name = entry.getValue();
    System.out.println(id + " -> " + name);
}

High-Frequency DSA IdiomsCopy Anchor Link

1. Frequency Counting with merge()Copy Anchor Link

Map<String, Integer> freq = new HashMap<>();
for (String word : words) {
    freq.merge(word, 1, Integer::sum);
}

2. Grouping / Multi-Map with computeIfAbsent()Copy Anchor Link

Map<Character, List<String>> groups = new HashMap<>();
for (String word : words) {
    char firstChar = word.charAt(0);
    groups.computeIfAbsent(firstChar, k -> new ArrayList<>()).add(word);
}