1

[1, 1000] と文字列に 3 つの整数を持つ構造があります。

少なくとも 1 つのフィールドが異なる 2 つの構造が異なるコードを生成し、同じ内容を持つ構造が一貫して同じコードを生成するように、32 ビット数で表す必要があります。通常、整数フィールドの 1 つが数単位で増加します。これにより、必然的に異なるコードが生成されるはずです。

最初は、構造体フィールドを定数形式の文字列にフォーマットし、それを String クラスの GetHashCode 関数を使用してハッシュすることを考えました。しかし、同じ入力で繰り返しプロセスを実行しても同じハッシュ出力が生成されるとは限らないといういくつかの議論をここで読みました。まず、これは .NET 4 に当てはまりますか? ハッシュ値は永続化され、プロセスの実行中に一貫性を保つ必要があるため、これは私にとって重要です。また、素数を使用して各構造体フィールドに適用されたプラットフォーム GetHashCode の結果のビット演算を実行するための提案もここで見ました。しかし、ここでも、プロセス実行の一貫した結果を当てにできないようです。

暗号化ハッシュ関数を使用すると、32 ビットを超えます。

文字列フィールドがなければ、数値フィールドから 32 ビット配列としてコードを構成します。そのようなビット配列を文字列フィールド GetHashCode の結果と XOR する価値があるでしょうか? 一部の入力に対して実行を繰り返すと、同じハッシュ出力が生成される可能性が高くなりますか?

あなたは何をすることを提案しますか?

4

3 に答える 3

1

次の場合：

struct 
{
    int A;
    int B;
    int C;
}

A、B、Cが範囲内にあると仮定します[1, 1000]。A、B、Cはそれぞれ1000の異なる可能な値を持つことができるため、「完全なハッシュ」（衝突なし）を作成することが可能です。実際、log2(1000^3) <= 32（1000^3は構造の可能な値の数であり、log2は衝突せずにこれらすべての値を格納するために必要なビット数を取得するために使用され32、整数のビット数です）。

int MyHashCode()
{
    return 1000 * (1000 * (A - 1) + (B - 1)) + (C - 1);  // There is no overflow or collision since A, B, C are in the range [1, 1000]
}

より弱い条件を使用することで、これを単純化できます。A、B、Cは[0、1000]の範囲にあります。

int MyHashCode()
{
    return 1001 * (1001 * A + B) + C;  // There is no overflow or collision since A, B, C are in the range [0, 1000]
}

アップデート

構造内に文字列が含まれているとします。あなたが達成したいことは不可能です。文字列は無限の数の値を表すことができるためです。

それが可能であれば、非常に強力な圧縮アルゴリズムを作成できます。これにより、任意のファイルを...32ビットの数値に格納できます。数学的には、単射関数はより大きな空間にしかマッピングできないという事実から来ています。

于 2013-03-04T22:33:04.493 に答える
1

匿名型には、自動生成された賢明なGetHashCode()実装があります。私はちょうど使用してみます：

struct MyStruct 
{
    int _intField1;
    int _intField2;
    int _intField3;
    string _stringField;

    public long GetHashCode() 
    {
        return new { _intField1, _intField2, _intField3, _stringField }.GetHashCode();
    }
}

intsとsはどちらstringも不変の型であるため、基になる.NET Frameworkのバージョンが同じである限り、アプリケーションの実行間でハッシュコードは同じままである必要があります。（これは「十分に永続的」である場合とそうでない場合があります。）

とはいえ、変更の内部実装があれば変更される可能性がGetHashCode()あります。その場合は、暗号化ハッシュを使用してください。暗号化ハッシュは、入力の小さな変更に対して大きく異なる出力を生成するように設計されているため、32ビットを超えても問題ありません。これは、2つの異なる入力の場合、ハッシュコードの任意の32ビットが等しくなる可能性が非常に低いことを意味します。BitConverter.ToInt32()ハッシュの任意の部分をに変換するために使用するだけですint。

また、明らかに、これにより、2つの異なる構造が異なるハッシュコードを生成する可能性がやや低くなります。（これは、誕生日のパラドックスの近似式を使用して決定できます。ウィキを正しく読んでいる場合、最大140,000〜30,000レコードを保存すると、10％の確率で重複が発生する可能性があります。暗号化ハッシュが理想的であると仮定します。プロパティ。完全なハッシュがなくても、もっとうまくできるかどうかはわかりません。）

于 2013-03-04T22:39:38.517 に答える
0
  1. 型を byte[] にシリアル化します
  2. byte[] に一般的なハッシュ アルゴリズムを適用して、ハッシュ byte[] を取得します。
  3. たとえば、ハッシュ byte[] の最初の 32 ビットを取り出して、それを使用します。
于 2013-03-04T22:48:44.410 に答える