HashMap löst Zählprobleme in Java

1. Übersicht

Zählprobleme (counting problems) tauchen überall auf: Zählen von Zeichenhäufigkeiten, Finden des häufigsten Elements, Zählen von Paaren, die eine Bedingung erfüllen, und Gruppieren ähnlicher Elemente. HashMap ist das „Standard”-Werkzeug für diese Problemklasse, da sowohl Nachschlag als auch Aktualisierung durchschnittlich O(1) sind.

Nach dem Lesen dieses Artikels wirst du wissen, wie du HashMap (und Map.merge, getOrDefault) verwendest, um 4 häufige Zählprobleme zu lösen, die Zeit-/Raumkomplexität zu verstehen, und häufige Fehler bei der Verwendung von HashMap in Zählproblemen zu vermeiden.

2. Warum HashMap für Zählprobleme geeignet ist

Die allgemeine Idee eines Zählproblems: Für jedes Element musst du wissen, „wie viele Male es bereits vorgekommen ist” oder „ob es vorgekommen ist”. HashMap<K, V> bietet dir:

• Schlüssel-Nachschlag in durchschnittlich O(1) — kein Sortieren nötig.
• Wert aktualisieren (Zähler erhöhen) in durchschnittlich O(1).
• Den Status „gesehen” mit containsKey oder Zählwert > 0 speichern.

Im Gegensatz zu einem Zähl-Array (counting array), das nur funktioniert, wenn der Wertebereich klein und bekannt ist (z. B. Zeichen a–z), ist HashMap allgemeiner: der Schlüssel kann String, Integer oder ein beliebiges Objekt sein.

3. Zählen der Häufigkeit von Elementen

3.1. Mit getOrDefault

Dies ist die klassische Methode, um die Häufigkeit jedes Elements in einer Liste zu zählen.

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

public class FrequencyCounter {

    public static Map<String, Integer> countFrequency(List<String> words) {
        Map<String, Integer> freq = new HashMap<>();
        for (String word : words) {
            freq.put(word, freq.getOrDefault(word, 0) + 1);
        }
        return freq;
    }
}

freq.getOrDefault(word, 0) gibt den aktuellen Wert zurück, wenn word bereits vorhanden ist, oder 0, wenn nicht — erspart dir das Schreiben von if (map.containsKey(...)). Für die Liste ["cam", "xoai", "cam", "cam", "xoai"] ist das Ergebnis:

{cam=3, xoai=2}

3.2. Mit Map.merge (kürzer)

Ab Java 8 kombiniert Map.merge den Prüf- und Aktualisierungsschritt in einen Aufruf.

public static Map<String, Integer> countFrequencyMerge(List<String> words) {
    Map<String, Integer> freq = new HashMap<>();
    words.forEach(word -> freq.merge(word, 1, Integer::sum));
    return freq;
}

freq.merge(word, 1, Integer::sum) bedeutet: wenn word noch nicht vorhanden ist, setze den Wert auf 1; wenn bereits vorhanden, addiere den alten Wert zu 1 über die Funktion Integer::sum. Dieser Weg ist etwas schneller und liest sich natürlicher, wenn die Akkumulationslogik einfach ist.

3.3. Test mit JUnit 5 + AssertJ

import org.junit.jupiter.api.Test;
import java.util.List;
import java.util.Map;
import static org.assertj.core.api.Assertions.assertThat;

class FrequencyCounterTest {

    @Test
    void shouldCountFrequencyCorrectly() {
        Map<String, Integer> result = FrequencyCounter.countFrequency(
                List.of("cam", "xoai", "cam", "cam", "xoai"));

        assertThat(result)
                .containsEntry("cam", 3)
                .containsEntry("xoai", 2);
    }
}

Hinweis: getOrDefault ändert die Map nicht, wenn der Schlüssel nicht vorhanden ist — es liest nur. Verwechsle es nicht mit putIfAbsent, das einen Standardwert setzt, wenn der Schlüssel noch nicht vorhanden ist.

4. Finden des Elements mit der höchsten Häufigkeit

Nachdem du die Häufigkeitstabelle hast, ist das Finden des Elements mit der höchsten Häufigkeit nur ein Durchlauf durch entrySet().

