JA
Tiếng Việt한국어DeutschEspañolPortuguêsFrançaisEnglish日本語简体中文
ホーム / 基礎 / アルゴリズム

JavaのHashMapで数え上げ問題を効率よく解く

Cris The Dev · 2026/10/06 · 7 分で読めます · 111

1. 概要

数え上げ問題（counting problem）はプログラミング面接やアルゴリズムで頻出です。文字の頻度カウント、最頻出要素の探索、条件を満たすペアのカウント、同じ性質の要素をグループ化するなど、いろいろな場面に登場します。こうした問題を解くときにHashMapはほぼ「デフォルト」の選択肢になります。検索も更新も平均的には O(1) で実行できるからです。

このレッスンを読み終わると、HashMap（とMap.merge、getOrDefault）を使った 4 つの頻出な数え上げパターンを解けるようになります。それぞれの時間計算量・空間計算量を理解し、HashMapを使う際によくあるトラップを回避できるようになるでしょう。

2. なぜHashMapが数え上げ問題に向いているのか

数え上げ問題の基本的なアイデア：各要素について「何回見かけたか」や「見かけたか未か」という情報が必要になります。HashMap<K, V>はそのために以下を提供します。

  • キーの検索が O(1) 平均 — ソートが不要。
  • キーに対応する値の更新（カウント増加）が O(1) 平均。
  • containsKeyまたは値で「見かけたかどうか」を管理できる。

値の範囲が小さく事前に決まっている場合のみ使える配列カウント（counting array、例えば文字 a-z）と異なり、HashMapはより汎用的です。キーはString、Integer、任意のオブジェクトになります。

3. 要素の頻度をカウントする

3.1. getOrDefaultを使う方法

リスト内の各要素の出現回数を数えるときの定番パターンです。

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)は、wordがすでに存在すればその値を、なければ0を返します。if (map.containsKey(...)) という条件分岐を書かずにすみます。["cam", "xoai", "cam", "cam", "xoai"] という入力なら結果は以下のようになります。

{cam=3, xoai=2}

3.2. Map.mergeでもっとシンプルに

Java 8 以降、Map.mergeを使うと確認と更新を 1 行で書けます。

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) の動作：word がなければ値を1に設定、あれば古い値にInteger::sumで1を足します。わずかに高速ですし、加算ロジックがシンプルなら読みやすくなります。

3.3. 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);
    }
}

注意： getOrDefaultはキーが存在しない場合、map を変更しません。単に読み取るだけです。putIfAbsentと混同しないようにしましょう。putIfAbsentはキーがまだないときにだけ値をセットします。

4. 最頻出要素を探す

頻度テーブルが手に入ったら、最頻出要素を探すのは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()は entry を値（出現回数）で比較します。.max(...) で最大値を持つ entry を取得し、.map(Map.Entry::getKey) でキーだけを抽出します。複数の要素が同数最多の場合、maxはそのうち 1 つだけを返します。HashMapは挿入順序を保持しないので、結果の順序は保証されません。

入力：{cam=3, xoai=2}
出力：Optional[cam]

注意： 複数の最頻出要素がある場合でも結果を安定させたいなら、HashMapではなくLinkedHashMapを使ってください。

5. 条件を満たすペアの個数をカウントする（Two Sum のカウント版）

よくある応用：arr[i] + arr[j] == target となるペア (i, j) の個数を数える問題です。ブルートフォース O(n²) ではなく、HashMapを使って 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;
    }
}

各行の説明：

  • complement = target - number：number に足して target になる値。
  • count += seen.getOrDefault(complement, 0)：これまでに見かけた complement の個数を加えます。その分だけペアが成立します。
  • seen.merge(number, 1, Integer::sum)：現在の number をカウント用テーブルに記録します。後から来た要素と組ペアになるように。

numbers = [1, 2, 3, 2, 4]、target = 5 の例では、ペアは (1,4)、(2,3)、(3,2) になります。テストで確認してみましょう。

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

