コンピュータサイエンスにおけるインデックスマッピング（またはダイレクトアドレッシング、あるいは自明なハッシュ関数）とは、配列を用いて各位置が可能な値の集合内のキーに対応することを指します。[1] この手法は、キーの集合が適度に小さく、あらゆるキーに対して1つの位置を持つ配列を割り当てることが負担にならない場合に最も効果的です。その有効性は、配列内の任意の位置を定数時間で調べることができるという事実に由来します。
適用可能な配列
有効な値が狭い範囲に制限されているデータの実例は数多くあります。そのようなデータを参照キーとして利用する必要がある場合、単純なハッシュ関数が適しています。例としては、以下のようなものがあります。
- 年の月（1～12）
- 月内の日（1～31）
- 曜日（1～7）
- 人間の年齢（0～130） – 例：生命保険の保険数理表、固定期間住宅ローン
- ASCII文字（0～127）には、一般的な数学演算子記号、数字、句読点、英語のアルファベットが含まれます。
例
非反復テーブル検索で単純なハッシュ関数を使用すると、条件付きテストと分岐を完全に排除でき、コンピュータ プログラムの 命令パスの長さを短縮できます。
分岐を避ける
ロジャー・セイルは、スイッチ文によって発生する多分岐を排除する例[2]を挙げている。
inline bool HasOnly30Days ( int m ) { switch ( m ) { case 4 : // 4月case 6 : // 6月case 9 : // 9月case 11 : // 11月return true ; default : return false ; } }
これはテーブル検索に置き換えることができます:
インラインbool HasOnly30Days ( int m ) { static const bool T [] = { 0 , 0 , 0 , 1 , 0 , 1 , 0 , 0 , 1 , 0 , 1 , 0 }; return T [ m -1 ]; }
参考文献
- ^ コーメン、トーマス・H. (2009). アルゴリズム入門（第3版）. マサチューセッツ州ケンブリッジ: MIT出版. pp. 253– 255. ISBN 9780262033848. 2015年11月26日閲覧。
- ^ Sayle, Roger Anthony ( 2008年6月17日). 「スーパーオプティマイザーによる多分岐コード生成の分析」(PDF) . GCC開発者サミット議事録: 103–116 . 2015年11月26日閲覧。
