Hash Map giải bài toán đếm trong Java

1. Tổng quan

Bài toán đếm (counting problem) xuất hiện khắp nơi: đếm tần suất ký tự, tìm phần tử xuất hiện nhiều nhất, đếm số cặp thỏa điều kiện, nhóm các phần tử giống nhau. HashMap là công cụ gần như “mặc định” cho nhóm bài này vì tra cứu và cập nhật đều O(1) trung bình.

Đọc xong bài này, bạn sẽ biết cách dùng HashMap (và Map.merge, getOrDefault) để giải 4 dạng bài đếm phổ biến, hiểu độ phức tạp thời gian/không gian, và tránh được vài lỗi hay gặp khi dùng HashMap trong bài toán đếm.

2. Vì sao HashMap phù hợp cho bài toán đếm

Ý tưởng chung của bài toán đếm: với mỗi phần tử, bạn cần biết “đã gặp bao nhiêu lần” hoặc “đã gặp chưa”. HashMap<K, V> cho bạn:

Tra cứu key trong O(1) trung bình — không cần sort.
Cập nhật giá trị (tăng counter) trong O(1) trung bình.
Lưu trạng thái “đã thấy” bằng containsKey hoặc giá trị đếm > 0.

So với mảng đếm (counting array) chỉ dùng được khi miền giá trị nhỏ và biết trước (ví dụ ký tự a-z), HashMap tổng quát hơn: key có thể là String, Integer, object tùy ý.

3. Đếm tần suất phần tử

3.1. Dùng getOrDefault

Đây là cách kinh điển để đếm tần suất từng phần tử trong một danh sách.

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) trả về giá trị hiện tại nếu word đã tồn tại, hoặc 0 nếu chưa — tránh phải viết if (map.containsKey(...)). Với danh sách ["cam", "xoai", "cam", "cam", "xoai"], kết quả là:

{cam=3, xoai=2}

3.2. Dùng Map.merge (ngắn hơn)

Từ Java 8, Map.merge gộp bước kiểm tra và cập nhật thành một lời gọi.

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) nghĩa là: nếu word chưa có, đặt giá trị 1; nếu đã có, lấy giá trị cũ cộng với 1 qua hàm Integer::sum. Cách này nhanh hơn một chút và đọc tự nhiên hơn khi logic cộng dồn đơn giản.

3.3. Test với 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);
    }
}

Lưu ý: getOrDefault không chỉnh sửa map nếu key chưa tồn tại — nó chỉ đọc. Đừng nhầm với putIfAbsent, vốn dùng để gán giá trị mặc định khi key chưa có.

4. Tìm phần tử xuất hiện nhiều nhất

Sau khi có bảng tần suất, tìm phần tử xuất hiện nhiều nhất chỉ là một lượt duyệt 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() so sánh các entry theo value (số lần xuất hiện), .max(...) lấy entry có value lớn nhất. Nếu có nhiều phần tử đồng hạng nhất, max chỉ trả về một trong số đó — thứ tự không đảm bảo vì HashMap không giữ thứ tự chèn.

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

Lưu ý: Nếu cần giữ thứ tự chèn để kết quả ổn định khi có nhiều phần tử đồng hạng, dùng LinkedHashMap thay cho HashMap.

5. Đếm cặp phần tử thỏa điều kiện (Two Sum dạng đếm)

Một biến thể phổ biến: đếm số cặp (i, j) sao cho arr[i] + arr[j] == target. Thay vì brute-force O(n²), dùng HashMap để giảm xuống O(n).

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;
    }
}

Giải thích từng dòng:

complement = target - number: giá trị cần tìm để cộng với number ra target.
count += seen.getOrDefault(complement, 0): cộng thêm số lần complement đã xuất hiện trước đó — mỗi lần như vậy tạo ra một cặp hợp lệ.
seen.merge(number, 1, Integer::sum): ghi nhận number hiện tại vào bảng đếm, để các phần tử sau có thể ghép cặp với nó.