import java.util.Map;
import java.util.Optional;

public class MostFrequentFinder {

    public static Optional<String> findMostFrequent(Map<String, Integer> freq) {
        return freq.entrySet().stream()
                .max(Map.Entry.comparingByValue())
                .map(Map.Entry::getKey);
    }
}

Map.Entry.comparingByValue() vergleicht die Einträge nach Wert (Häufigkeit), .max(...) nimmt den Eintrag mit dem größten Wert. Wenn es mehrere Elemente mit der gleichen höchsten Häufigkeit gibt, gibt max nur eines zurück — die Reihenfolge ist nicht garantiert, da HashMap die Einfügungsreihenfolge nicht beibehält.

Input:  {cam=3, xoai=2}
Output: Optional[cam]

Hinweis: Wenn du die Einfügungsreihenfolge beibehalten möchtest, um ein stabiles Ergebnis zu erhalten, wenn es mehrere Elemente mit der gleichen höchsten Häufigkeit gibt, verwende LinkedHashMap statt HashMap.

5. Zählen von Elementpaaren, die eine Bedingung erfüllen (Two Sum Zählen)

Eine häufige Variante: Zähle die Anzahl der Paare (i, j) so dass arr[i] + arr[j] == target. Anstatt Brute-Force O(n²) zu verwenden, nutze HashMap, um auf O(n) zu reduzieren.

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

public class PairCounter {

    public static int countPairsWithSum(int[] numbers, int target) {
        Map<Integer, Integer> seen = new HashMap<>();
        int count = 0;

        for (int number : numbers) {
            int complement = target - number;
            count += seen.getOrDefault(complement, 0);
            seen.merge(number, 1, Integer::sum);
        }
        return count;
    }
}

Erklärung Zeile für Zeile:

• complement = target - number: der Wert, der zusammen mit number target ergibt.
• count += seen.getOrDefault(complement, 0): addiere die Anzahl, wie oft complement zuvor vorgekommen ist — jedes Mal bildet das ein gültiges Paar.
• seen.merge(number, 1, Integer::sum): vermerke number in der Zähltabelle, damit zukünftige Elemente sich mit ihm paaren können.

Mit numbers = [1, 2, 3, 2, 4] und target = 5: die Paare sind (1,4), (2,3), (3,2) → aber da wir nur nach Reihenfolge des vorherigen Auftretens zählen, überprüfe es mit einem Test.

import org.junit.jupiter.api.Test;
import static org.assertj.core.api.Assertions.assertThat;

class PairCounterTest {

    @Test
    void shouldCountPairsWithGivenSum() {
        int[] numbers = {1, 2, 3, 2, 4};

        int result = PairCounter.countPairsWithSum(numbers, 5);

        assertThat(result).isEqualTo(3);
    }
}

Die drei Paare sind: (2,3) wenn wir auf 3 treffen, (2,3) wenn wir auf die zweite 2 treffen (mit der bereits gesehenen 3 gepaart), und (1,4) wenn wir auf 4 treffen.

6. Gruppieren ähnlicher Elemente (Anagramm-Gruppen)

Ein fortgeschritteneres Zählproblem: Gruppiere Wörter, die Anagramme zueinander sind (gleiche Zeichenmenge, unterschiedliche Reihenfolge), und zähle dann die Anzahl der Gruppen oder die Anzahl der Elemente in jeder Gruppe.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class AnagramGrouper {

    public static Map<String, List<String>> groupAnagrams(List<String> words) {
        Map<String, List<String>> groups = new HashMap<>();

        for (String word : words) {
            char[] chars = word.toCharArray();
            Arrays.sort(chars);
            String signature = new String(chars);

            groups.computeIfAbsent(signature, key -> new ArrayList<>())
                  .add(word);
        }
        return groups;
    }
}

Der Schlüsselpunkt liegt bei signature: Sortiere die Zeichen jedes Wortes, um eine gemeinsame „Signatur” für alle Anagramme zu erstellen. computeIfAbsent(signature, key -> new ArrayList<>()) erstellt eine neue Liste, wenn die Signatur noch nicht als Schlüssel vorhanden ist, und fügt dann das aktuelle Wort hinzu.