3 つのペアは：数字3に出会ったときの (2,3)、2 番目の2に出会ったときの (2,3)（すでに見かけた3とのペア）、そして4に出会ったときの (1,4) です。

6. 同じ性質の要素をグループ化する（アナグラム）

より高度な数え上げ：アナグラム（同じ文字からなるが順序が異なる単語）を 1 つにグループ化し、グループ数や各グループのサイズをカウントするパターンです。

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

ポイントはsignatureです。各単語の文字をソートすることで、すべてのアナグラムに共通の「署名」を作ります。computeIfAbsent(signature, key -> new ArrayList<>()) は署名がまだ map にないなら新しいリストを作成し、その後に単語を追加します。

入力 ["eat", "tea", "tan", "ate", "nat", "bat"] の場合、結果は以下のようになります。

{
  "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 は手作業で containsKey + put を書くより洗練されています。値が collection で遅延初期化（lazy init）が必要な場合は特に重宝します。

7. 時間計算量と空間計算量

問題 時間計算量 空間計算量
頻度をカウント O(n) O(k)（k は異なる要素数）
最頻出要素を探す O(n) O(k)
合計が target のペアをカウント O(n) O(n)
アナグラムをグループ化 O(n · m log m)（m は最長の単語の長さ） O(n)

事前にソート → スキャンする方法（O(n log n)）と比べると、HashMap は時間計算量が有利ですが、その代わり O(n) や O(k) の追加メモリを消費します。メモリが厳しく制約されていて、値の範囲が小さく限定されている場合は、配列カウント（counting array）のほうが軽量です。

8. よくあるミス

  • ミュータブルなオブジェクトをキーにして equals/hashCode をオーバーライドしていない：自分で定義したクラス（例えばPoint）をキーにしてカウントする場合、これら 2 つのメソッドをオーバーライドし忘れると、HashMap は「中身が同じ」 2 つのオブジェクトを同じキーとして認識しません。
public record Point(int x, int y) {}

record を使えば、全フィールドから自動的に正しい equals/hashCode が生成されます。このミスを完全に防げます。

  • 反復順序が保証されていることを期待する：HashMap は順序を保証しません。挿入順序を保持したければLinkedHashMapを、キーでソート済みの順序が必要ならTreeMapを使ってください。

  • イテレーション中に map を修正する：entrySet()をループしながら要素を削除するとConcurrentModificationExceptionが発生します。削除が必要ならIterator.remove()かremoveIfを使いましょう。

  • 大規模ループで Integer の自動ボックス化に注意：getOrDefault + + 1 のたびに、自動ボックス化で新しいIntegerオブジェクトが作られます。非常に大規模なデータ（数百万要素）の場合は、Map<String, int[]> やプリミティブ型マップライブラリ（例えば Eclipse Collections）を検討してオーバーヘッドを削減してください。

注意： キーの範囲が 26 個の文字 a-z、または小さな決まった整数範囲に限定されるなら、配列（int[26]）のほうが常に高速でメモリ効率も良いです。キーの範囲が大きく事前に未決定、あるいは非連続な場合にだけHashMapを使いましょう。

9. まとめ

HashMap により、数え上げ問題（頻度カウント、目立つ要素の抽出、ペアカウント、同じ要素のグループ化）は O(1) の検索のおかげでシンプルな O(n) ループに変わります。getOrDefault、merge、computeIfAbsent といったメソッドを使えば、手作業で containsKey をチェックする場合よりもコードが短く明確になります。忘れずに：HashMap は挿入順序を保持しません、キーがオブジェクトなら正しい equals/hashCode が必要です、そして値の範囲が小さいなら配列カウントもまだ軽量な選択肢です。

algorithmsjavahashmapdata-structuresinterview
著者のアプリHoanTien.proCashback on Shopee, TikTok Shop and Lazada (Vietnam)iOS · Android · Web

同じトピックの記事