hashmap で頻度集計
hashmap で頻度集計
このレッスンで分かること
- 配列に同じ値が何回現れるかを知りたい場面は、データ分析の現場でも実装の現場でも頻繁にあります
- 素朴に「ある値が何回出るかを数える」ことを
forの二重ループで書くとO(n^2)になってしまいます- この関数
mostFrequent(arr)は整数の配列を受け取り、最も多く現れた値 を 1 つ返します
hashmap で頻度集計 とは
配列の各要素が何回現れたかを
hashmapで集計し、最も多く出た値を返す関数を実装する。本レッスンでは、hashmap で頻度集計 の基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。
配列に同じ値が何回現れるかを知りたい場面は、データ分析の現場でも実装の現場でも頻繁にあります。アンケートの回答集計、ログのエラーコード集計、テキスト中の単語出現回数など、対象が変わっても 頻度を数える という操作は本質的に同じです。本レッスンでは hashmap (Python の dict、JavaScript の Map / Object、Java の HashMap、Go の map) を使って、配列の頻度集計を O(n) で実装します。
素朴に「ある値が何回出るかを数える」ことを for の二重ループで書くと O(n^2) になってしまいます。1 要素ごとに、配列全体を走査して一致を数えるからです。これを hashmap で 1 パスに置き換えるのが今回のテーマです。
配列の頻度集計は
hashmapの代表例。O(n^2)からO(n)に落とすための基本パターンを身につけよう。
仕様
この関数 mostFrequent(arr) は整数の配列を受け取り、最も多く現れた値 を 1 つ返します。同点が複数ある場合は、最も小さい値 を返すことにします。配列が空のときは -1 を返します。
アルゴリズム
手順は次の通りです。
hashmapを 1 つ用意する (キーは値、バリューは出現回数)- 配列を 1 度だけ走査して、
map[v] = map[v] + 1を行う mapを走査して、最大の頻度を持つ値の中で 最小の値 を選ぶ
各ステップは O(n) なので、合計でも O(n) で済みます。素朴な二重ループの O(n^2) と比べて、要素が 1 万個あれば 1 万倍速くなる計算です。
Mermaid で流れを確認
Python での実装
Python
def mostFrequent(arr):
if not arr:
return -1
freq = {}
for v in arr:
freq[v] = freq.get(v, 0) + 1
best_val = None
best_count = -1
for v, c in freq.items():
if c > best_count or (c == best_count and v < best_val):
best_val = v
best_count = c
return best_valfreq.get(v, 0) は「キーがなければ 0 を返す」という安全なアクセスです。freq[v] だけだと KeyError になります。
JavaScript での実装
JavaScript
function mostFrequent(arr) {
if (arr.length === 0) return -1;
const freq = new Map();
for (const v of arr) {
freq.set(v, (freq.get(v) || 0) + 1);
}
let bestVal = null;
let bestCount = -1;
for (const [v, c] of freq) {
if (c > bestCount || (c === bestCount && v < bestVal)) {
bestVal = v;
bestCount = c;
}
}
return bestVal;
}Map は Object と違い、キーの型を保ったまま保存できます。整数キーをそのまま使えるので、競技プログラミング系の問題と相性が良いです。
よくある間違い
1 つ目は freq[v] = freq[v] + 1 のように、初回アクセス時の undefined を考慮しないケースです。Python なら KeyError、JS なら NaN になります。get(v, 0) や || 0 で初期値を補いましょう。
2 つ目はタイブレークの条件です。同点のときに何を返すか仕様で決めないと、テストが揺れます。本問では「最も小さい値」と決めています。実装時は c == best_count and v < best_val の 両方 をチェックしてください。
3 つ目は空配列です。何も入っていない配列に対して「最頻値」は定義できないので、-1 を返す約束にしています。
集合や辞書の問題では「同点 / 空 / 単一要素」の 3 つのエッジケースを必ず先に考える。
やってみよう
[1, 2, 2, 3, 3]を入力するとどう動くか手で追ってみる。最頻値は2と3で同点なので、より小さい2が返るはず。- 配列の代わりに 文字列 を渡したい場合に書き換えてみる。Python なら
for ch in s:でそのまま動く。 - 同じ集計を 二重ループ でも書いて、計算量の違いを体感する。
頻度集計は
hashmapの超基本。これがスラスラ書けるとgroup byやtwo sumなどの応用が一気に視野に入る。
よくある質問
Q. dict と Counter どちらを使えばよいですか？
A. Python の collections.Counter は頻度集計専用の dict サブクラスです。Counter(arr) の 1 行で集計が完了し、most_common(n) で上位 n 件も取れます。一方、自前で dict を使うと「初回は 0、以降はインクリメント」というロジックが明示されるので、学習目的や細かい条件分岐が必要な場面では dict のほうが見通しが良くなります。実務では Counter を積極的に使いましょう。
Q. キーが存在しないときの安全なアクセス方法は何ですか？
A. Python では freq[v] とすると存在しないキーで KeyError が発生します。freq.get(v, 0) を使うとキーがなければ 0 を返すので安全です。defaultdict(int) も選択肢で、初回アクセス時に自動で 0 をセットします。JavaScript の Map では freq.get(v) || 0 で同じことができます。
Q. 同点（タイブレーク）はどう扱えばよいですか？
A. 仕様次第で変わります。本レッスンでは「最も小さい値を返す」と定めました。実務では「最初に登場した値」「辞書順で先の値」など要件に合わせて決める必要があります。タイブレークが未定義のまま実装すると、入力順次第で結果が変わる非決定的な関数になってしまうので、必ず仕様に明記しましょう。
Q. JavaScript で Map と Object の使い分けは？
A. Object はキーが文字列（または Symbol）に変換されます。整数をキーにすると文字列化されるため、比較や計算に注意が必要です。Map はキーの型を保ったまま格納できるので、整数や配列をキーにしたい場合は Map が適しています。頻度集計で整数の値をキーとして使う本レッスンのようなケースでは Map を選ぶと型が保証されて安全です。
次のレッスン
次は キーでグループ化 で、配列の各要素が何回現れたかを hashmap で集計し、最も多く出た値を返す関数を実装する を学びます。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- 頻度集計 の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. 頻度集計 とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン
要件
- 配列は最大数千要素まで対応すること
- 二重ループ (
O(n^2)) ではなくhashmapを使ったO(n)で実装する - 頻度が同じ値が複数ある場合は、その中で最も小さい値を返す。空配列なら
-1を返す
入出力例
test-cases.txt
mostFrequent([1,2,2,3,3]) → 2
mostFrequent([5,5,5,1,2]) → 5
mostFrequent([7]) → 7
mostFrequent([1,2,3]) → 1
mostFrequent([4,4,3,3,2,2]) → 2
mostFrequent([10,20,10,20,10]) → 10