ルックアップテーブル
例えば、(二進数の)数字の中で「1」である桁数(ハミング重み)を求める処理を考える。例えば、十進数の「37」は二進数では「100101」であり、「1」である桁は3つある。
この処理をC言語で記述した簡単な例を以下に示す。この例では、int型の引数を対象に「1」である桁を数えている。
この一見シンプルなアルゴリズムは、実際に実行すると、近代的なアーキテクチャのプロセッサでも数百サイクルを要する場合がある。これは、ループ中で繰り返し分岐処理が実行されるためである(分岐処理は遅いことが多い)。コンパイラによっては、最適化の際にこの処理をループ展開することで性能がいくらか改善される場合もある。しかし、自明なハッシュ関数を利用したアルゴリズムであればよりシンプルかつ高速に処理が行える。
256個の要素を持つ静的なテーブル(名前はbit_setとする)を用意し、各要素には0から255までの数の「1」の桁数を格納する。