1

私のアルゴリズムで生成された HashCodes の一意性に関するハッシュ関数のテストを開始しました。そして、同じ hashCode がいつ生成されるかをテストするために、次のテキスト クラスを作成しました。

class Program
{
    static void Main(string[] args)
    {
        var hashes = new List<int>();
        for (int i = 0; i < 100000; i++)
        {
            var vol = new Volume();
            var code = vol.GetHashCode();
            if (!hashes.Contains(code))
            {
                hashes.Add(code);
            }
            else
            {
                Console.WriteLine("Same hash code generated on the {0} retry", hashes.Count());
            }
        }
    }
}

public class Volume
{
    public Guid DriverId = Guid.NewGuid();
    public Guid ComputerId = Guid.NewGuid();
    public int Size;
    public ulong VersionNumber;
    public int HashCode;
    public static ulong CurDriverEpochNumber;
    public static Random RandomF = new Random();

    public Volume()
    {
        Size = RandomF.Next(1000000, 1200000);
        CurDriverEpochNumber ++;
        VersionNumber = CurDriverEpochNumber;
        HashCode = GetHashCodeInternal();
    }

    public int GetHashCodeInternal()
    {
        unchecked
        {
            var one = DriverId.GetHashCode() + ComputerId.GetHashCode() * 22;
            var two = (ulong)Size + VersionNumber;
            var result = one ^ (int)two;
            return result;
        }
    } 

}

GUID フィールド DriverId、ComputerId、および int Size はランダムです。いつか同じハッシュコードを生成するだろうと思いました。大規模なコレクションで作業が中断されることはわかっています。魔法は、重複したハッシュコードが生成されたときのリトライ回数が同じであることでした。サンプル コードを数回実行しましたが、ほとんど同じ結果が得られました。最初は 10170 回の再試行で、2 回目は 7628 回、3 回目は 7628 回、そして 7628 回で何度も何度も実行されました。ほとんどの場合、7628 でした。

私には何の説明もありません。エラーですか。NET乱数発生器または何？

皆さんありがとう。これで、私のコード (Matthew Watson) のバグが明らかになりました。GetHashCode() ではなく、GetHashCodeIntelrnal() を呼び出す必要がありました。最高の GetHashCode のユニークな結果は次のとおりです。

    public int GetHashCodeInternal()
    {
        unchecked
        {
            var one = DriverId.GetHashCode() + ComputerId.GetHashCode();
            var two = ((ulong)Size) + VersionNumber;
            var result = one ^ (int)two << 32;
            return result;
        }
    }

Bu まだ 140 000 近くで同じコードが得られます... 10 000 近くのコレクションがあるため、良くないと思います...

4

2 に答える 2

2

Console.WriteLine() を変更して Volume.Size も次のように出力する場合:

Console.WriteLine("Same hash code generated on the {0} retry ({1})", hashes.Count, vol.Size);

hashes.Countは最初の衝突では常に同じですが、vol.Size通常は異なることがわかります。

これは、この問題の原因となっている乱数ジェネレーターを除外しているようです - の奇妙なプロパティのように見えますGetHashCodeInternal()。

詳しく調べると、間違ったハッシュ コード関数を呼び出していることがわかります。

この行：var code = vol.GetHashCode();

次のようにする必要があります。var code = vol.HashCode;

代わりにそれを試してください！現時点では、デフォルトの.NetGetHashCode()を呼び出しているため、必要なことをまったく行っていません。

于 2013-04-05T10:54:46.477 に答える
1

再利用する単一の乱数ジェネレーターを作成して、乱数ジェネレーターを渡す必要があります。現在、それらの新しいインスタンスを作成しすぎて、同じシードが使用されているため、同じシードが使用されているためです。アウト。

結果は 、シード日付の次のティック/秒からシードが生成された時点でランダムに見えます。だから、本当に偶然です。

于 2013-04-05T10:36:14.390 に答える