HashMap & HashSet API

HashMap Core Methods

put, get, remove, containsKey, containsValue, size, isEmpty. Power methods: getOrDefault (safe null-free get), putIfAbsent (only write if missing), merge (count/accumulate), replace, compute, computeIfAbsent.

O(1) average per op

O(n)

How It Works

Java's HashMap core operations — put, get, remove, containsKey, size, isEmpty — all run in O(1) average time by hashing the key to a bucket; containsValue is the exception at O(n) since values are not indexed. Keys hash into an array of bins, with collisions handled by chaining, and bins converting to red-black trees when chains grow long, capping worst-case lookups at O(log n).

The power methods eliminate boilerplate around missing keys: getOrDefault(k, d) avoids null checks, putIfAbsent writes only when the key is new, merge(k, 1, Integer::sum) is the idiomatic one-line frequency counter, and compute/computeIfAbsent build or transform values in place. Mastering these turns most counting and grouping patterns into single statements.

Step-by-Step Visualization

put(key, val) — insert or overwrite. O(1) average

put

get

remove

containsKey

getOrDefault

merge

map{a: 1}

1/4

Code

Java

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

// ─── Core CRUD — all O(1) average ────────────────────────────
map.put("a", 1);       // write / overwrite
map.get("a");          // read (null if missing)
map.remove("a");       // delete
map.containsKey("a");  // O(1) key check
map.containsValue(1);  // O(n) — scans all values!
map.size();            // number of entries
map.isEmpty();         // true if empty

// ─── Safer / smarter operations ──────────────────────────────
map.getOrDefault("b", 0);       // 0 instead of null — use this, not get()
map.putIfAbsent("c", 5);        // only writes if key is absent
map.replace("a", 42);           // update only if key already exists
map.merge("a", 1, Integer::sum);// merge(key, val, fn) — best freq counter

// ─── Compute patterns ────────────────────────────────────────
map.compute("a", (k, v) -> v == null ? 1 : v + 1);
map.computeIfAbsent("list", k -> new ArrayList<>()).add("item");

Tips & Gotchas

1getOrDefault(key, 0) is safer than get() — avoids null checks

2merge(key, 1, Integer::sum) is the cleanest frequency counter

3putIfAbsent returns the existing value (or null), doesn't overwrite

4computeIfAbsent(key, k -> new ArrayList<>()) for grouping patterns

Practice Problems

1Two Sum
2Contains Duplicate II
3Isomorphic Strings
4Word Pattern
5First Unique Character in a String

About the HashMap & HashSet API Pattern

The complete Java API for HashMap and HashSet — constructors, every core method, iteration patterns, and set-based conversions. These are your building blocks for every hash-based problem.

Key insight

If brute force is O(n²) because of a nested search, a hash map usually drops it to O(n). The tradeoff is O(n) extra space.

Common Hash Map Interview Problems

Two Sum
Subarray Sum Equals K
Top K Frequent Elements
LRU Cache
Group Anagrams
Longest Consecutive Sequence

Frequently Asked Questions

What is the cleanest way to count frequencies in Java?

Use map.merge(key, 1, Integer::sum), which inserts 1 for a new key and adds 1 to an existing count in one call. The equivalent map.put(key, map.getOrDefault(key, 0) + 1) also works but performs two hash lookups instead of one.

Why does get return null and how do I code around it?

HashMap returns null for absent keys, which risks NullPointerException when unboxing to int or chaining calls. Prefer getOrDefault for reads with a fallback, containsKey when null values are legal in the map, and computeIfAbsent when you want to create the value on first access.

Is containsValue as fast as containsKey?

No. containsKey hashes straight to the right bucket in O(1) average time, but containsValue must scan every entry, costing O(n). If value lookups are frequent, maintain a second reverse map from value to key.