Hashing and Counting in Java
HashMap, merge and computeIfAbsent, why an int array beats a map for characters, and the autoboxing tax that makes Java counting slower than a plain array.
Hashing turns a nested scan into a single pass. In Java it also turns every count into a boxed object, which is the part worth measuring.
The pattern: seen-before in one pass
import java.util.*;
public class Duplicates {
static boolean bruteHasDuplicate(int[] nums) {
for (int i = 0; i < nums.length; i++)
for (int j = i + 1; j < nums.length; j++)
if (nums[i] == nums[j]) return true;
return false;
}
static boolean hashedHasDuplicate(int[] nums) {
Set<Integer> seen = new HashSet<>();
for (int n : nums) if (!seen.add(n)) return true; // add returns false if present
return false;
}
public static void main(String[] args) {
int[] nums = new int[30_000];
for (int i = 0; i < nums.length; i++) nums[i] = i; // worst case: no duplicate
long t0 = System.nanoTime();
boolean a = bruteHasDuplicate(nums);
long t1 = System.nanoTime();
boolean b = hashedHasDuplicate(nums);
long t2 = System.nanoTime();
System.out.printf("brute O(n^2) %8.2f ms %s%n", (t1-t0)/1e6, a);
System.out.printf("hashed O(n) %8.2f ms %s%n", (t2-t1)/1e6, b);
System.out.printf("speedup: %.0fx%n", (double)(t1-t0)/(t2-t1));
}
}$ java Duplicates.java
brute O(n^2) 198.44 ms false
hashed O(n) 3.12 ms false
speedup: 64xseen.add(n) returning false when the element was already present is the Java idiom — it
replaces the contains check plus add, which hashes twice.
Four ways to count, one of them idiomatic
import java.util.*;
import java.util.stream.Collectors;
public class Counting {
public static void main(String[] args) {
String[] words = "the quick brown fox jumps over the lazy dog the end".split(" ");
Map<String, Integer> a = new HashMap<>();
for (String w : words) {
if (a.containsKey(w)) a.put(w, a.get(w) + 1); // 3 hashes per hit
else a.put(w, 1);
}
Map<String, Integer> b = new HashMap<>();
for (String w : words) b.put(w, b.getOrDefault(w, 0) + 1); // 2 hashes
Map<String, Integer> c = new HashMap<>();
for (String w : words) c.merge(w, 1, Integer::sum); // 1 hash, idiomatic
Map<String, Long> d = Arrays.stream(words)
.collect(Collectors.groupingBy(w -> w, Collectors.counting()));
System.out.println("containsKey " + new TreeMap<>(a));
System.out.println("getOrDefault " + new TreeMap<>(b));
System.out.println("merge " + new TreeMap<>(c));
System.out.println("stream " + new TreeMap<>(d));
System.out.println("all equal: " + (a.equals(b) && b.equals(c)));
}
}$ java Counting.java
containsKey {brown=1, dog=1, end=1, fox=1, jumps=1, lazy=1, over=1, quick=1, the=3}
getOrDefault {brown=1, dog=1, end=1, fox=1, jumps=1, lazy=1, over=1, quick=1, the=3}
merge {brown=1, dog=1, end=1, fox=1, jumps=1, lazy=1, over=1, quick=1, the=3}
stream {brown=1, dog=1, end=1, fox=1, jumps=1, lazy=1, over=1, quick=1, the=3}
all equal: trueNote the TreeMap wrapper in every print. Without it the output order is HashMap order, which
is unspecified — the lesson would print something different on another JDK. That is not a
formatting nicety; an answer that depends on HashMap iteration order is wrong.
merge(w, 1, Integer::sum) reads as “put 1, or combine with what is there”. It is the shortest
correct form and the one to reach for.
Grouping: computeIfAbsent
import java.util.*;
public class Anagrams {
static Collection<List<String>> group(String[] words) {
Map<String, List<String>> buckets = new HashMap<>();
for (String w : words) {
char[] chars = w.toCharArray();
Arrays.sort(chars);
String key = new String(chars);
buckets.computeIfAbsent(key, k -> new ArrayList<>()).add(w);
}
return buckets.values();
}
public static void main(String[] args) {
System.out.println(group(new String[]{"eat","tea","tan","ate","nat","bat"}));
}
}$ java Anagrams.java
[[bat], [tan, nat], [eat, tea, ate]]computeIfAbsent(key, k -> new ArrayList<>()).add(w) is the Java equivalent of Python’s
defaultdict(list). The alternative spelling creates a throwaway list on every iteration:
buckets.putIfAbsent(key, new ArrayList<>()); // allocates even when the key exists
buckets.get(key).add(w);Both are correct; only one avoids the wasted allocation. Saying which and why is the difference between knowing the API and knowing what it costs.
The counting key: sorting versus a 26-slot array
import java.util.*;
public class AnagramKey {
static String sortKey(String w) {
char[] c = w.toCharArray();
Arrays.sort(c);
return new String(c); // O(k log k)
}
static String countKey(String w) {
int[] counts = new int[26];
for (char c : w.toCharArray()) counts[c - 97]++; // 97 is 'a'; assumes lowercase
return Arrays.toString(counts); // O(k)
}
public static void main(String[] args) {
String[] words = new String[200_000];
Random rnd = new Random(1);
for (int i = 0; i < words.length; i++) {
char[] c = new char[12];
for (int j = 0; j < 12; j++) c[j] = (char)(97 + rnd.nextInt(26));
words[i] = new String(c);
}
long t0 = System.nanoTime();
for (String w : words) sortKey(w);
long t1 = System.nanoTime();
for (String w : words) countKey(w);
long t2 = System.nanoTime();
System.out.printf("sort key %7.1f ms%n", (t1-t0)/1e6);
System.out.printf("count key %7.1f ms%n", (t2-t1)/1e6);
System.out.println("same grouping: " +
sortKey("listen").equals(sortKey("silent")) + " / " +
countKey("listen").equals(countKey("silent")));
}
}$ java AnagramKey.java
sort key 88.6 ms
count key 54.1 ms
same grouping: true / trueThe count key is O(k) rather than O(k log k), and for twelve-character words that is a modest
win — worth stating honestly rather than overselling. What it is not is safe for arbitrary
input: subtracting 97 throws ArrayIndexOutOfBoundsException on an uppercase letter or a space.
“I would use the counting key if the constraints say lowercase English letters, and say that assumption out loud. Otherwise sorting is safer, and for short words the difference is small.”
The autoboxing tax — where a map loses to a plain array
import java.util.*;
public class BoxingTax {
public static void main(String[] args) {
int n = 3_000_000;
int[] data = new Random(7).ints(n, 0, 1000).toArray();
long t0 = System.nanoTime();
Map<Integer, Integer> map = new HashMap<>();
for (int v : data) map.merge(v, 1, Integer::sum);
long t1 = System.nanoTime();
int[] arr = new int[1000];
for (int v : data) arr[v]++;
long t2 = System.nanoTime();
System.out.printf("HashMap<Integer,Integer> %7.1f ms%n", (t1-t0)/1e6);
System.out.printf("int[1000] %7.1f ms%n", (t2-t1)/1e6);
System.out.printf("ratio: %.1fx%n", (double)(t1-t0)/(t2-t1));
System.out.println("same answer for key 500: " + map.get(500) + " / " + arr[500]);
}
}$ java BoxingTax.java
HashMap<Integer,Integer> 241.7 ms
int[1000] 8.3 ms
ratio: 29.1x
same answer for key 500: 3033 / 3033Twenty-nine times. Both are O(n); the constant is the whole story. Each merge boxes the key,
hashes it, follows a reference to a node, unboxes the value, adds, and boxes the result. The
array does one bounds check and one increment.
“Both are O(n). The map pays for boxing, hashing, and pointer chasing on every element. When the key space is small and dense — bounded integers, ASCII, lowercase letters — I use an array and note the assumption. When it is not, the map is the right structure and 240 ms for three million elements is fine.”
That framing matters: this is not “avoid HashMap”. It is “know which one the constraints
allow”.
Two-sum, first-unique, anagram
import java.util.*;
public class Patterns {
static int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> seen = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
Integer j = seen.get(target - nums[i]); // Integer, not int
if (j != null) return new int[]{j, i};
seen.put(nums[i], i);
}
return null;
}
static int firstUniqChar(String s) {
int[] counts = new int[128];
for (char c : s.toCharArray()) counts[c]++;
for (int i = 0; i < s.length(); i++) if (counts[s.charAt(i)] == 1) return i;
return -1;
}
static boolean isAnagram(String a, String b) {
if (a.length() != b.length()) return false; // cheap reject first
int[] counts = new int[128];
for (int i = 0; i < a.length(); i++) { counts[a.charAt(i)]++; counts[b.charAt(i)]--; }
for (int c : counts) if (c != 0) return false;
return true;
}
public static void main(String[] args) {
System.out.println(Arrays.toString(twoSum(new int[]{2,7,11,15}, 9)));
System.out.println(firstUniqChar("leetcode"));
System.out.println(firstUniqChar("aabb"));
System.out.println(isAnagram("listen", "silent") + " " + isAnagram("rat", "car"));
}
}$ java Patterns.java
[0, 1]
0
-1
true falseisAnagram increments for one string and decrements for the other in a single loop — one pass,
one array, and the length check rejects the common mismatch before any work.
The traps
import java.util.*;
public class Traps {
record Point(int x, int y) {}
static class Bad { int x; Bad(int x) { this.x = x; } }
public static void main(String[] args) {
Map<Integer, Integer> m = new HashMap<>();
m.put(1, 10);
System.out.println("get(2) = " + m.get(2));
try {
int v = m.get(2);
System.out.println(v);
} catch (NullPointerException e) {
System.out.println("unboxing null -> NullPointerException");
}
Set<Point> points = new HashSet<>();
points.add(new Point(1, 2));
System.out.println("record dedupes: " + points.contains(new Point(1, 2)));
Set<Bad> bad = new HashSet<>();
bad.add(new Bad(1));
System.out.println("no equals/hashCode: " + bad.contains(new Bad(1)));
Map<String, Integer> counts = new LinkedHashMap<>();
for (String w : "banana apple cherry apple".split(" ")) counts.merge(w, 1, Integer::sum);
System.out.println("LinkedHashMap: " + counts);
System.out.println("TreeMap (sorted): " + new TreeMap<>(counts));
}
}$ java Traps.java
get(2) = null
unboxing null -> NullPointerException
record dedupes: true
no equals/hashCode: false
LinkedHashMap: {banana=1, apple=2, cherry=1}
TreeMap (sorted): {apple=2, banana=1, cherry=1}Three things to carry:
getreturnsnull, and unboxing it throws. UsegetOrDefault, or hold anInteger.- A custom class without
equals/hashCodenever dedupes.recordgenerates both, which is why records are the right choice for a composite key. A plain class is a silent bug — note thatbad.containsreturnedfalsewithout any error. - Choose the map for the ordering you need.
LinkedHashMapkeeps insertion order,TreeMapkeeps sorted order,HashMappromises neither.
Recognising it
SIGNAL STRUCTURE
"has it appeared before?" HashSet — add() returns false if present
"how many times?" HashMap + merge, or int[] if dense
"group these by something" computeIfAbsent(k, x -> new ArrayList<>())
"pair summing to X", unsorted HashMap of value -> index
"first non-repeating" count pass, then scan in original order
"anagram / permutation" counts array, one increment + one decrement
composite key (pair, coordinate) record — it generates equals and hashCode
need insertion order LinkedHashMap
need sorted keys TreeMap, O(log n) per operationPractice
1. Count with merge and with containsKey.
merge {the=3, ...} one hash per element
containsKey {the=3, ...} three hashes per hitBoth correct. merge(k, 1, Integer::sum) is the idiom, and knowing the hash count is the part
that shows depth.
2. Time a map of boxed integers against int[1000].
HashMap 241.7 ms int[] 8.3 ms 29.1xSame O(n), 29x constant. Boxing, hashing, and pointer chasing versus one increment. Use the array when the key space is small and dense, and say the assumption out loud.
3. Put a class with no equals in a HashSet, then a record.
no equals/hashCode: false
record dedupes: trueIdentity hashing means two equal-looking objects are different keys, and nothing warns you.
record generates both methods — the right default for a composite key.
4. Assign map.get(missing) to an int.
unboxing null -> NullPointerExceptionget returns null for a missing key. Use getOrDefault(k, 0), or hold the result in an
Integer and null-check it — the two-sum solution above does the latter.
Next: sliding window — the fixed and variable forms, and why charAt beats substring.