Hash Table（ハッシュテーブル）

キーから必要な値を探す

Hash Tableは、キーと値を組にして保存し、キーから対応する値を探すデータ構造です。辞書で言葉から意味を探すように、「何を手がかりに、何を取り出すか」を決めて使います。

キー

攻撃対象のID

String

値

受けるダメージの合計

Int

VEINで解決したいこと

VEINの戦闘では、同じtick内に複数の攻撃者が同じ相手を狙うことがあります。攻撃のたびに対象を探して体力を更新するのではなく、まず対象IDごとのダメージをMapへ集計し、その後にまとめて反映します。

攻撃A → 対象X：12

攻撃B → 対象X：8

攻撃C → 対象Y：10

IDごとに集計したMap

対象X → 20

対象Y → 10

同じIDの値へダメージを加算する

攻撃順に依存して途中の状態を何度も変更せず、対象ごとの合計を明示してから戦闘結果へ反映できます。

VEINのコードで見る

damageToCreaturesは、クリーチャーIDをキー、受けるダメージの合計を値として持つMapです。対象が初めて攻撃された場合は0から始め、すでに値があれば現在値へ新しいダメージを加えます。

Kotlin — AssaultBattle.ktから抜粋

// 同じtickで各クリーチャーが受けるダメージをID別に集計する
val damageToCreatures = mutableMapOf<String, Int>()

// すでに集計した値があれば加算し、初回なら0から始める
damageToCreatures[target.id] =
    damageToCreatures.getOrDefault(target.id, 0) + damage

この変数の型はMutableMap<String, Int>です。Mapを使うことで、攻撃対象の人数や攻撃回数が増えても、IDに対応する集計値を毎回一覧の先頭から探す必要がありません。

なぜハッシュ値を使うのか

Mapは対象のString型IDからハッシュ値を計算し、対応するダメージ合計が置かれた場所の候補を絞ります。その後、IDが本当に同じかを確認して値を返します。

1. 攻撃対象のIDをキーとして受け取る
2. hashCode()で保存場所の候補を絞る
3. equals()で同じIDか確認する
4. 対応するダメージ合計を返す

キーには、処理中に意味が変わらず、同じ対象なら同じ値として比較できるものを選びます。この例では戦闘参加者を識別するIDを使うため、座標が変わっても同じ対象の集計を続けられます。

Mapは経路探索専用ではない

VEINでは、同じMapでも場面によってキーと値の意味が変わります。データ構造名から用途を決めず、「何を手がかりに、何を取得または更新したいか」から設計します。

ID → 戦闘参加者

演出を作るとき、更新前の参加者をIDから取得する。

画像ID → Texture

読み込んだ画像を描画時に再利用する。

Species → Level

クリーチャーの種類ごとに成長状態を管理する。

速くなる代わりに、メモリを使う

ハッシュを使ったMapでは、キーによる検索と更新を平均O(1)で行えます。ただし、キーと値を保持する追加メモリが必要です。また、ハッシュ値が同じになる衝突もあるため、O(1)は常に保証される時間ではありません。