Gruppieren & Deduplizieren
Map<K, List<V>>, um nach einem berechneten Schlüssel zu gruppieren, und Sets, um in O(1) zu deduplizieren oder 'schon gesehen' zu erkennen.
Deutsche Übersetzung in Arbeit
Diese Lektion ist noch nicht ins Deutsche übersetzt und wird daher auf Englisch angezeigt. Der Rest der Seite ist vollständig lokalisiert.
Auf dieser Seite
Two more everyday hashing moves round out the toolkit: grouping items that share some property, and de-duplicating or detecting "have I seen this before." Both turn nested-loop O(n²) solutions into single-pass O(n) ones, and both come up constantly.
Grouping with a list-valued map
To bucket items by a computed key, use a Map<K, List<V>> and computeIfAbsent to lazily create each
group's list. The classic example is grouping anagrams by their sorted-letter signature:
// group anagrams — words that sort to the same key belong together
Map<String, List<String>> groups = new HashMap<>();
for (String word : words) {
char[] c = word.toCharArray();
Arrays.sort(c);
String key = new String(c); // "eat" and "tea" → "aet"
groups.computeIfAbsent(key, k -> new ArrayList<>()).add(word);
}
return new ArrayList<>(groups.values()); // each value is one groupThe pattern is always the same: compute a key that collides exactly when items should group, then append to that key's list. Grouping "by first letter," "by remainder mod k," or "by frequency signature" all follow this shape.
De-duplication and "seen before" with a set
A HashSet answers membership in O(1). Its add returns false if the element was already present,
which makes duplicate detection a one-liner:
// does the array contain any duplicate? — O(n)
boolean hasDuplicate(int[] a) {
Set<Integer> seen = new HashSet<>();
for (int x : a)
if (!seen.add(x)) return true; // add returns false → already seen
return false;
}Sets also dedupe a collection instantly (new HashSet<>(list) drops repeats), and power any "process
each distinct value once" or "have I visited this node?" logic - which is exactly how graph traversals
avoid revisiting nodes (coming up in the graphs module).
Set operations are built in
Java sets support the mathematical operations directly: a.retainAll(b) is intersection, a.addAll(b)
is union, a.removeAll(b) is difference. For 'elements common to two lists' or 'in A but not B,' a
set plus one of these methods beats writing nested loops.
A mail sorter doesn't compare every letter to every other to group them by street - that's O(n²). Instead each letter's address maps to a pigeonhole, and the letter drops straight in; letters for the same street pile up in the same hole automatically. Grouping with a hash map is exactly this: the computed key is the address, the map value is the pigeonhole, and one pass sorts everything into its group. A set is the same idea with just one slot per key - useful when you only care whether a slot is occupied.
You have a list of strings and want to group them by their length. Describe the map type and the key you'd use, and the complexity - then explain how you'd instead just count how many distinct lengths appear.
What is the standard way to detect whether an array contains a duplicate in O(n)?
Key takeaways
- Group items with a Map<K, List<V>>: compute a key that collides exactly when items should group, then append via computeIfAbsent.
- Anagram grouping keys on the sorted-letter signature; other groupings key on any computed property.
- A HashSet gives O(1) membership; add returns false on a repeat, making duplicate detection a one-liner.
- Sets dedupe a collection instantly and power 'seen before' / 'visited' logic (e.g. graph traversal).
- Built-in set operations (retainAll, addAll, removeAll) give intersection, union, and difference without nested loops.