3

私はプログラミング言語を開発しています。私のプログラミング言語では、オブジェクトをハッシュ テーブルとして保存しています。私が使用しているハッシュ関数は、256 ビットのルックアップ テーブルに依存するPearson Hashingです。関数は次のとおりです。

char* pearson(char* name, char* lookup)
{
    char index = '\0';
    while(*name)
    {
        index = lookup[index ^ *name];
        name++;
    }
    return index;
}

私の質問は、256 未満のメンバー名の固定グループが与えられたlookup場合pearson()、'\0'. つまり、完全なハッシュのルックアップ テーブルを作成するアルゴリズムが必要です。これにより、メンバーの数よりも多くのスペースを占有しないオブジェクトを持つことができます。これはコンパイル時に行われるため、速度は大きな問題ではありませんが、高速であればあるほどよいでしょう。これをブルート フォースするのは簡単ですが、もっと良い方法があると思います (願っています)。

例を次に示します。クラスにメンバー変数 'foo'、'bar'、および 'baz' がある場合、次のlookupように決定したいと考えています。

pearson('foo',lookup) == (char) 0
pearson('bar',lookup) == (char) 1
pearson('baz',lookup) == (char) 2

順序は問題ではないことに注意してください。したがって、次の結果も許容されます。

pearson('foo',lookup) == (char) 2
pearson('bar',lookup) == (char) 0
pearson('baz',lookup) == (char) 1

理想的な世界では、テーブルにないすべての名前は 2 より大きい値を返します。これにより、チェックを回避でき、メンバー名の保存を回避できる可能性もありますが、これが可能だとは思わないので、テーブルにあるかどうかを確認するために、追加のチェックを追加する必要があります。これを考えると、使用されていないルックアップ テーブルの値を初期化しない方がおそらく時間を節約できます (衝突は問題ではありません。衝突してチェックに失敗した場合、それはオブジェクトにまったく含まれていないため、衝突は解決する必要はなく、エラーのみを処理する必要があります)。

4

2 に答える 2

1

メンバー名の数が多すぎると、力ずくで解決策を見つけることができるとは思えません。誕生日のパラドックスのおかげで、衝突が存在しない (つまり、2 つのハッシュが同じである) 確率は、64 の場合は約 1:5000、96 のメンバー名の場合は 1:850,000,000 です。あなたのハッシュ関数の構造から（物事をうまく「混ぜる」ように設計された暗号構造から派生したものです）、あなたの問題を解決するアルゴリズムが存在するとは思いません（しかし、私は間違いなくそのような獣に興味があります）。

あなたの理想の世界は (ご想像のとおり) 錯覚です: 'foo' に追加できる文字は 256 文字あり、そのうちの 2 つが同じハッシュを持つ新しい単語を与えることはありません。ハッシュ値には 256 の可能性しかないため、文字を 'foo' に追加して、そのハッシュが 'foo'、'bar'、または 'baz' のハッシュのいずれかと同じになるようにすることができます。

CMPHのような既存のライブラリを使用しないのはなぜですか?

于 2009-09-09T09:51:28.110 に答える
0

私があなたを正しく理解している場合、必要なのは、バイナリ検索を実行できる、並べ替えられた重複要素のない配列です。キーが配列にある場合、インデックスは「ハッシュ」です。それ以外の場合は、配列のサイズを取得します。ルックアップ テーブル O(1) と比較すると O(nlogn) ですが、少数の要素 (この場合は 256) には十分です。

于 2009-09-09T09:26:56.747 に答える