53

バイト配列を格納するオブジェクトがあり、そのハッシュコードを効率的に生成できるようにしたいとします。実装が簡単なので、過去にこれに暗号ハッシュ関数を使用しましたが、暗号学的に一方向にする必要があるよりもはるかに多くの作業を行っており、それについては気にしません (私は単にハッシュテーブルへのキーとしてのハッシュコード)。

ここに私が今日持っているものがあります：

struct SomeData : IEquatable<SomeData>
{
    private readonly byte[] data;
    public SomeData(byte[] data)
    {
        if (null == data || data.Length <= 0)
        {
            throw new ArgumentException("data");
        }
        this.data = new byte[data.Length];
        Array.Copy(data, this.data, data.Length);
    }

    public override bool Equals(object obj)
    {
        return obj is SomeData && Equals((SomeData)obj);
    }

    public bool Equals(SomeData other)
    {
        if (other.data.Length != data.Length)
        {
            return false;
        }
        for (int i = 0; i < data.Length; ++i)
        {
            if (data[i] != other.data[i])
            {
                return false;
            }
        }
        return true;
    }
    public override int GetHashCode()
    {
        return BitConverter.ToInt32(new MD5CryptoServiceProvider().ComputeHash(data), 0);
    }
}

何かご意見は？

dp: Equals のチェックを忘れていたのは正しいです。更新しました。バイト配列から既存のハッシュコードを使用すると、参照が等しくなります (または、少なくとも同じ概念がハッシュコードに変換されます)。例えば：

byte[] b1 = new byte[] { 1 };
byte[] b2 = new byte[] { 1 };
int h1 = b1.GetHashCode();
int h2 = b2.GetHashCode();

そのコードでは、2 つのバイト配列が同じ値を持っているにもかかわらず、メモリの異なる部分を参照しているため、(おそらく) 異なるハッシュ コードが生成されます。同じ内容の 2 つのバイト配列のハッシュ コードを等しくする必要があります。

4

11 に答える 11

67

オブジェクトのハッシュ コードは一意である必要はありません。

チェック規則は次のとおりです。

  • ハッシュコードは等しいですか？次に、完全な (遅い)Equalsメソッドを呼び出します。
  • ハッシュコードは等しくありませんか? その場合、2 つの項目は間違いなく等しくありません。

必要なのは、GetHashCodeコレクションをほぼ均等なグループに分割するアルゴリズムだけです。キーを形成しないHashTableかDictionary<>、検索を最適化するためにハッシュを使用する必要があります。

データはどのくらいの期間になると予想されますか? どのようにランダムですか？長さが大幅に異なる場合 (ファイルなど)、長さだけを返します。長さが似ている可能性が高い場合は、変化するバイトのサブセットを調べます。

GetHashCodeよりもはるかEqualsに高速である必要がありますが、一意である必要はありません。

2 つの同一のものが異なるハッシュ コードであってはなりません。2 つの異なるオブジェクトが同じハッシュ コードを持つべきではありませんが、いくつかの衝突が予想されます (結局のところ、考えられる 32 ビット整数よりも多くの順列があります)。

于 2008-08-19T15:17:05.937 に答える
51

ハッシュテーブルに暗号化ハッシュを使用しないでください。これはばかげている/やり過ぎです。

どうぞ... C# で変更された FNV ハッシュ

http://bretm.home.comcast.net/hash/6.html

    public static int ComputeHash(params byte[] data)
    {
        unchecked
        {
            const int p = 16777619;
            int hash = (int)2166136261;

            for (int i = 0; i < data.Length; i++)
                hash = (hash ^ data[i]) * p;

            hash += hash << 13;
            hash ^= hash >> 7;
            hash += hash << 3;
            hash ^= hash >> 17;
            hash += hash << 5;
            return hash;
        }
    }
于 2009-01-22T04:55:49.990 に答える
13

JetBrains ソフ​​トウェアによって生成されたコードを借りて、次の関数に落ち着きました。

    public override int GetHashCode()
    {
        unchecked
        {
            var result = 0;
            foreach (byte b in _key)
                result = (result*31) ^ b;
            return result;
        }
    }

