C++のMapは便利ですが、直感的には少し分かりにくい存在です。
配列とは違い、「値から場所を引く」という考え方が必要になります。
この記事ではGoogleMapを例に、Mapの仕組みをイメージしやすく整理します。
ハッシュ値や「値が番地になる」という考え方も含めて解説します。
Contents
Mapとは何か
Mapとは、キーと値をセットで管理するデータ構造です。
C++では主に std::map と std::unordered_map の2種類が使われます。
特に後者の unordered_map は、平均計算量がO(1)で高速な検索が可能です。
例えば100万件のデータがあっても、理論上はほぼ一瞬で検索できます。
Mapの基本構造
- キー（検索に使う値）
- 値（実際に取り出したいデータ）
この2つがペアで管理されます。
配列が「番号でアクセスする」のに対して、Mapは「意味でアクセスする」構造です。
配列との違い
配列はインデックスベースの構造、つまり、0番、1番、2番という順番でデータにアクセスします。
一方でMapはキーによってアクセスします。
例えば「7」という値から直接データを取得できます。
計算量の違い
- 配列検索：O(n)
- Map検索：O(1)（平均）
例えば1万件のデータを探す場合、配列では最大1万回の比較が必要です。
一方でMapでは1回で到達できます。
この差が、アルゴリズムの性能を大きく左右します。
GoogleMapで考えるMap
GoogleMapを使うと、住所から場所を一瞬で特定できます。
これはMapの考え方に非常に近いです。
例えば「東京都千代田区」と入力すると、地図上の位置がすぐに表示されます。
ユーザーは裏側の処理を意識しません。
GoogleMapとの対応関係
- 住所 → キー
- 地図上の位置 → 値
この対応がMapの基本構造です。
ただし、C++のMapはもう少し機械的です。
GoogleMapのような空間的なイメージではなく、内部的なルールで配置されます。
ハッシュ値とは何か
unordered_mapではハッシュ値という仕組みが使われます。
ハッシュ値とは、入力された値を数値に変換する関数の結果です。
例えば「7」という値があるとします。
これをハッシュ関数に通すと、ある固定の数値に変換されます。
ハッシュの役割
- 値 → ハッシュ値に変換
- ハッシュ値 → 配置場所を決定
この2段階でデータの位置が決まります。
この仕組みにより、検索時も同じ計算をするだけで場所に到達できます。
値が番地になるという考え方
Mapのイメージとしてよく使われるのが「値が番地になる」という考え方です。
ただし厳密には、値そのものではなくハッシュ値が番地になります。
イメージ整理
- 配列：番地 → 値
- Map：値 → 番地
この逆転が、違和感の原因になります。
実際には「値 → ハッシュ値 → 番地」という流れです。
この変換が内部で自動的に行われています。
出典：CodeBeauty