93

2 つのオブジェクトのハッシュ コードを結合するための迅速かつ簡単な方法を推奨できますか? 私はそれを効率的に処理するハッシュテーブルを持っているので、衝突についてあまり心配していません。できるだけ早くコードを生成するものが欲しいだけです。

SO と Web を読むと、主な候補がいくつかあるようです。

  1. 排他的論理和
  2. 素数乗算による XOR 演算
  3. 乗算/除算などの単純な数値演算 (オーバーフロー チェックまたはラップ アラウンドを使用)
  4. String を作成してから String クラスの Hash Code メソッドを使用する

人々は何を推奨し、その理由は何ですか?

4

10 に答える 10

142

私は個人的にXORを避けます-それは任意の2つの等しい値が0になることを意味します-したがってhash（1、1）== hash（2、2）== hash（3、3）など。またhash（5、0） ==ハッシュ（0、5）など。たまに発生する可能性があります。私は意図的にこれをセットハッシュに使用しました-一連のアイテムをハッシュしたいが、順序を気にしないのであれば、それは素晴らしいことです。

私は通常使用します：

unchecked
{
    int hash = 17;
    hash = hash * 31 + firstField.GetHashCode();
    hash = hash * 31 + secondField.GetHashCode();
    return hash;
}

これは、JoshBlochがEffectiveJavaで提案している形式です。前回同様の質問に答えたとき、これが詳細に説明されている記事を見つけることができました-IIRC、なぜそれがうまく機能するのか誰も本当に知りませんが、それは機能します。また、覚えやすく、実装しやすく、任意の数のフィールドに簡単に拡張できます。

于 2009-10-29T22:11:04.610 に答える
22

タプルで組み合わせロジックを使用します。この例では、c#7 タプルを使用しています。

(field1, field2).GetHashCode();
于 2017-11-24T22:38:09.043 に答える
20

.NET Framework チームはSystem.String.GetHashCode()実装のテストで適切な仕事をしたと思うので、それを使用します。

// System.String.GetHashCode(): http://referencesource.microsoft.com/#mscorlib/system/string.cs,0a17bbac4851d0d4
// System.Web.Util.StringUtil.GetStringHashCode(System.String): http://referencesource.microsoft.com/#System.Web/Util/StringUtil.cs,c97063570b4e791a
public static int CombineHashCodes(IEnumerable<int> hashCodes)
{
    int hash1 = (5381 << 16) + 5381;
    int hash2 = hash1;

    int i = 0;
    foreach (var hashCode in hashCodes)
    {
        if (i % 2 == 0)
            hash1 = ((hash1 << 5) + hash1 + (hash1 >> 27)) ^ hashCode;
        else
            hash2 = ((hash2 << 5) + hash2 + (hash2 >> 27)) ^ hashCode;

        ++i;
    }

    return hash1 + (hash2 * 1566083941);
}

もう 1 つの実装は、System.Web.Util.HashCodeCombiner.CombineHashCodes(System.Int32, System.Int32)およびSystem.Array.CombineHashCodes(System.Int32, System.Int32)メソッドからのものです。これはより単純ですが、おそらく上記の方法ほど適切な分布はありません。

// System.Web.Util.HashCodeCombiner.CombineHashCodes(System.Int32, System.Int32): http://referencesource.microsoft.com/#System.Web/Util/HashCodeCombiner.cs,21fb74ad8bb43f6b
// System.Array.CombineHashCodes(System.Int32, System.Int32): http://referencesource.microsoft.com/#mscorlib/system/array.cs,87d117c8cc772cca
public static int CombineHashCodes(IEnumerable<int> hashCodes)
{
    int hash = 5381;

    foreach (var hashCode in hashCodes)
        hash = ((hash << 5) + hash) ^ hashCode;

    return hash;
}
于 2015-12-11T17:55:26.477 に答える
3

これは、 Special Sauceの見事に研究されたソリューションの再パッケージ化です。
値のタプル ( ITuple) を利用します。これにより、パラメータおよび
のデフォルトが許可されます。seedfactor

public static int CombineHashes(this ITuple tupled, int seed=1009, int factor=9176)
{
    var hash = seed;

    for (var i = 0; i < tupled.Length; i++)
    {
        unchecked
        {
            hash = hash * factor + tupled[i].GetHashCode();
        }
    }

    return hash;
}

使用法：

var hash1 = ("Foo", "Bar", 42).CombineHashes();    
var hash2 = ("Jon", "Skeet", "Constants").CombineHashes(seed=17, factor=31);
于 2020-01-20T11:37:42.453 に答える
0

入力ハッシュが同じサイズで、均等に分散されており、互いに関連していない場合、XOR は問題ありません。さらに、高速です。

私がこれを提案している状況は、あなたがやりたい場所です

H = hash(A) ^ hash(B); // A and B are different types, so there's no way A == B.

もちろん、A と B が妥当な (無視できない) 確率で同じ値にハッシュされることが期待できる場合は、この方法で XOR を使用しないでください。

于 2009-10-29T21:57:11.033 に答える
0

速度を求めていて衝突があまりない場合は、XOR が最速です。ゼロ付近でのクラスタリングを防ぐには、次のようにします。

finalHash = hash1 ^ hash2;
return finalHash != 0 ? finalHash : hash1;

もちろん、いくつかのプロトタイピングによって、パフォーマンスとクラスタリングについてのアイデアが得られるはずです。

于 2009-10-30T00:34:09.107 に答える
-11

自分で作成するのではなく、System.Security.Cryptography に組み込まれているハッシュ関数を使用することをお勧めします。

于 2009-10-29T23:05:58.233 に答える