Java Collections

HashMap / TreeMap

Complete lesson for HashMap / TreeMap using LEARNCODEGURU’s 6-level learning model — from basics to advanced practice, with Java OOP and Collections where relevant.

Basics — HashMap / TreeMap

Section: Java Collections. HashMap, TreeMap, and ConcurrentHashMap: buckets, null rules, and interview complexity.

Key-value store

HashMap offers average O(1) put / get / remove. Keys must obey equals/hashCode.
One null key and many null values are allowed. Iteration order is undefined (unless LinkedHashMap).
getOrDefault, putIfAbsent, merge, computeIfAbsent (Java 8) avoid extra lookups.

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

public class HashMapBasics {
    public static void main(String[] args) {
        Map<String, Integer> freq = new HashMap<>();
        for (String w : new String[] {"java", "jvm", "java"}) {
            freq.merge(w, 1, Integer::sum);
        }
        System.out.println(freq.getOrDefault("rust", 0));
        freq.forEach((k, v) -> System.out.println(k + "=" + v));
    }
}

HashMap vs TreeMap vs ConcurrentHashMap

	`HashMap`	`TreeMap`	`ConcurrentHashMap`
Order	None	Sorted by key	None (weakly consistent)
Complexity	Average O(1)	O(log n)	Average O(1) concurrent
Null key	Yes (one)	No (natural order)	No
Null values	Yes	Yes	No
Thread-safe	No	No	Yes
Use	General map	Sorted / range (`subMap`)	Shared caches, counters

Hashtable (legacy)

Hashtable is synchronized, forbids nulls, and is mostly replaced by ConcurrentHashMap or a synchronized wrapper.
Interviews still ask HashMap vs Hashtable: sync, nulls, iterators (fail-fast vs Enumerator).

Advanced — HashMap / TreeMap

Buckets, load factor, and treeify

Default capacity 16, load factor 0.75 — resize when size > capacity * loadFactor. Resize is O(n).
Hash is mixed (hash ^ (hash >>> 16)) so high bits affect the bucket index.
Java 8+ treeifies a bin when collisions exceed a threshold (and table is large enough). Comparable keys help the tree.
Never use a mutable object as a key. Never use == to look up a custom key — get uses equals.
LinkedHashMap can be access-ordered — the usual building block for a simple LRU (override removeEldestEntry).

Tricky Interview Points

Q1) How does HashMap work internally?

Answer An array of bins. The key’s hash selects a bin; collisions are a list or a tree. equals finds the exact key. Resize rehashes when the load factor is exceeded.

Q2) Why override hashCode with equals for keys?

Answer get/put find the bin with hashCode, then equals. If they disagree, you cannot retrieve the value you stored.

Q3) HashMap vs ConcurrentHashMap?

Answer HashMap is single-thread (or externally locked). CHM allows concurrent reads/writes, forbids nulls, and does not lock the whole table for typical operations.

Q4) Can two keys have the same hashCode?

Answer Yes. They share a bucket and are distinguished by equals.

Q5) What is load factor 0.75?

Answer A resize trigger: trade-off between wasted space (low factor) and collisions (high factor). 0.75 is the default compromise.

Q6) How do you iterate keys and values efficiently?

Answer entrySet() or forEach. Looping keySet and then get(key) does extra lookups.

Q7) TreeMap vs HashMap?

Answer TreeMap keeps keys sorted and offers subMap/headMap. Operations are O(log n). Keys must be comparable.

Simple Programs

First unique character with LinkedHashMap

import java.util.LinkedHashMap;
import java.util.Map;

public class FirstUnique {
    static char firstUnique(String s) {
        Map<Character, Integer> map = new LinkedHashMap<>();
        for (int i = 0; i < s.length(); i++) {
            map.merge(s.charAt(i), 1, Integer::sum);
        }
        for (Map.Entry<Character, Integer> e : map.entrySet()) {
            if (e.getValue() == 1) return e.getKey();
        }
        return '-';
    }

    public static void main(String[] args) {
        System.out.println(firstUnique("swiss")); // w
    }
}

Problem Solving Tricks

computeIfAbsent(k, key -> new ArrayList<>()).add(v) is the grouping idiom (or Collectors.groupingBy).
Pre-size: new HashMap<>(expected / 0.75f + 1) when you know n and want to avoid resize.
For multi-thread counters, chm.merge(k, 1, Integer::sum) or LongAdder values.
Print a map with map.toString() in demos; in APIs iterate entrySet.

Practice Programs List

Count word frequencies from a sentence (split on spaces).
Invert a Map to Map>.
Use TreeMap to print keys in sorted order and query subMap.
Show that a mutable key is lost after you change a field used in hashCode.
Rewrite a two-loop “group anagrams” using computeIfAbsent and sorted-character keys.