Für die Eingabe ["eat", "tea", "tan", "ate", "nat", "bat"] ist das Ergebnis:

{
  "aet"=[eat, tea, ate],
  "ant"=[tan, nat],
  "abt"=[bat]
}

import org.junit.jupiter.api.Test;
import java.util.List;
import java.util.Map;
import static org.assertj.core.api.Assertions.assertThat;

class AnagramGrouperTest {

    @Test
    void shouldGroupAnagramsTogether() {
        Map<String, List<String>> groups = AnagramGrouper.groupAnagrams(
                List.of("eat", "tea", "tan", "ate", "nat", "bat"));

        assertThat(groups.values())
                .anySatisfy(group -> assertThat(group).containsExactlyInAnyOrder("eat", "tea", "ate"));
    }
}

computeIfAbsent ist eine sauberere Lösung als manuelle containsKey + put, besonders wenn der Wert eine Collection ist, die lazy initialisiert werden muss.

7. Zeit- und Raumkomplexität

Problem	Zeit	Raum
Häufigkeitszählung	O(n)	O(k) — k ist die Anzahl der unterschiedlichen Elemente
Häufigstes Element finden	O(n)	O(k)
Paare mit Zielssumme zählen	O(n)	O(n)
Anagramme gruppieren	O(n · m log m) — m ist die Länge des längsten Wortes	O(n)

Im Vergleich zu einer Lösung, die zuerst sortiert und dann durchläuft (O(n log n)), ist HashMap normalerweise schneller in der Zeitkomplexität, kostet aber zusätzlich O(n) oder O(k) Speicher. Wenn der Speicher eng begrenzt ist und der Wertebereich klein ist, bleibt ein Zähl-Array (counting array) die speichereffizientere Wahl.

8. Häufige Fehler

• Verwendung eines mutable Objekts als Schlüssel ohne Überschreiben von equals/hashCode: Wenn du mit einer selbst definierten Klasse (z. B. Point) zählst und diese beiden Methoden nicht überschreibst, erkennt HashMap zwei „gleiche” Objekte nicht als denselben Schlüssel an.

public record Point(int x, int y) {}

Die Verwendung von record gibt dir automatisch korrekte equals/hashCode basierend auf alle Felder — vermeidet diesen Fehler komplett.

• Erwartung stabiler Iterationsreihenfolge (iteration order): HashMap garantiert keine Reihenfolge. Wenn du die Einfügungsreihenfolge benötigst, verwende LinkedHashMap; wenn du aufsteigende Reihenfolge nach Schlüssel benötigst, verwende TreeMap.

• Ändern der Map während des Durchlaufs von entrySet(): verursacht ConcurrentModificationException. Wenn du Einträge während des Durchlaufs entfernen musst, verwende Iterator.remove() oder removeIf.

• Sorglose Verwendung von Integer Boxing in großen Schleifen: Jedes Mal getOrDefault + + 1 erstellt ein neues Integer Objekt durch Auto-Boxing. Mit sehr großen Datenmengen (Millionen Elemente) solltest du Map<String, int[]> oder eine primitive Map-Bibliothek (z. B. Eclipse Collections) in Betracht ziehen, um den Overhead zu reduzieren.

Hinweis: Wenn der Schlüsselbereich nur 26 Zeichen a–z oder ein kleines festes Zahlenintervall ist, ist ein Array (int[26]) immer schneller und speichereffizienter als HashMap. Verwende HashMap nur, wenn der Schlüsselbereich groß, unbekannt oder nicht zusammenhängend ist.

9. Fazit

HashMap verwandelt Zählprobleme — Häufigkeitszählung, Finden des herausragendsten Elements, Paarenzählung, Gruppieren ähnlicher Elemente — in einfache O(n) Schleifen dank O(1) Nachschlags. Die Methoden getOrDefault, merge, computeIfAbsent machen den Code kürzer und klarer als manuelle containsKey Prüfungen. Denk dran: HashMap behält die Reihenfolge nicht bei, benötigt korrekte equals/hashCode für Objekt-Schlüssel, und mit kleinem Wertebereich ist ein Zähl-Array immer noch die leichtgewichtigere Wahl.