0

私が解決しようとしているもの: Dictionary(string, someObject) のキーとしてguid文字列を使用し、キーの完全なハッシュが必要です...

何か不足しているかどうかわかりません...サイズ割り当てのみを渡す辞書コンストラクターで次のテストを実行すると、実行ごとに+-10の衝突が発生します。文字列に対して gethashcode を呼び出すだけで IEqualityComparer を渡すと、テストに合格しました。場合によっては x = 10 回の反復を使用して複数回実行し、y を最大 100 万回実行します。特に文字列を扱うときに、辞書がハッシュ関数を調整していると思いましたか？私のマシンにはリフレクターがありません:(だから今夜はチェックできません...辞書の初期化を交互にコメントアウトすると、私のi7でテストが比較的速く実行されます.

            [TestMethod]
    public void NearPerfectHashingForGuidStrings()
    {
        int y = 100000;
        int collisions = 0;

        //Dictionary<string, string> list = new Dictionary<string, string>(y, new GuidStringHashing());
        Dictionary<string, string> list = new Dictionary<string, string>(y);
        for (int x = 0; x < 5; x++)
        {

            Enumerable.Range(1, y).ToList().ForEach((h) =>
            {
                list[Guid.NewGuid().ToString()] = h.ToString();
            });

            var hashDuplicates = list.Keys.GroupBy(h => h.GetHashCode())
                .Where(group => group.Count() > 1)
                .Select(group => group.Key).ToList();

            hashDuplicates.ToList().ForEach(v => Debug.WriteLine( x +  "--- " + v));
            collisions += hashDuplicates.Count();
            list.Clear();
        }

        Assert.AreEqual(0, collisions);
    }

        public class GuidStringHashing : IEqualityComparer<string>
{
    public bool Equals(string x, string y)
    {
        return GetHashCode(x) == GetHashCode(y);
    }

    public int GetHashCode(string obj)
    {
        return obj.GetHashCode();
    }
}
4

3 に答える 3

2

あなたのテストは壊れています。

等値比較器は、たまたま同じハッシュを持つ 2 つの異なる GUID が等しいと誤って報告するため、最初から辞書に衝突が保存されることはありません。

鳩の巣の原理により、2 32個を超えるアイテムに対して 32 ビットの完全なハッシュを作成することは基本的に不可能です。

于 2013-02-10T20:05:00.913 に答える
0

それは不可能だ。未知のキーセットに対して完全なハッシュ関数が必要です。特定のキーセットに対して完全なハッシュ関数を作成できます。すべてのキーセットで機能する1つの完全なハッシュ関数を作成することはできません。

その理由は、マーク・ノップラーが非常にうまく述べたように、「2人のイエスの原則」です。「2人の男性は彼らがイエスだと言います。そのうちの1人は間違っているに違いありません。」（これは「鳩の巣原理」としてより広く知られています）

于 2013-02-10T21:06:10.537 に答える
0

完全なハッシュ コードとはどういう意味ですか?

特にGuidStringHashingテストメソッドで使用されていないクラスを投稿しているため、コードはやや混乱しています。

しかし、あなたのコードは、100,000 個の GUID を作成し、それらをすべて文字列に変換してから、文字列のハッシュ コードを取得すると、すべてのハッシュ コードが異なるということが非常に頻繁に発生することを示しています。選択できる整数が 40 億以上あり、100,000 個の文字列しか生成しない場合、これは驚くべきことです。

一般的な文字列にを使用してGetHashCode()いますが、文字列はあまり一般的ではなく、すべて次のようなものです

"2315c2a7-7d29-42b1-9696-fe6a9dd72ffd"

したがって、ハッシュコードが最適ではない可能性があります。のように、文字列を解析hして GUID に戻し、そのハッシュ コードを使用することをお勧めします(new Guid(h)).GetHashCode()。

ただし、これでも 100,000 個の GUID との衝突が発生します。あなたが見ているのは誕生日のパラドックスだと思います。

このより単純なコードを試してください。ここでGetHashCode()は GUID を使用しているため、整数はかなりランダムであると予想されます。

        var set = new HashSet<int>();
        for (int i = 1; true; ++i)
        {
            if (!set.Add(Guid.NewGuid().GetHashCode()))
                Console.WriteLine("Collision, i is: " + i);
        }

(上記のコードを何度も実行することで) 100,000 個のハッシュ コードが計算される前に、ほぼ常に衝突が発生することがわかります。

于 2013-02-10T22:21:21.897 に答える