既知のキーのセットが与えられたら、それらのための最適なハッシュ関数を決定できますか？

Question

gperfは（CまたはC++を使用している場合）1つのオプションと思われますが、少なくともいくつかの状況ではより良いものがありますか？アプリケーションの例は、コードと例外をリンクすることです。例外処理の一般的な実装では、リンカは、スタックのunwindのために関数のコードを破棄/終了するアドレスに、リターンアドレス（例外を生成する関数への呼び出し用）から最適な連想検索を構築する必要があります。

Answer 1

既知のすべてのキーがあらかじめわかっている場合は、trie/keyword treeのキーを作成してください。各単語の終わりにユニークなインデックスを置く。

この方法では、ハッシュ関数はO(length_of_the_largest_string)時間を超えることはありません。必要なメモリがO(total_character_in_all_the_strings)

の場合は、一意のプレフィックスだけを使用すると、時間とメモリを減らすことができます。