オーバーライドされたSystem.Object.GetHashCodeに最適なアルゴリズムは何ですか?
-
06-07-2019 - |
質問
.NET System.Object.GetHashCode
メソッドは、.NETベースクラスライブラリ全体の多くの場所で使用されます。特に、コレクション内のアイテムをすばやく見つける場合、または同等性を判断する場合。パフォーマンスを低下させないように、カスタムクラスにGetHashCode
オーバーライドを実装する方法に関する標準アルゴリズム/ベストプラクティスはありますか?
解決
通常、Josh Blochの fabulous 有効なJava 。それは高速で、衝突を引き起こす可能性が低いかなり良いハッシュを作成します。 2つの異なる素数を選択します。 17および23、および実行:
public override int GetHashCode()
{
unchecked // Overflow is fine, just wrap
{
int hash = 17;
// Suitable nullity checks etc, of course :)
hash = hash * 23 + field1.GetHashCode();
hash = hash * 23 + field2.GetHashCode();
hash = hash * 23 + field3.GetHashCode();
return hash;
}
}
コメントで指摘されているように、代わりに乗算する大きな素数を選択する方が良い場合があります。どうやら486187739が良い...と私が小さな数で見たほとんどの例は素数を使用する傾向がありますが、非素数がしばしば使用される少なくとも同様のアルゴリズムがあります。 not-quite- FNV の例、たとえば、明らかにうまく機能する数字を使用しましたが、初期値は素数ではありません。 (ただし、乗算定数は 素数です。これがどれほど重要かはわかりません。)
これは、2つの主な理由により、ハッシュコードをXOR
する一般的な方法よりも優れています。 2つのint
フィールドを持つ型があるとします:
XorHash(x, x) == XorHash(y, y) == 0 for all x, y
XorHash(x, y) == XorHash(y, x) for all x, y
ところで、以前のアルゴリズムは、匿名型に対してC#コンパイラで現在使用されているアルゴリズムです。
このページには多くのオプションがあります。ほとんどの場合、上記は<!> quot;十分<< >> quot;覚えて正しいことをするのは非常に簡単です。 FNV の代替手段も同様に単純ですが、代わりに異なる定数とADD
を使用します<=>結合操作として。下のコードのように何かに見えますが、通常のFNVアルゴリズムは個々のバイトで動作するため、32ビットのハッシュ値ごとではなく、バイトごとに1回の反復を実行するように変更する必要があります。 FNVは可変長データ用にも設計されていますが、ここで使用している方法は常に同じ数のフィールド値用です。この回答に対するコメントは、ここでのコードは、上記の追加アプローチほど実際には(テストされたサンプルケースでは)動作しないことを示唆しています。
// Note: Not quite FNV!
public override int GetHashCode()
{
unchecked // Overflow is fine, just wrap
{
int hash = (int) 2166136261;
// Suitable nullity checks etc, of course :)
hash = (hash * 16777619) ^ field1.GetHashCode();
hash = (hash * 16777619) ^ field2.GetHashCode();
hash = (hash * 16777619) ^ field3.GetHashCode();
return hash;
}
}
注意すべきことの1つは、理想的には、ハッシュコードに依存するコレクションに追加した後に、等値依存(したがって、ハッシュコード依存)状態が変化しないようにすることです。
不変の参照型のGetHashCodeをオーバーライドできます。一般に、可変参照型の場合、次の場合にのみGetHashCodeをオーバーライドする必要があります。
- 可変ではないフィールドからハッシュコードを計算できます。または
- オブジェクトがそのハッシュコードに依存するコレクションに含まれている間、可変オブジェクトのハッシュコードが変更されないようにすることができます。
他のヒント
匿名タイプ
Microsoftは既に優れた汎用HashCodeジェネレーターを提供しています。プロパティ/フィールドの値を匿名型にコピーしてハッシュするだけです:
new { PropA, PropB, PropC, PropD }.GetHashCode();
これは、任意の数のプロパティで機能します。ボクシングは使用しません。匿名型のフレームワークに既に実装されているアルゴリズムを使用します。
ValueTuple-C#7の更新
@cactuaroidがコメントで言及しているように、値タプルを使用できます。これにより、いくつかのキーストロークが節約され、さらに重要なことに、純粋にスタック上で実行されます(ガベージなし):
(PropA, PropB, PropC, PropD).GetHashCode();
(注:匿名型を使用する元の手法はヒープ上にオブジェクト、つまりガベージを作成するようです。匿名型はクラスとして実装されますが、これはコンパイラによって最適化される場合があります。これらのオプションのベンチマークは興味深いでしょう、ただしtupleオプションの方が優れている必要があります。)
これが私のハッシュコードヘルパーです。
利点は、ジェネリック型引数を使用するため、ボクシングが発生しないことです:
public static class HashHelper
{
public static int GetHashCode<T1, T2>(T1 arg1, T2 arg2)
{
unchecked
{
return 31 * arg1.GetHashCode() + arg2.GetHashCode();
}
}
public static int GetHashCode<T1, T2, T3>(T1 arg1, T2 arg2, T3 arg3)
{
unchecked
{
int hash = arg1.GetHashCode();
hash = 31 * hash + arg2.GetHashCode();
return 31 * hash + arg3.GetHashCode();
}
}
public static int GetHashCode<T1, T2, T3, T4>(T1 arg1, T2 arg2, T3 arg3,
T4 arg4)
{
unchecked
{
int hash = arg1.GetHashCode();
hash = 31 * hash + arg2.GetHashCode();
hash = 31 * hash + arg3.GetHashCode();
return 31 * hash + arg4.GetHashCode();
}
}
public static int GetHashCode<T>(T[] list)
{
unchecked
{
int hash = 0;
foreach (var item in list)
{
hash = 31 * hash + item.GetHashCode();
}
return hash;
}
}
public static int GetHashCode<T>(IEnumerable<T> list)
{
unchecked
{
int hash = 0;
foreach (var item in list)
{
hash = 31 * hash + item.GetHashCode();
}
return hash;
}
}
/// <summary>
/// Gets a hashcode for a collection for that the order of items
/// does not matter.
/// So {1, 2, 3} and {3, 2, 1} will get same hash code.
/// </summary>
public static int GetHashCodeForOrderNoMatterCollection<T>(
IEnumerable<T> list)
{
unchecked
{
int hash = 0;
int count = 0;
foreach (var item in list)
{
hash += item.GetHashCode();
count++;
}
return 31 * hash + count.GetHashCode();
}
}
/// <summary>
/// Alternative way to get a hashcode is to use a fluent
/// interface like this:<br />
/// return 0.CombineHashCode(field1).CombineHashCode(field2).
/// CombineHashCode(field3);
/// </summary>
public static int CombineHashCode<T>(this int hashCode, T arg)
{
unchecked
{
return 31 * hashCode + arg.GetHashCode();
}
}
また、流methodなインターフェイスを提供する拡張メソッドがあるため、次のように使用できます。
public override int GetHashCode()
{
return HashHelper.GetHashCode(Manufacturer, PartN, Quantity);
}
またはこのように:
public override int GetHashCode()
{
return 0.CombineHashCode(Manufacturer)
.CombineHashCode(PartN)
.CombineHashCode(Quantity);
}
この目的で使用するヘルパーライブラリにハッシュクラスがあります。
/// <summary>
/// This is a simple hashing function from Robert Sedgwicks Hashing in C book.
/// Also, some simple optimizations to the algorithm in order to speed up
/// its hashing process have been added. from: www.partow.net
/// </summary>
/// <param name="input">array of objects, parameters combination that you need
/// to get a unique hash code for them</param>
/// <returns>Hash code</returns>
public static int RSHash(params object[] input)
{
const int b = 378551;
int a = 63689;
int hash = 0;
// If it overflows then just wrap around
unchecked
{
for (int i = 0; i < input.Length; i++)
{
if (input[i] != null)
{
hash = hash * a + input[i].GetHashCode();
a = a * b;
}
}
}
return hash;
}
その後、次のように使用できます:
public override int GetHashCode()
{
return Hashing.RSHash(_field1, _field2, _field3);
}
パフォーマンスを評価しなかったので、フィードバックを歓迎します。
Jon Skeetの実装を使用したヘルパークラスです。
public static class HashCode
{
public const int Start = 17;
public static int Hash<T>(this int hash, T obj)
{
var h = EqualityComparer<T>.Default.GetHashCode(obj);
return unchecked((hash * 31) + h);
}
}
使用法:
public override int GetHashCode()
{
return HashCode.Start
.Hash(_field1)
.Hash(_field2)
.Hash(_field3);
}
System.Int32の拡張メソッドの記述を避けたい場合:
public struct HashCode
{
private readonly int _value;
public HashCode(int value) => _value = value;
public static HashCode Start { get; } = new HashCode(17);
public static implicit operator int(HashCode hash) => hash._value;
public HashCode Hash<T>(T obj)
{
var h = EqualityComparer<T>.Default.GetHashCode(obj);
return unchecked(new HashCode((_value * 31) + h));
}
public override int GetHashCode() => _value;
}
依然として汎用的であり、ヒープ割り当てを回避し、まったく同じ方法で使用されます:
public override int GetHashCode()
{
// This time `HashCode.Start` is not an `Int32`, it's a `HashCode` instance.
// And the result is implicitly converted to `Int32`.
return HashCode.Start
.Hash(_field1)
.Hash(_field2)
.Hash(_field3);
}
マーティンのコメント後に更新:
obj != null
によりボクシングが発生したため、デフォルトの比較演算子に切り替えました。
編集(2018年5月):
EqualityComparer<T>.Default
ゲッターはJIT組み込み関数になりました-プルリクエストはこのブログのStephen Toub投稿。
Equals()が複数のフィールドを比較する場合、ほとんどの場合、GetHash()が1つのフィールドでハッシュするか、多くのフィールドでハッシュするかは問題ではありません。ハッシュの計算が本当に安く(割り当てなし、お願いします)、高速(重い計算なし、そして確かにデータベース接続なし)であり、良い分散を提供することを確認する必要があります。
ヘビーリフティングはEquals()メソッドの一部である必要があります。ハッシュは、できるだけ少ないアイテムでEquals()を呼び出すことができるようにするための非常に安価な操作である必要があります。
最後のヒント: GetHashCode()が複数のアプリケーション実行にわたって安定していることに依存しないでください。多くの.Netタイプは、再起動後もハッシュコードが同じままになることを保証していません。そのため、メモリ内のデータ構造にはGetHashCode()の値のみを使用する必要があります。
最近まで、私の答えはジョン・スキートのここに非常に近かったでしょう。ただし、最近、2のべき乗のハッシュテーブル、つまり内部テーブルのサイズが8、16、32などのハッシュテーブルを使用するプロジェクトを開始しました。素数のサイズを優先するのには十分な理由がありますが、 2のべき乗サイズの利点もいくつかあります。
そして、それはほとんど吸い込まれました。それで、少しの実験と研究の後、次のようにハッシュを再ハッシュし始めました。
public static int ReHash(int source)
{
unchecked
{
ulong c = 0xDEADBEEFDEADBEEF + (ulong)source;
ulong d = 0xE2ADBEEFDEADBEEF ^ c;
ulong a = d += c = c << 15 | c >> -15;
ulong b = a += d = d << 52 | d >> -52;
c ^= b += a = a << 26 | a >> -26;
d ^= c += b = b << 51 | b >> -51;
a ^= d += c = c << 28 | c >> -28;
b ^= a += d = d << 9 | d >> -9;
c ^= b += a = a << 47 | a >> -47;
d ^= c += b << 54 | b >> -54;
a ^= d += c << 32 | c >> 32;
a += d << 25 | d >> -25;
return (int)(a >> 1);
}
}
そして、私の2のべき乗のハッシュテーブルはもう吸いませんでした。
これは私を混乱させました。なぜなら、上記は機能しないはずだからです。もっと正確に言えば、元のGetHashCode()
が非常に特殊な方法で貧弱でない限り、動作しないはずです。
ハッシュコードを再混合しても、優れたハッシュコードを改善することはできません。これは、考えられる唯一の効果は、衝突がさらに発生するためです。
ハッシュコードを再混合しても、ひどいハッシュコードを改善することはできません。値53から多数の値18,3487,291への多数の衝突。
ハッシュコードの再混合は、その範囲全体で絶対衝突を回避するのに少なくともかなりうまくいったハッシュコード(2 32 の可能性のある値)のみを改善できますが、モジュロ化されたときに衝突を回避するのはひどくハッシュテーブルで実際に使用するためにダウンします。 2のべき乗のテーブルのより単純なモジュロはこれをより明確にしましたが、より一般的な素数のテーブルにもマイナスの影響を与えていましたが、それはそれほど明白ではありませんでした(リハッシュの追加作業が利益を上回るでしょう) 、しかし、利益はまだそこにあります)。
編集:オープンアドレス指定も使用していました。これにより、おそらく2のべき乗であるという事実よりも、衝突に対する感度が高くなります。
そして、のstring.GetHashCode()
実装がどれだけ邪魔されていたのか.NET (またはこちらを調べてください)は、この方法で改善できます(実行されるテストの順序で、衝突が少ないために30倍速くなります)、自分のハッシュコードをどれだけ改善できるか(それ以上に)邪魔になります。
過去にコーディングし、実際にこのサイトの回答の基礎として使用したすべてのGetHashCode()実装は、私が考えていたよりもずっと悪かった。多くの場合、それは<!> quot;十分に良い<!> quot;多くの用途に使用できますが、もっと良いものが欲しかったです。
それで、私はそのプロジェクトを片側に置いて(とにかくペットプロジェクトでした)、. NETで優れた、よく分散されたハッシュコードをすばやく生成する方法を検討し始めました。
最終的に、 SpookyHash を.NETに移植することに決めました。実際、上記のコードはSpookyHashを使用して32ビット入力から32ビット出力を生成する高速パスバージョンです。
今、SpookyHashは覚えやすいコードの一部ではありません。私のポートはさらに少ないので、速度を上げるために多くの部分をインライン化したためです。しかし、それがコードの再利用の目的です。
次に、そのプロジェクトを片側に置きました。元のプロジェクトがより良いハッシュコードを生成する方法の問題を生成したように、そのプロジェクトはより良いハッシュコードを生成する方法の問題を生成したからです.NET memcpy。
その後、私は戻ってきて、ほとんどすべてのネイティブ型(decimal
<!>#8224;を除く)をハッシュコードに簡単にフィードするために多くのオーバーロードを作成しました。
高速です。ボブジェンキンスは、特にアルゴリズムが最適化されている64ビットマシンでは、私が移植した元のコードがより高速であるため、ほとんどの功績に値します。<!>#8225;。
完全なコードは https://bitbucket.org/JonHanna/spookilysharp/src ただし、上記のコードは簡略化されていることを考慮してくださいそれのバージョン。
ただし、すでに記述されているため、より簡単に使用できます。
public override int GetHashCode()
{
var hash = new SpookyHash();
hash.Update(field1);
hash.Update(field2);
hash.Update(field3);
return hash.Final().GetHashCode();
}
シード値も取得するため、信頼できない入力に対処し、Hash DoS攻撃から保護する必要がある場合、稼働時間などに基づいてシードを設定し、攻撃者が結果を予測できないようにすることができます:
private static long hashSeed0 = Environment.TickCount;
private static long hashSeed1 = DateTime.Now.Ticks;
public override int GetHashCode()
{
//produce different hashes ever time this application is restarted
//but remain consistent in each run, so attackers have a harder time
//DoSing the hash tables.
var hash = new SpookyHash(hashSeed0, hashSeed1);
hash.Update(field1);
hash.Update(field2);
hash.Update(field3);
return hash.Final().GetHashCode();
}
*これでの大きな驚きは、(x << n) | (x >> -n)
を返した回転メソッドを手動でインライン化すると改善されたことです。ジッターがそれをインライン化したと確信していたでしょうが、プロファイリングはそうではないことを示しました。
<!>#8224; Equals()
は、C#からですが、.NETの観点からはネイティブではありません。それに関する問題は、それ自身の<=>は精度を重要として扱いますが、それ自身の<=>はそうではないことです。どちらも有効な選択肢ですが、そのように混在することはありません。独自のバージョンを実装する際、どちらかを選択する必要がありますが、どちらが欲しいかわかりません。
<!>#8225;比較のため。文字列で使用する場合、64ビットのSpookyHashは32ビットの<=>よりもかなり高速で、64ビットの<=>よりもわずかに高速です。32ビットのSpookyHashよりもかなり高速ですが、合理的な選択。
これは良いものです:
/// <summary>
/// Helper class for generating hash codes suitable
/// for use in hashing algorithms and data structures like a hash table.
/// </summary>
public static class HashCodeHelper
{
private static int GetHashCodeInternal(int key1, int key2)
{
unchecked
{
var num = 0x7e53a269;
num = (-1521134295 * num) + key1;
num += (num << 10);
num ^= (num >> 6);
num = ((-1521134295 * num) + key2);
num += (num << 10);
num ^= (num >> 6);
return num;
}
}
/// <summary>
/// Returns a hash code for the specified objects
/// </summary>
/// <param name="arr">An array of objects used for generating the
/// hash code.</param>
/// <returns>
/// A hash code, suitable for use in hashing algorithms and data
/// structures like a hash table.
/// </returns>
public static int GetHashCode(params object[] arr)
{
int hash = 0;
foreach (var item in arr)
hash = GetHashCodeInternal(hash, item.GetHashCode());
return hash;
}
/// <summary>
/// Returns a hash code for the specified objects
/// </summary>
/// <param name="obj1">The first object.</param>
/// <param name="obj2">The second object.</param>
/// <param name="obj3">The third object.</param>
/// <param name="obj4">The fourth object.</param>
/// <returns>
/// A hash code, suitable for use in hashing algorithms and
/// data structures like a hash table.
/// </returns>
public static int GetHashCode<T1, T2, T3, T4>(T1 obj1, T2 obj2, T3 obj3,
T4 obj4)
{
return GetHashCode(obj1, GetHashCode(obj2, obj3, obj4));
}
/// <summary>
/// Returns a hash code for the specified objects
/// </summary>
/// <param name="obj1">The first object.</param>
/// <param name="obj2">The second object.</param>
/// <param name="obj3">The third object.</param>
/// <returns>
/// A hash code, suitable for use in hashing algorithms and data
/// structures like a hash table.
/// </returns>
public static int GetHashCode<T1, T2, T3>(T1 obj1, T2 obj2, T3 obj3)
{
return GetHashCode(obj1, GetHashCode(obj2, obj3));
}
/// <summary>
/// Returns a hash code for the specified objects
/// </summary>
/// <param name="obj1">The first object.</param>
/// <param name="obj2">The second object.</param>
/// <returns>
/// A hash code, suitable for use in hashing algorithms and data
/// structures like a hash table.
/// </returns>
public static int GetHashCode<T1, T2>(T1 obj1, T2 obj2)
{
return GetHashCodeInternal(obj1.GetHashCode(), obj2.GetHashCode());
}
}
そしてその使用方法は次のとおりです。
private struct Key
{
private Type _type;
private string _field;
public Type Type { get { return _type; } }
public string Field { get { return _field; } }
public Key(Type type, string field)
{
_type = type;
_field = field;
}
public override int GetHashCode()
{
return HashCodeHelper.GetHashCode(_field, _type);
}
public override bool Equals(object obj)
{
if (!(obj is Key))
return false;
var tf = (Key)obj;
return tf._field.Equals(_field) && tf._type.Equals(_type);
}
}
上記のJon Skeetが投稿したアルゴリズムの別の流な実装がありますが、割り当てもボクシング操作も含まれていません。
public static class Hash
{
public const int Base = 17;
public static int HashObject(this int hash, object obj)
{
unchecked { return hash * 23 + (obj == null ? 0 : obj.GetHashCode()); }
}
public static int HashValue<T>(this int hash, T value)
where T : struct
{
unchecked { return hash * 23 + value.GetHashCode(); }
}
}
使用法:
public class MyType<T>
{
public string Name { get; set; }
public string Description { get; set; }
public int Value { get; set; }
public IEnumerable<T> Children { get; set; }
public override int GetHashCode()
{
return Hash.Base
.HashObject(this.Name)
.HashObject(this.Description)
.HashValue(this.Value)
.HashObject(this.Children);
}
}
コンパイラは、ジェネリック型の制約により、クラスでHashValue
が呼び出されないようにします。ただし、汎用引数を追加するとボクシング操作も追加されるため、HashObject
のコンパイラサポートはありません。
https://github.com/dotnet/coreclr/pull/14863、非常に簡単なハッシュコードを生成する新しい方法があります!書くだけ
public override int GetHashCode()
=> HashCode.Combine(field1, field2, field3);
これにより、実装の詳細を気にすることなく、高品質のハッシュコードが生成されます。
これは私の単純なアプローチです。これには、古典的なビルダーパターンを使用しています。タイプセーフ(ボクシング/アンボクシングなし)であり、.NET 2.0と互換性があります(拡張メソッドなどはありません)。
次のように使用されます:
public override int GetHashCode()
{
HashBuilder b = new HashBuilder();
b.AddItems(this.member1, this.member2, this.member3);
return b.Result;
}
そして、これがacutalビルダークラスです:
internal class HashBuilder
{
private const int Prime1 = 17;
private const int Prime2 = 23;
private int result = Prime1;
public HashBuilder()
{
}
public HashBuilder(int startHash)
{
this.result = startHash;
}
public int Result
{
get
{
return this.result;
}
}
public void AddItem<T>(T item)
{
unchecked
{
this.result = this.result * Prime2 + item.GetHashCode();
}
}
public void AddItems<T1, T2>(T1 item1, T2 item2)
{
this.AddItem(item1);
this.AddItem(item2);
}
public void AddItems<T1, T2, T3>(T1 item1, T2 item2, T3 item3)
{
this.AddItem(item1);
this.AddItem(item2);
this.AddItem(item3);
}
public void AddItems<T1, T2, T3, T4>(T1 item1, T2 item2, T3 item3,
T4 item4)
{
this.AddItem(item1);
this.AddItem(item2);
this.AddItem(item3);
this.AddItem(item4);
}
public void AddItems<T1, T2, T3, T4, T5>(T1 item1, T2 item2, T3 item3,
T4 item4, T5 item5)
{
this.AddItem(item1);
this.AddItem(item2);
this.AddItem(item3);
this.AddItem(item4);
this.AddItem(item5);
}
public void AddItems<T>(params T[] items)
{
foreach (T item in items)
{
this.AddItem(item);
}
}
}
ReSharper ユーザーは、ReSharper -> Edit -> Generate Code -> Equality Members
を使用してGetHashCode、Equalsなどを生成できます。
// ReSharper's GetHashCode looks like this
public override int GetHashCode() {
unchecked {
int hashCode = Id;
hashCode = (hashCode * 397) ^ IntMember;
hashCode = (hashCode * 397) ^ OtherIntMember;
hashCode = (hashCode * 397) ^ (RefMember != null ? RefMember.GetHashCode() : 0);
// ...
return hashCode;
}
}
ほとんどの作業はデータベース接続で行われます。つまり、すべてのクラスにはデータベースからの一意の識別子があります。常にデータベースのIDを使用してハッシュコードを生成します。
// Unique ID from database
private int _id;
...
{
return _id.GetHashCode();
}
ナイトコーダーのソリューションに非常によく似ていますが、必要に応じて素数を上げるのが簡単です。
PS:これは、口の中で少し吐き出す時間の1つです。これは、9つのデフォルトの1つのメソッドにリファクタリングできますが、遅くなるので、目を閉じて忘れようとします。 。
/// <summary>
/// Try not to look at the source code. It works. Just rely on it.
/// </summary>
public static class HashHelper
{
private const int PrimeOne = 17;
private const int PrimeTwo = 23;
public static int GetHashCode<T1, T2, T3, T4, T5, T6, T7, T8, T9, T10>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5, T6 arg6, T7 arg7, T8 arg8, T9 arg9, T10 arg10)
{
unchecked
{
int hash = PrimeOne;
hash = hash * PrimeTwo + arg1.GetHashCode();
hash = hash * PrimeTwo + arg2.GetHashCode();
hash = hash * PrimeTwo + arg3.GetHashCode();
hash = hash * PrimeTwo + arg4.GetHashCode();
hash = hash * PrimeTwo + arg5.GetHashCode();
hash = hash * PrimeTwo + arg6.GetHashCode();
hash = hash * PrimeTwo + arg7.GetHashCode();
hash = hash * PrimeTwo + arg8.GetHashCode();
hash = hash * PrimeTwo + arg9.GetHashCode();
hash = hash * PrimeTwo + arg10.GetHashCode();
return hash;
}
}
public static int GetHashCode<T1, T2, T3, T4, T5, T6, T7, T8, T9>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5, T6 arg6, T7 arg7, T8 arg8, T9 arg9)
{
unchecked
{
int hash = PrimeOne;
hash = hash * PrimeTwo + arg1.GetHashCode();
hash = hash * PrimeTwo + arg2.GetHashCode();
hash = hash * PrimeTwo + arg3.GetHashCode();
hash = hash * PrimeTwo + arg4.GetHashCode();
hash = hash * PrimeTwo + arg5.GetHashCode();
hash = hash * PrimeTwo + arg6.GetHashCode();
hash = hash * PrimeTwo + arg7.GetHashCode();
hash = hash * PrimeTwo + arg8.GetHashCode();
hash = hash * PrimeTwo + arg9.GetHashCode();
return hash;
}
}
public static int GetHashCode<T1, T2, T3, T4, T5, T6, T7, T8>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5, T6 arg6, T7 arg7, T8 arg8)
{
unchecked
{
int hash = PrimeOne;
hash = hash * PrimeTwo + arg1.GetHashCode();
hash = hash * PrimeTwo + arg2.GetHashCode();
hash = hash * PrimeTwo + arg3.GetHashCode();
hash = hash * PrimeTwo + arg4.GetHashCode();
hash = hash * PrimeTwo + arg5.GetHashCode();
hash = hash * PrimeTwo + arg6.GetHashCode();
hash = hash * PrimeTwo + arg7.GetHashCode();
hash = hash * PrimeTwo + arg8.GetHashCode();
return hash;
}
}
public static int GetHashCode<T1, T2, T3, T4, T5, T6, T7>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5, T6 arg6, T7 arg7)
{
unchecked
{
int hash = PrimeOne;
hash = hash * PrimeTwo + arg1.GetHashCode();
hash = hash * PrimeTwo + arg2.GetHashCode();
hash = hash * PrimeTwo + arg3.GetHashCode();
hash = hash * PrimeTwo + arg4.GetHashCode();
hash = hash * PrimeTwo + arg5.GetHashCode();
hash = hash * PrimeTwo + arg6.GetHashCode();
hash = hash * PrimeTwo + arg7.GetHashCode();
return hash;
}
}
public static int GetHashCode<T1, T2, T3, T4, T5, T6>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5, T6 arg6)
{
unchecked
{
int hash = PrimeOne;
hash = hash * PrimeTwo + arg1.GetHashCode();
hash = hash * PrimeTwo + arg2.GetHashCode();
hash = hash * PrimeTwo + arg3.GetHashCode();
hash = hash * PrimeTwo + arg4.GetHashCode();
hash = hash * PrimeTwo + arg5.GetHashCode();
hash = hash * PrimeTwo + arg6.GetHashCode();
return hash;
}
}
public static int GetHashCode<T1, T2, T3, T4, T5>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5)
{
unchecked
{
int hash = PrimeOne;
hash = hash * PrimeTwo + arg1.GetHashCode();
hash = hash * PrimeTwo + arg2.GetHashCode();
hash = hash * PrimeTwo + arg3.GetHashCode();
hash = hash * PrimeTwo + arg4.GetHashCode();
hash = hash * PrimeTwo + arg5.GetHashCode();
return hash;
}
}
public static int GetHashCode<T1, T2, T3, T4>(T1 arg1, T2 arg2, T3 arg3, T4 arg4)
{
unchecked
{
int hash = PrimeOne;
hash = hash * PrimeTwo + arg1.GetHashCode();
hash = hash * PrimeTwo + arg2.GetHashCode();
hash = hash * PrimeTwo + arg3.GetHashCode();
hash = hash * PrimeTwo + arg4.GetHashCode();
return hash;
}
}
public static int GetHashCode<T1, T2, T3>(T1 arg1, T2 arg2, T3 arg3)
{
unchecked
{
int hash = PrimeOne;
hash = hash * PrimeTwo + arg1.GetHashCode();
hash = hash * PrimeTwo + arg2.GetHashCode();
hash = hash * PrimeTwo + arg3.GetHashCode();
return hash;
}
}
public static int GetHashCode<T1, T2>(T1 arg1, T2 arg2)
{
unchecked
{
int hash = PrimeOne;
hash = hash * PrimeTwo + arg1.GetHashCode();
hash = hash * PrimeTwo + arg2.GetHashCode();
return hash;
}
}
}
プロパティが8つ以下の場合(できれば)、ここに別の選択肢があります。
ValueTuple
は構造体であり、堅実なGetHashCode
実装を持っているようです。
つまり、単純にこれを行うことができます。
// Yay, no allocations and no custom implementations!
public override int GetHashCode() => (this.PropA, this.PropB).GetHashCode();
HashHelper
のHashHelpers.Combine
の.NET Coreの現在の実装を見てみましょう。
これは、からのものです。 Combine
:
internal static int CombineHashCodes(int h1, int h2)
{
return HashHelpers.Combine(HashHelpers.Combine(HashHelpers.RandomSeed, h1), h2);
}
internal static int CombineHashCodes(int h1, int h2, int h3)
{
return HashHelpers.Combine(CombineHashCodes(h1, h2), h3);
}
そして、これは <=> :
public static readonly int RandomSeed = Guid.NewGuid().GetHashCode();
public static int Combine(int h1, int h2)
{
unchecked
{
// RyuJIT optimizes this to use the ROL instruction
// Related GitHub pull request: dotnet/coreclr#1830
uint rol5 = ((uint)h1 << 5) | ((uint)h1 >> 27);
return ((int)rol5 + h1) ^ h2;
}
}
英語:
- 左回転(循環シフト)h1で5ポジション。
- 結果とh1を一緒に追加します。
- h2との結果のXOR
- {static random seed、h1}で上記の操作を実行することから始めます。
- さらに項目ごとに、前の結果と次の項目(h2など)で操作を実行します。
このROL-5ハッシュコードアルゴリズムのプロパティについて詳しく知りたいと思います。
残念ながら、私たち自身の<=>を<=>に延期することは、私たちが望んでいるほど速くないかもしれません。関連するディスカッションのこのコメントは、<=>の直接呼び出しがより高性能。逆に、それは内部的なものなので、ここで得たものの多くを犠牲にして、コードをコピーする必要があります。また、ランダムシードを最初に<=>することを覚えておく必要があります。その手順をスキップした場合の結果はわかりません。
.NET Core 2.1以降
.NET Core 2.1以上を使用している場合、 System.HashCode 構造体。それを使用する2つの方法があります:
HashCode.Combine
Combine
メソッドを使用して、最大8つのオブジェクトを指定してハッシュコードを作成できます。
public override int GetHashCode() => HashCode.Combine(this.object1, this.object2);
HashCode.Add
Add
メソッドは、コレクションの処理に役立ちます:
public override int GetHashCode()
{
var hashCode = new HashCode();
hashCode.Add(this.object1);
foreach (var item in this.collection)
{
hashCode.Add(item);
}
return hashCode.ToHashCode();
}
GetHashCodeが簡単になりました
詳細およびコメント。
使用例
public class SuperHero
{
public int Age { get; set; }
public string Name { get; set; }
public List<string> Powers { get; set; }
public override int GetHashCode() =>
HashCode.Of(this.name).And(this.age).AndEach(this.powers);
}
実装
public struct HashCode : IEquatable<HashCode>
{
private const int EmptyCollectionPrimeNumber = 19;
private readonly int value;
private HashCode(int value) => this.value = value;
public static implicit operator int(HashCode hashCode) => hashCode.value;
public static bool operator ==(HashCode left, HashCode right) => left.Equals(right);
public static bool operator !=(HashCode left, HashCode right) => !(left == right);
public static HashCode Of<T>(T item) => new HashCode(GetHashCode(item));
public static HashCode OfEach<T>(IEnumerable<T> items) =>
items == null ? new HashCode(0) : new HashCode(GetHashCode(items, 0));
public HashCode And<T>(T item) =>
new HashCode(CombineHashCodes(this.value, GetHashCode(item)));
public HashCode AndEach<T>(IEnumerable<T> items)
{
if (items == null)
{
return new HashCode(this.value);
}
return new HashCode(GetHashCode(items, this.value));
}
public bool Equals(HashCode other) => this.value.Equals(other.value);
public override bool Equals(object obj)
{
if (obj is HashCode)
{
return this.Equals((HashCode)obj);
}
return false;
}
public override int GetHashCode() => this.value.GetHashCode();
private static int CombineHashCodes(int h1, int h2)
{
unchecked
{
// Code copied from System.Tuple a good way to combine hashes.
return ((h1 << 5) + h1) ^ h2;
}
}
private static int GetHashCode<T>(T item) => item?.GetHashCode() ?? 0;
private static int GetHashCode<T>(IEnumerable<T> items, int startHashCode)
{
var temp = startHashCode;
var enumerator = items.GetEnumerator();
if (enumerator.MoveNext())
{
temp = CombineHashCodes(temp, GetHashCode(enumerator.Current));
while (enumerator.MoveNext())
{
temp = CombineHashCodes(temp, GetHashCode(enumerator.Current));
}
}
else
{
temp = CombineHashCodes(temp, EmptyCollectionPrimeNumber);
}
return temp;
}
}
上記の答えとして選択された実装を使用して、浮動小数点と小数の問題に遭遇しました。
このテストは失敗します(浮動小数点数、2つの値を負に切り替えてもハッシュは同じです):
var obj1 = new { A = 100m, B = 100m, C = 100m, D = 100m};
var obj2 = new { A = 100m, B = 100m, C = -100m, D = -100m};
var hash1 = ComputeHash(obj1.A, obj1.B, obj1.C, obj1.D);
var hash2 = ComputeHash(obj2.A, obj2.B, obj2.C, obj2.D);
Assert.IsFalse(hash1 == hash2, string.Format("Hashcode values should be different hash1:{0} hash2:{1}",hash1,hash2));
ただし、このテストは(intを使用して)合格します:
var obj1 = new { A = 100m, B = 100m, C = 100, D = 100};
var obj2 = new { A = 100m, B = 100m, C = -100, D = -100};
var hash1 = ComputeHash(obj1.A, obj1.B, obj1.C, obj1.D);
var hash2 = ComputeHash(obj2.A, obj2.B, obj2.C, obj2.D);
Assert.IsFalse(hash1 == hash2, string.Format("Hashcode values should be different hash1:{0} hash2:{1}",hash1,hash2));
プリミティブ型にGetHashCodeを使用しないように実装を変更しましたが、うまく機能しているようです
private static int InternalComputeHash(params object[] obj)
{
unchecked
{
var result = (int)SEED_VALUE_PRIME;
for (uint i = 0; i < obj.Length; i++)
{
var currval = result;
var nextval = DetermineNextValue(obj[i]);
result = (result * MULTIPLIER_VALUE_PRIME) + nextval;
}
return result;
}
}
private static int DetermineNextValue(object value)
{
unchecked
{
int hashCode;
if (value is short
|| value is int
|| value is byte
|| value is sbyte
|| value is uint
|| value is ushort
|| value is ulong
|| value is long
|| value is float
|| value is double
|| value is decimal)
{
return Convert.ToInt32(value);
}
else
{
return value != null ? value.GetHashCode() : 0;
}
}
}
これは、Josh Blochの実装を実装する静的ヘルパークラスです。 <!> quot; prevent <!> quot;への明示的なオーバーロードを提供します。ボクシング、また、長いプリミティブ専用のハッシュを実装します。
等しい実装に一致する文字列比較を渡すことができます。
Hashの出力は常にintであるため、Hash呼び出しを連鎖させることができます。
using System;
using System.Collections;
using System.Collections.Generic;
using System.Reflection;
using System.Runtime.CompilerServices;
namespace Sc.Util.System
{
/// <summary>
/// Static methods that allow easy implementation of hashCode. Example usage:
/// <code>
/// public override int GetHashCode()
/// => HashCodeHelper.Seed
/// .Hash(primitiveField)
/// .Hsh(objectField)
/// .Hash(iEnumerableField);
/// </code>
/// </summary>
public static class HashCodeHelper
{
/// <summary>
/// An initial value for a hashCode, to which is added contributions from fields.
/// Using a non-zero value decreases collisions of hashCode values.
/// </summary>
public const int Seed = 23;
private const int oddPrimeNumber = 37;
/// <summary>
/// Rotates the seed against a prime number.
/// </summary>
/// <param name="aSeed">The hash's first term.</param>
/// <returns>The new hash code.</returns>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static int rotateFirstTerm(int aSeed)
{
unchecked {
return HashCodeHelper.oddPrimeNumber * aSeed;
}
}
/// <summary>
/// Contributes a boolean to the developing HashCode seed.
/// </summary>
/// <param name="aSeed">The developing HashCode value or seed.</param>
/// <param name="aBoolean">The value to contribute.</param>
/// <returns>The new hash code.</returns>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int Hash(this int aSeed, bool aBoolean)
{
unchecked {
return HashCodeHelper.rotateFirstTerm(aSeed)
+ (aBoolean
? 1
: 0);
}
}
/// <summary>
/// Contributes a char to the developing HashCode seed.
/// </summary>
/// <param name="aSeed">The developing HashCode value or seed.</param>
/// <param name="aChar">The value to contribute.</param>
/// <returns>The new hash code.</returns>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int Hash(this int aSeed, char aChar)
{
unchecked {
return HashCodeHelper.rotateFirstTerm(aSeed)
+ aChar;
}
}
/// <summary>
/// Contributes an int to the developing HashCode seed.
/// Note that byte and short are handled by this method, through implicit conversion.
/// </summary>
/// <param name="aSeed">The developing HashCode value or seed.</param>
/// <param name="aInt">The value to contribute.</param>
/// <returns>The new hash code.</returns>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int Hash(this int aSeed, int aInt)
{
unchecked {
return HashCodeHelper.rotateFirstTerm(aSeed)
+ aInt;
}
}
/// <summary>
/// Contributes a long to the developing HashCode seed.
/// </summary>
/// <param name="aSeed">The developing HashCode value or seed.</param>
/// <param name="aLong">The value to contribute.</param>
/// <returns>The new hash code.</returns>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int Hash(this int aSeed, long aLong)
{
unchecked {
return HashCodeHelper.rotateFirstTerm(aSeed)
+ (int)(aLong ^ (aLong >> 32));
}
}
/// <summary>
/// Contributes a float to the developing HashCode seed.
/// </summary>
/// <param name="aSeed">The developing HashCode value or seed.</param>
/// <param name="aFloat">The value to contribute.</param>
/// <returns>The new hash code.</returns>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int Hash(this int aSeed, float aFloat)
{
unchecked {
return HashCodeHelper.rotateFirstTerm(aSeed)
+ Convert.ToInt32(aFloat);
}
}
/// <summary>
/// Contributes a double to the developing HashCode seed.
/// </summary>
/// <param name="aSeed">The developing HashCode value or seed.</param>
/// <param name="aDouble">The value to contribute.</param>
/// <returns>The new hash code.</returns>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int Hash(this int aSeed, double aDouble)
=> aSeed.Hash(Convert.ToInt64(aDouble));
/// <summary>
/// Contributes a string to the developing HashCode seed.
/// </summary>
/// <param name="aSeed">The developing HashCode value or seed.</param>
/// <param name="aString">The value to contribute.</param>
/// <param name="stringComparison">Optional comparison that creates the hash.</param>
/// <returns>The new hash code.</returns>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int Hash(
this int aSeed,
string aString,
StringComparison stringComparison = StringComparison.Ordinal)
{
if (aString == null)
return aSeed.Hash(0);
switch (stringComparison) {
case StringComparison.CurrentCulture :
return StringComparer.CurrentCulture.GetHashCode(aString);
case StringComparison.CurrentCultureIgnoreCase :
return StringComparer.CurrentCultureIgnoreCase.GetHashCode(aString);
case StringComparison.InvariantCulture :
return StringComparer.InvariantCulture.GetHashCode(aString);
case StringComparison.InvariantCultureIgnoreCase :
return StringComparer.InvariantCultureIgnoreCase.GetHashCode(aString);
case StringComparison.OrdinalIgnoreCase :
return StringComparer.OrdinalIgnoreCase.GetHashCode(aString);
default :
return StringComparer.Ordinal.GetHashCode(aString);
}
}
/// <summary>
/// Contributes a possibly-null array to the developing HashCode seed.
/// Each element may be a primitive, a reference, or a possibly-null array.
/// </summary>
/// <param name="aSeed">The developing HashCode value or seed.</param>
/// <param name="aArray">CAN be null.</param>
/// <returns>The new hash code.</returns>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int Hash(this int aSeed, IEnumerable aArray)
{
if (aArray == null)
return aSeed.Hash(0);
int countPlusOne = 1; // So it differs from null
foreach (object item in aArray) {
++countPlusOne;
if (item is IEnumerable arrayItem) {
if (!object.ReferenceEquals(aArray, arrayItem))
aSeed = aSeed.Hash(arrayItem); // recursive call!
} else
aSeed = aSeed.Hash(item);
}
return aSeed.Hash(countPlusOne);
}
/// <summary>
/// Contributes a possibly-null array to the developing HashCode seed.
/// You must provide the hash function for each element.
/// </summary>
/// <param name="aSeed">The developing HashCode value or seed.</param>
/// <param name="aArray">CAN be null.</param>
/// <param name="hashElement">Required: yields the hash for each element
/// in <paramref name="aArray"/>.</param>
/// <returns>The new hash code.</returns>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int Hash<T>(this int aSeed, IEnumerable<T> aArray, Func<T, int> hashElement)
{
if (aArray == null)
return aSeed.Hash(0);
int countPlusOne = 1; // So it differs from null
foreach (T item in aArray) {
++countPlusOne;
aSeed = aSeed.Hash(hashElement(item));
}
return aSeed.Hash(countPlusOne);
}
/// <summary>
/// Contributes a possibly-null object to the developing HashCode seed.
/// </summary>
/// <param name="aSeed">The developing HashCode value or seed.</param>
/// <param name="aObject">CAN be null.</param>
/// <returns>The new hash code.</returns>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int Hash(this int aSeed, object aObject)
{
switch (aObject) {
case null :
return aSeed.Hash(0);
case bool b :
return aSeed.Hash(b);
case char c :
return aSeed.Hash(c);
case int i :
return aSeed.Hash(i);
case long l :
return aSeed.Hash(l);
case float f :
return aSeed.Hash(f);
case double d :
return aSeed.Hash(d);
case string s :
return aSeed.Hash(s);
case IEnumerable iEnumerable :
return aSeed.Hash(iEnumerable);
}
return aSeed.Hash(aObject.GetHashCode());
}
/// <summary>
/// This utility method uses reflection to iterate all specified properties that are readable
/// on the given object, excluding any property names given in the params arguments, and
/// generates a hashcode.
/// </summary>
/// <param name="aSeed">The developing hash code, or the seed: if you have no seed, use
/// the <see cref="Seed"/>.</param>
/// <param name="aObject">CAN be null.</param>
/// <param name="propertySelector"><see cref="BindingFlags"/> to select the properties to hash.</param>
/// <param name="ignorePropertyNames">Optional.</param>
/// <returns>A hash from the properties contributed to <c>aSeed</c>.</returns>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int HashAllProperties(
this int aSeed,
object aObject,
BindingFlags propertySelector
= BindingFlags.Instance
| BindingFlags.Public
| BindingFlags.GetProperty,
params string[] ignorePropertyNames)
{
if (aObject == null)
return aSeed.Hash(0);
if ((ignorePropertyNames != null)
&& (ignorePropertyNames.Length != 0)) {
foreach (PropertyInfo propertyInfo in aObject.GetType()
.GetProperties(propertySelector)) {
if (!propertyInfo.CanRead
|| (Array.IndexOf(ignorePropertyNames, propertyInfo.Name) >= 0))
continue;
aSeed = aSeed.Hash(propertyInfo.GetValue(aObject));
}
} else {
foreach (PropertyInfo propertyInfo in aObject.GetType()
.GetProperties(propertySelector)) {
if (propertyInfo.CanRead)
aSeed = aSeed.Hash(propertyInfo.GetValue(aObject));
}
}
return aSeed;
}
/// <summary>
/// NOTICE: this method is provided to contribute a <see cref="KeyValuePair{TKey,TValue}"/> to
/// the developing HashCode seed; by hashing the key and the value independently. HOWEVER,
/// this method has a different name since it will not be automatically invoked by
/// <see cref="Hash(int,object)"/>, <see cref="Hash(int,IEnumerable)"/>,
/// or <see cref="HashAllProperties"/> --- you MUST NOT mix this method with those unless
/// you are sure that no KeyValuePair instances will be passed to those methods; or otherwise
/// the generated hash code will not be consistent. This method itself ALSO will not invoke
/// this method on the Key or Value here if that itself is a KeyValuePair.
/// </summary>
/// <param name="aSeed">The developing HashCode value or seed.</param>
/// <param name="keyValuePair">The value to contribute.</param>
/// <returns>The new hash code.</returns>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int HashKeyAndValue<TKey, TValue>(this int aSeed, KeyValuePair<TKey, TValue> keyValuePair)
=> aSeed.Hash(keyValuePair.Key)
.Hash(keyValuePair.Value);
/// <summary>
/// NOTICE: this method is provided to contribute a collection of <see cref="KeyValuePair{TKey,TValue}"/>
/// to the developing HashCode seed; by hashing the key and the value independently. HOWEVER,
/// this method has a different name since it will not be automatically invoked by
/// <see cref="Hash(int,object)"/>, <see cref="Hash(int,IEnumerable)"/>,
/// or <see cref="HashAllProperties"/> --- you MUST NOT mix this method with those unless
/// you are sure that no KeyValuePair instances will be passed to those methods; or otherwise
/// the generated hash code will not be consistent. This method itself ALSO will not invoke
/// this method on a Key or Value here if that itself is a KeyValuePair or an Enumerable of
/// KeyValuePair.
/// </summary>
/// <param name="aSeed">The developing HashCode value or seed.</param>
/// <param name="keyValuePairs">The values to contribute.</param>
/// <returns>The new hash code.</returns>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int HashKeysAndValues<TKey, TValue>(
this int aSeed,
IEnumerable<KeyValuePair<TKey, TValue>> keyValuePairs)
{
if (keyValuePairs == null)
return aSeed.Hash(null);
foreach (KeyValuePair<TKey, TValue> keyValuePair in keyValuePairs) {
aSeed = aSeed.HashKeyAndValue(keyValuePair);
}
return aSeed;
}
}
}
複数のハッシュ方法でマイクロソフトがリード...
//for classes that contain a single int value
return this.value;
//for classes that contain multiple int value
return x ^ y;
//for classes that contain single number bigger than int
return ((int)value ^ (int)(value >> 32));
//for classes that contain class instance fields which inherit from object
return obj1.GetHashCode();
//for classes that contain multiple class instance fields which inherit from object
return obj1.GetHashCode() ^ obj2.GetHashCode() ^ obj3.GetHashCode();
複数の大きな整数に対してこれを使用できると推測できます:
int a=((int)value1 ^ (int)(value1 >> 32));
int b=((int)value2 ^ (int)(value2 >> 32));
int c=((int)value3 ^ (int)(value3 >> 32));
return a ^ b ^ c;
また、マルチタイプについても同じ:int
を使用してすべてを最初にGetHashCode()
に変換
int値がxor'edされ、結果がハッシュになります。
ハッシュをIDとして使用する(一意の値を意味する)場合、ハッシュは自然に数桁に制限されます。ハッシュアルゴリズムでは5バイト、少なくともMD5だったと思います。
複数の値をハッシュ値に変換できますが、それらの一部は同じであるため、識別子として使用しないでください。 (おそらくいつかあなたのコンポーネントを使用するつもりです)