バイトを XOR するだけの問題は、返される値の 3/4 (3 バイト) が 2 つの可能な値 (すべてオンまたはすべてオフ) しかないことです。これにより、ビットがもう少し広がります。

Equals にブレークポイントを設定することは良い提案でした。私のデータの約 200,000 エントリをディクショナリに追加すると、約 10 回の Equals 呼び出し (または 1/20,000) が表示されます。

于 2009-01-08T17:37:53.877 に答える
4

SHA1CryptoServiceProvider.ComputeHashメソッドと比較しましたか? バイト配列を取り、SHA1 ハッシュを返します。かなり最適化されていると思います。負荷がかかった状態でかなりうまく機能するIdenticon Handlerで使用しました。

于 2008-08-19T15:53:28.983 に答える
4

興味深い結果が見つかりました:

私はクラスを持っています：

public class MyHash : IEquatable<MyHash>
{        
    public byte[] Val { get; private set; }

    public MyHash(byte[] val)
    {
        Val = val;
    }

    /// <summary>
    /// Test if this Class is equal to another class
    /// </summary>
    /// <param name="other"></param>
    /// <returns></returns>
    public bool Equals(MyHash other)
    {
        if (other.Val.Length == this.Val.Length)
        {
            for (var i = 0; i < this.Val.Length; i++)
            {
                if (other.Val[i] != this.Val[i])
                {
                    return false;
                }
            }

            return true;
        }
        else
        {
            return false;
        }            
    }

    public override int GetHashCode()
    {            
        var str = Convert.ToBase64String(Val);
        return str.GetHashCode();          
    }
}

次に、MyHash 型のキーを使用して辞書を作成し、挿入速度をテストし、衝突の数も確認しました。私は次のことをしました

        // dictionary we use to check for collisions
        Dictionary<MyHash, bool> checkForDuplicatesDic = new Dictionary<MyHash, bool>();

        // used to generate random arrays
        Random rand = new Random();



        var now = DateTime.Now;

        for (var j = 0; j < 100; j++)
        {
            for (var i = 0; i < 5000; i++)
            {
                // create new array and populate it with random bytes
                byte[] randBytes = new byte[byte.MaxValue];
                rand.NextBytes(randBytes);

                MyHash h = new MyHash(randBytes);

                if (checkForDuplicatesDic.ContainsKey(h))
                {
                    Console.WriteLine("Duplicate");
                }
                else
                {
                    checkForDuplicatesDic[h] = true;
                }
            }
            Console.WriteLine(j);
            checkForDuplicatesDic.Clear(); // clear dictionary every 5000 iterations
        }

        var elapsed = DateTime.Now - now;

        Console.Read();

辞書に新しい項目を挿入するたびに、辞書はそのオブジェクトのハッシュを計算します。したがって、ここにあるいくつかの回答をメソッドに配置することで、どのメソッドが最も効率的かがわかりpublic override int GetHashCode()ます

    public override int GetHashCode()
    {            
        var str = Convert.ToBase64String(Val);
        return str.GetHashCode();          
    }

実行に2秒かかりました。方法

    public override int GetHashCode()
    {
        // 7.1 seconds
        unchecked
        {
            const int p = 16777619;
            int hash = (int)2166136261;

            for (int i = 0; i < Val.Length; i++)
                hash = (hash ^ Val[i]) * p;

            hash += hash << 13;
            hash ^= hash >> 7;
            hash += hash << 3;
            hash ^= hash >> 17;
            hash += hash << 5;
            return hash;
        }
    }

衝突もありませんでしたが、実行に 7 秒かかりました!

于 2014-03-12T20:40:25.987 に答える
2

パフォーマンスを求める場合は、いくつかのハッシュ キーをテストしましたが、Bob Jenkin のハッシュ関数をお勧めします。計算が非常に高速であり、これまでに使用した暗号化ハッシュと同じくらい衝突が少なくなります。

