4

4000 個の文字列があり、これらの文字列を使用して完全なハッシュ テーブルを作成したいと考えています。文字列は事前にわかっているので、最初のアイデアは一連のifステートメントを使用することでした。

 if (name=="aaa")
      return 1;
 else if (name=="bbb")
      return 2;
        .
        .
        .
 // 4000th `if' statement

ただし、これは非常に非効率的です。より良い方法はありますか？

4

4 に答える 4

10

gperfまさにそれを行うツールです：

GNUgperfは完璧なハッシュ関数ジェネレーターです。指定された文字列のリストに対して、入力文字列に応じて値を検索するために、ハッシュ関数とハッシュ テーブルを C または C++ コードの形式で生成します。ハッシュ関数は完全です。つまり、ハッシュ テーブルには衝突がなく、ハッシュ テーブルのルックアップには単一の文字列比較のみが必要です。

ドキュメントによると、gperfGNU C、GNU C++、GNU Java、GNU Pascal、GNU Modula 3、および GNU indent の字句解析器の予約済みキーワード認識エンジンを生成するために使用されます。

その仕組みについては、Douglas C. Schmidtによる GPERF: A Perfect Hash Function Generatorで説明されています。

于 2014-12-29T18:39:27.167 に答える