gperfの概要
完全ハッシュ関数生成器gperfは、入力ファイルから「キーワード」の集合を読み込みます。デフォルトでは標準入力から読み込みます。検索テーブルを高々1回調べることで、静的キーワード集合の要素を認識する完全ハッシュ関数を求めようとします。このような関数を生成できた場合、gperfはハッシュ計算とテーブル検索による認識を行う2つのCソースコードのルーチンを出力します。生成するCコードはすべて標準出力に送られます。以下で説明するコマンドラインオプションを使うと、gperfの入力形式や出力形式を変更できます。
デフォルトでは、gperfは時間効率のよいコードを作ろうとし、空間の利用効率はそれほど重視しません。ただし、実行時間と記憶領域とのトレードオフを調整できるオプションがあります。特に、生成するテーブルのサイズを大きくすると疎な検索構造となり、一般に検索が速くなります。逆に、データの記憶領域を最小限にするCのswitch文方式を使うよう、gperfに指定することもできます。さらに、Cのswitchを使うことで、実際にキーワードの取得時間が多少短くなる場合もあります。当然ながら、実際の結果は使用するCコンパイラによって異なります。
一般に、gperfは、各キーワードに一意の値が与えられる組み合わせが見つかるまで、ハッシュ計算に使うバイトに値を割り当てます。ハッシュ値の範囲が大きいほど、gperfが完全ハッシュ関数を見つけて生成しやすくなる、という経験則が役立ちます。gperfを最大限に活用する鍵は、実際に試してみることです。