ルックアップテーブル（コンピューティング）

構造と実装

代表的な実装には、連続した配列、ハッシュマップ、直接マップ方式のテーブルがある。テーブルのキーには整数のインデックス、文字列、あるいは別の複合キーを使用でき、揮発性メモリまたは読み取り専用の領域に格納される。プログラマは、制御フローの分岐先を選択するジャンプテーブルや、暗号で用いられる置換ボックス（Sボックス）といった特殊な形式も利用する。連続的な定義域における関数をテーブルで表す必要がある場合は、離散的な標本値を格納し、検索時に補間を適用することが一般的である。

一般的な用途と例

• 繰り返し行う算術計算の置換。例として、組込みシステム用の三角関数表や対数表がある。
• 復号と対応付け。文字エンコーディング、カラーパレット、オペコードのディスパッチなどに用いられる。
• 既知の値と入力を照合することによる検証や所属判定。たとえば、有効なトークンの配列が該当する。
• Sボックスなどの暗号コンポーネント、およびハッシュやCRCの計算用に事前計算されたテーブル。

性能上のトレードオフと考慮事項

ルックアップテーブルの使用は、速度を向上させる代わりにメモリを消費する、典型的な空間・時間トレードオフである。設計者は、キャッシュの挙動、初期化コスト、値が実行時に変化するかどうかを考慮しなければならない。定義域が非常に大きい場合、テーブルは実用的でないことがある。その代替として、メモ化、アルゴリズムの最適化、階層的なテーブルが挙げられる。ルックアップテーブルは意図的に事前計算され、多くの場合は不変であるのに対し、キャッシュは過去の計算結果を機会的に格納する点で異なる。

歴史と注目すべき事項

この考え方はデジタルコンピュータよりも古く、対数表や正弦表などの数学表は手計算のために作成されていた。現代のコンピューティングにおいて、この用語は単純な静的配列から、より複雑なインデックス付き構造までを含む。実装は低水準のファームウェアから高性能ライブラリまで、さまざまなシステムで見られる。表形式の情報という一般的な概念については、表（情報）を参照。

関連概念と資料

ルックアップテーブルは、プログラムを高速化するために使用されるデータ構造の一例である。照合アルゴリズム、ハッシュ化、コンパイラ最適化など、多くのプログラミング技法と関わる。実用的な用途に関する技術的な入門は、標準的な教育サイトで利用できるアルゴリズムの参考資料やシステムマニュアル（計算に関する資料）、および業界の文書（取得と実装に関する注記）を参照するとよい。一般的なアルゴリズム上のトレードオフについては、大学の資料からリンクされるチュートリアル教材（コンピュータ科学）や応用ガイド（実行時の性能）を参照できる。メモ化およびキャッシュとの詳しい比較については、アルゴリズムの教科書や実践的なプログラミングガイド（検証、空間・時間トレードオフ）を参照。