指定された文字列キーの整数を返す必要がある、次のシグネチャを持つ検索関数を考えてみましょう。
int GetValue(string key) { ... }
さらに、キーと値のマッピング (番号 N) は、関数のソース コードが記述されているときに事前にわかっていることを考慮してください。たとえば、次のようになります。
// N=3
{ "foo", 1 },
{ "bar", 42 },
{ "bazz", 314159 }
したがって、上記の入力に対する関数の有効な (ただし完全ではない!) 実装は次のようになります。
int GetValue(string key)
{
switch (key)
{
case "foo": return 1;
case "bar": return 42;
case "bazz": return 314159;
}
// Doesn't matter what we do here, control will never come to this point
throw new Exception();
}
また、特定のキーごとに関数が実行時に呼び出される正確な回数 (C>=1) も事前にわかっています。例えば：
C["foo"] = 1;
C["bar"] = 1;
C["bazz"] = 2;
ただし、そのような呼び出しの順序は不明です。たとえば、上記は実行時に次の一連の呼び出しを記述することができます。
GetValue("foo");
GetValue("bazz");
GetValue("bar");
GetValue("bazz");
呼び出し回数が一致する場合、またはその他のシーケンス。
制限 M もあり、最も便利な単位で指定され、 で使用できるルックアップ テーブルやその他のヘルパー構造体のメモリ上限を定義しますGetValue(構造体は事前に初期化されます。その初期化は複雑さに対してカウントされません)。関数の）。たとえば、M=100 文字、または M=256 sizeof(オブジェクト参照) です。
GetValue問題は、可能な限り高速になるように の本体を記述する方法です。つまり、すべてのGetValue呼び出しの合計時間 (上記のすべての合計数を知っていることに注意してください) は、与えられた N、C に対して最小です。そしてM？
アルゴリズムは、M の妥当な最小値を必要とする場合があります (例: M >= ) char.MaxValue。また、M を何らかの合理的な境界に揃えることも必要になる場合があります。たとえば、2 のべき乗のみである場合などです。また、M が特定の種類の N の関数でなければならないことも必要になる場合があります (たとえば、有効な M=N、または M=2N、...; または有効な M=N、または M=N^2、 ...;など)。
アルゴリズムは、適切な言語またはその他の形式で表現できます。生成されたコードのランタイム パフォーマンスの制約については、生成されたコードGetValueが C#、VB、または Java であると仮定します (実際には、文字列が文字の不変配列として扱われる限り、つまり O(1) の長さと O (1) 索引付け、事前に計算されたその他のデータなし)。また、これを少し単純化するために、すべてのキーに対して C=1 であると仮定する回答は有効と見なされますが、より一般的なケースをカバーする回答が優先されます。
可能なアプローチについてのいくつかの熟考
上記に対する明白な最初の答えは、完全なハッシュを使用することですが、完全なハッシュを見つけるための一般的なアプローチは不完全なようです。たとえば、上記のサンプル データに対して Pearson ハッシュを使用して最小限の完全ハッシュのテーブルを簡単に生成できますが、その場合、 を呼び出すたびに入力キーをGetValueハッシュする必要があり、Pearson ハッシュは必然的に入力文字列全体をスキャンします。しかし、すべてのサンプル キーは実際には 3 番目の文字が異なるため、文字列全体ではなく、3 番目の文字のみをハッシュの入力として使用できます。さらに、M が少なくともchar.MaxValueである必要がある場合、3 番目の文字自体が完全なハッシュになります。
別のキーのセットでは、これはもはや当てはまらないかもしれませんが、正確な答えを得る前に考慮される文字の量を減らすことはまだ可能かもしれません. さらに、最小限の完全なハッシュが文字列全体を検査する必要がある場合は、ハッシュを非最小限にすることで、ルックアップをサブセットに減らすか、そうでなければ高速化することができます (たとえば、より複雑でないハッシュ関数?)。 (つまり、M > N) - 速度のためにスペースを効果的に犠牲にします。
また、従来のハッシュは最初からあまり良い考えではない可能性もありますGetValue。一連の条件として本体を構造化する方が簡単であり、最初に「最も可変性のある」文字 (全体的に変化する文字) をチェックするように配置されます。ほとんどのキー)、正しい答えを決定するために、必要に応じてさらにネストされたチェックを行います。ここでの「分散」は、各キーが検索される回数の影響を受ける可能性があることに注意してください (C)。さらに、ブランチの最良の構造がどのようなものであるべきかは、常に容易に明らかであるとは限りません。たとえば、「最も変化しやすい」文字では、100 個のキーのうち 10 個のキーしか区別できず、残りの 90 個のキーについては 1 回の追加チェックが必要になる場合があります。それらを区別する必要はありません。「最も変化しやすい」キャラクターから始めないでください。目標は、チェックの完全な順序を決定することです。