概要

  • std::unordered_mapは連想配列の一種
    • 連想配列はARR["Key"]のような形で任意の文字列や識別子を使えるデータ構造のこと
    • 具体的な実装方法としては ハッシュテーブル が用いられている
  • std::mapも連想配列の一種
    • こちらは 平衡二分探索木 が内部実装
    • 使い分けは簡単にまとめておく

キーに自作の型を使うとき

キーに自作の型を使うときには

  • キーの型にoperator==をオーバーロード
  • キーの型を入力としたハッシュ関数実装
    が必要となる。

operator==のオーバーロードについて

キーのoperator==をオーバーロードする必要があるが、このときに

operator==でtrueとみなされたオブジェクトインスタンスA, Bをハッシュ関数の引数にしたとき、A, Bともにハッシュ関数の戻り値は常に同じである必要がある。

キーの型を入力としたハッシュ関数について

キーの構成に合わせて「なるべく結果が被らない」ように設計する必要がある。
例えば2Dグリッドを考えたときに

struct S_2D_GRID
{
    int nX;
    int nY
}

struct S_2D_GRID_HASH
{
    std::size_t operator(const S_2D_GRID& rGrid) const
    {
        return nX * 10 + nY * 10;
    }
}

としてしまうと(10, 20)と(20, 10)のハッシュが同じ値になってハッシュ衝突してしまう。（これはマジで単純すぎる例だけど…）

なので、

  • 中央積算法
  • 折り畳み法
    など工夫を行う必要がある。

衝突後の解決方法によらず、衝突すればするほど探索が遅くなるのでなるべくハッシュ値を被らないようにするのが大事。
グリッド1のように複数の値からハッシュを計算するときはboost::hash_combine()みたいな工夫が大事2

Footnotes

  1. ゲームにおいてモデルとかの配置物とかで大まかな位置を把握するときとかには結構使うので覚えておかないとなぁ ↩

  2. boost::hash_combine()のマジックナンバー ↩