私は C# をまったく知りませんし、C とリンクできるかどうかもわかりませんが、C での実装は次のとおりです。

于 2008-08-19T15:16:24.720 に答える
1

完全なハッシュ関数（等しいと評価されるオブジェクトごとに異なる値）が必要な場合でも、非常に優れたハッシュ関数が必要な場合でも、通常はパフォーマンスのトレードオフになります。通常、優れたハッシュ関数の計算には時間がかかります。データセットが小さい場合は、次のようになります。高速関数。（2番目の投稿で指摘されているように）最も重要なのは正確さであり、それを実現するために必要なのは、配列の長さを返すことだけです。データセットによっては、問題ない場合もあります。そうでない場合（たとえば、すべての配列が同じ長さである場合）、最初と最後の値を調べてそれらの値をXORし、データに適していると思われる複雑さを追加するなど、安価な方法を使用できます。

ハッシュ関数がデータに対してどのように実行されるかを確認する簡単な方法は、すべてのデータをハッシュテーブルに追加し、Equals関数が呼び出される回数を数えることです。これは、関数に対して行う作業が多すぎる場合に使用します。これを行う場合は、開始時にハッシュテーブルのサイズをデータセットよりも大きく設定する必要があることに注意してください。そうしないと、データを再ハッシュして、再挿入とより多くのEquals評価をトリガーします（おそらくより現実的ですか？）

一部のオブジェクト（これではない）では、ToString（）。GetHashCode（）によってクイックHashCodeを生成できますが、これは確かに最適ではありませんが、ToString（）からオブジェクトのIDに近いものを返す傾向があるため、これは正確に役立ちます。 GetHashcodeが探しているもの

雑学：私が今まで見た中で最悪のパフォーマンスは、誰かが誤ってGetHashCodeから定数を返したときでしたが、特にハッシュテーブルで多くのルックアップを行う場合は、デバッガーで簡単に見つけることができます。

于 2008-09-09T22:35:54.877 に答える
1

バイト配列フ​​ィールドから既存のハッシュコードを使用するのは十分ではありませんか? また、Equals メソッドでは、比較を行う前に配列が同じサイズであることを確認する必要があることに注意してください。

于 2008-08-19T15:19:32.203 に答える
1

適切なハッシュを生成することは、言うは易く行うは難しです。基本的に、n バイトのデータを m ビットの情報で表していることを思い出してください。データセットが大きく、m が小さいほど、衝突が発生する可能性が高くなります... 2 つのデータが同じハッシュに解決されます。

私がこれまでに学んだ最も単純なハッシュは、単純にすべてのバイトを XOR することでした。これは簡単で、ほとんどの複雑なハッシュ アルゴリズムよりも高速であり、小規模なデータ セット向けの中途半端な汎用ハッシュ アルゴリズムです。それは実際には、ハッシュ アルゴリズムのバブル ソートです。単純な実装では 8 ビットしか残らないため、ハッシュは 256 個しかありません ... それほどホットではありません。個々のバイトの代わりにチャンクを XOR することもできますが、アルゴリズムははるかに複雑になります。

確かに、暗号化アルゴリズムは必要のないことを行っている可能性があります...しかし、それらは汎用ハッシュの品質においても大きな進歩です。使用している MD5 ハッシュには 128 ビットがあり、何十億もの可能なハッシュがあります。より良いものを得る唯一の方法は、アプリケーションを通過すると予想されるデータの代表的なサンプルをいくつか取得し、それに対してさまざまなアルゴリズムを試して、衝突がいくつ発生するかを確認することです。

したがって、既定のハッシュ アルゴリズムを使用しない理由 (おそらくパフォーマンス?) がわかるまでは、既存のものを使い続けることをお勧めします。

于 2008-08-19T15:31:02.757 に答える
0

RuntimeHelpers.GetHashCodeが役立つ場合があります。

MSDN より:

ハッシュ アルゴリズムやハッシュ テーブルなどのデータ構造での使用に適した、特定の型のハッシュ関数として機能します。

于 2008-08-20T02:32:20.193 に答える