Với numbers = [1, 2, 3, 2, 4] và target = 5: các cặp là (1,4), (2,3), (3,2) → nhưng vì ta chỉ đếm theo thứ tự xuất hiện trước, hãy kiểm tra bằng 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);
    }
}

Ba cặp đó là: (2,3) lúc gặp số 3, (2,3) lúc gặp số 2 thứ hai (ghép với 3 đã thấy), và (1,4) lúc gặp số 4.

6. Nhóm các phần tử giống nhau (Anagram Groups)

Một bài toán đếm nâng cao hơn: nhóm các từ là anagram của nhau (cùng tập ký tự, khác thứ tự), rồi đếm số nhóm hoặc số phần tử mỗi nhóm.

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;
    }
}

Điểm mấu chốt nằm ở signature: sắp xếp ký tự của mỗi từ để tạo ra một “chữ ký” chung cho mọi anagram. computeIfAbsent(signature, key -> new ArrayList<>()) tạo danh sách mới nếu chữ ký chưa có key, rồi thêm từ hiện tại vào.

Với đầu vào ["eat", "tea", "tan", "ate", "nat", "bat"], kết quả:

{
  "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 là phương án sạch hơn containsKey + put thủ công, đặc biệt khi value là collection cần khởi tạo lười (lazy init).

7. Độ phức tạp thời gian và không gian

Bài toán	Thời gian	Không gian
Đếm tần suất	O(n)	O(k) — k là số phần tử phân biệt
Tìm phần tử nhiều nhất	O(n)	O(k)
Đếm cặp có tổng target	O(n)	O(n)
Nhóm anagram	O(n · m log m) — m là độ dài từ dài nhất	O(n)

So với giải pháp dùng sort trước rồi duyệt (O(n log n)), HashMap thường nhanh hơn ở độ phức tạp thời gian nhưng đổi lại tốn thêm không gian O(n) hoặc O(k). Nếu bộ nhớ là ràng buộc chặt và miền giá trị nhỏ, mảng đếm (counting array) vẫn là lựa chọn tiết kiệm hơn.

8. Lỗi hay gặp

Dùng key là mutable object mà không override equals/hashCode: nếu bạn đếm theo một class tự định nghĩa (ví dụ Point), quên override hai phương thức này khiến HashMap không nhận ra hai object “giống nhau” là cùng một key.

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

Dùng record giúp tự động có equals/hashCode đúng dựa trên tất cả field — tránh hẳn lỗi này.

Kỳ vọng thứ tự lặp (iteration order) ổn định: HashMap không đảm bảo thứ tự. Nếu cần thứ tự chèn, dùng LinkedHashMap; nếu cần thứ tự tăng dần theo key, dùng TreeMap.
Sửa đổi map khi đang duyệt entrySet(): gây ConcurrentModificationException. Nếu cần loại bỏ entry trong lúc duyệt, dùng Iterator.remove() hoặc removeIf.
Dùng Integer boxing không cẩn thận trong vòng lặp lớn: mỗi lần getOrDefault + + 1 tạo ra object Integer mới do auto-boxing. Với dữ liệu rất lớn (hàng triệu phần tử), xem xét Map<String, int[]> hoặc thư viện primitive map (ví dụ Eclipse Collections) để giảm overhead.

Lưu ý: Nếu miền key chỉ là 26 ký tự a-z hoặc một khoảng số nguyên nhỏ cố định, mảng (int[26]) luôn nhanh hơn và tốn ít bộ nhớ hơn HashMap. Chỉ dùng HashMap khi miền key lớn, không biết trước, hoặc không liên tục.

9. Kết luận

HashMap biến các bài toán đếm — đếm tần suất, tìm phần tử nổi bật, đếm cặp, nhóm phần tử giống nhau — thành những vòng lặp O(n) đơn giản nhờ tra cứu O(1). Các phương thức getOrDefault, merge, computeIfAbsent giúp code ngắn và rõ ý hơn so với kiểm tra containsKey thủ công. Hãy nhớ: HashMap không giữ thứ tự, cần equals/hashCode đúng cho key là object, và với miền giá trị nhỏ, mảng đếm vẫn là lựa chọn gọn nhẹ hơn.