GetHashCodeの.NETの手はどこから生まれているのか

はじめに

この記事は、.NETプラットフォームでのハッシュコードの生成に焦点を当てています。 このトピックは非常に興味深いものであり、自尊心のある.NET開発者なら誰でも知っているはずです。 さあ、行こう！

フィールド以外のオブジェクトには何が保存されますか？

記事の最初に、フィールドに加えて参照型のオブジェクトに保存されているものを学習します。



参照タイプの各オブジェクトには、ヘッダー（ヘッダー）と呼ばれる2つのフィールドがあります。このオブジェクトのタイプへのポインター（MethodTablePointer）と、同期インデックス（SyncBlockIndex）です。



彼らは何のために？



最初のフィールドは、各管理対象オブジェクトが実行時にそのタイプに関する情報を提供できるようにするために必要です。つまり、次のタイプを次々に配ることはできません。これはタイプセーフのために行われます。 このポインターは、メソッドの動的ディスパッチを実装するためにも使用されます;実際、このオブジェクトのメソッドはそれを通して呼び出されます。 Object.GetTypeメソッドは、実際にはMethodTablePointerポインターを正確に返します。



2番目のフィールドは、マルチスレッド環境に必要です。つまり、各オブジェクトをスレッドセーフで使用できるようにします。



CLRが読み込まれると、いわゆる同期ブロックのプールが作成されます。これらの同期ブロックの通常の配列と言えます。 オブジェクトがマルチスレッド環境で動作する必要がある場合（これはMonitor.EnterメソッドまたはC＃ロック言語構成を使用して行われます）、CLRはそのリストで空き同期ブロックを探し、そのインデックスをオブジェクトヘッダーの同じフィールドに書き込みます。 オブジェクトがマルチスレッド環境を必要としなくなるとすぐに、CLRはこのフィールドに-1の値を割り当てるだけで、同期ブロックを解放します。



同期ブロックは、実際にはC ++からのクリティカルセクションの新しい化身です。 CLRの作成者は、ほとんどのオブジェクトがマルチスレッド環境をまったく使用していないことを考慮すると、クリティカルセクション構造を各管理対象オブジェクトに関連付けるには費用がかかりすぎると感じました。



状況をよりよく理解するには、次の図を考慮してください。





この図は、ObjectTableとObjectTableが同じ型を指しているため、ObjectAとObjectBが同じ型であることを示しています。 ObjectCは異なるタイプです。 また、ObjectAとObjectCが同期ブロックのプールを使用することもわかります。つまり、実際にはマルチスレッド環境を使用します。 ObjectBは、SyncBlockIndex = -1であるため、プールを使用しません。



オブジェクトの保存方法を調べた後、ハッシュコードの生成に進むことができます。

GetHashCodeが参照型と連携する方法

GetHashCodeメソッドがマネージヒープ内のオブジェクトのアドレスを返すという事実は神話です。 これは、その一貫性の観点から、ガベージコレクター、ヒープの圧縮、オブジェクトのシフト、それに応じてそれらのすべてのアドレスを変更することはできません。

フレームワークの最初のバージョンでは、SyncBlockのフリーインデックスが参照型のハッシュコードとして使用されていたため、SyncBlockとは何かを説明して記事を始めたのは無駄ではありませんでした。 したがって、.NET 1.0および.NET 1.1では、GetHashCodeメソッドを呼び出すと、SyncBlockが作成され、SyncBlockIndexフィールドのオブジェクトヘッダーにそのインデックスが作成されました。 理解できるように、これはハッシュ関数の適切な実装ではありません。まず、メモリを占有する不必要な内部構造が作成され、その作成に時間が浪費されます。 ここにブログへのリンクがあります。CLR開発者の1人が、そのような実装は悪いことであり、次のバージョンでそれを変更すると言います。



.NET 2.0以降、ハッシュアルゴリズムが変更されました。 現在では、メソッドが実行されるスレッドの管理識別子を使用します。 SSCLI20での実装を信じている場合、メソッドは次のようになります。

inline DWORD GetNewHashCode() { // Every thread has its own generator for hash codes so that we won't get into a situation // where two threads consistently give out the same hash codes. // Choice of multiplier guarantees period of 2**32 - see Knuth Vol 2 p16 (3.2.1.2 Theorem A) DWORD multiplier = m_ThreadId*4 + 5; m_dwHashCodeSeed = m_dwHashCodeSeed*multiplier + 1; return m_dwHashCodeSeed; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このように、各スレッドにはハッシュコード用の独自のジェネレーターがあるため、2つのスレッドが同じハッシュコードを連続して生成する状況にはなりません。



前と同様に、ハッシュコードは1回計算され、SyncBlockIndexフィールドのオブジェクトヘッダーに格納されます（これはCLR最適化です）。 ここで問題は、GetHashCodeメソッドを呼び出した後、同期インデックスを使用する必要がある場合はどうでしょうか。 どこに記録しますか？ そして、ハッシュコードをどうしますか？



これらの質問に答えるために、SyncBlockの構造を検討してください。





GetHashCodeメソッドが最初に呼び出されると、CLRはハッシュコードを計算し、SyncBlockIndexフィールドに入力します。 SyncBlockがオブジェクトに関連付けられている場合、つまりSyncBlockIndexフィールドが使用されている場合、CLRはハッシュコードをSyncBlock自体に書き込みます。図は、ハッシュコードの格納を担当するSyncBlock内の場所を示しています。 SyncBlockが解放されるとすぐに、CLRはハッシュコードを本体からSyncBlockIndexオブジェクトのヘッダーにコピーします。 以上です。

重要な型に対するGetHashCodeの仕組み

ここで、GetHashCodeメソッドが重要な型に対してどのように機能するかについて話しましょう。 前もって言っておきますが、これは非常に興味深いものです。



最初に言うことは、CLRの作成者は、ユーザータイプに対してこのメ​​ソッドを常に再定義することをお勧めします。



実際、CLRには、重要な型に対するGetHashCodeメソッドの実装の2つのバージョンがあり、使用されるバージョンは完全に型自体に依存します。



最初のバージョン：

構造に参照フィールドがなく、フィールド間に空きスペースがない場合、GetHashCodeメソッドの高速バージョンが使用されます。 CLRは単なるxorです-構造体の4バイトごとに応答します。 構造の内容全体が関係するため、これは適切なハッシュです。 たとえば、bool型とint型のフィールドを持つ構造体には、3バイトの空き領域があります。これは、JITがフィールドを配置するときに、4バイトで整列するため、ハッシュコードを取得するために2番目のバージョンが使用されるためです。



ちなみに、このバージョンの実装では、.NET 4でのみ修正されたバグがありました。これは、decimal型のハッシュコードが正しく計算されなかったという事実から成りました。



コードを検討する

 decimal d1 = 10.0m; decimal d2 = 10.00000000000000000m;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

数値に関しては、d1とd2は同じですが、ビット表現は異なります（10進表現の性質のため）。 また、CLR xorは4バイトごとにumであるため（10進数は16バイトであるため4バイトのみです）、異なるハッシュコードが取得されます。 ちなみに、このバグは10進数だけでなく、このタイプを含むすべての構造でも現れ、高速バージョンを使用してハッシュコードを計算します。



2番目のバージョン：

構造体に参照フィールドが含まれているか、フィールド間に空きスペースがある場合、メソッドの低速バージョンが使用されます。 CLRは、構造の最初のフィールドを選択し、それに基づいてハッシュコードを作成します。 可能な場合、このフィールドは不変である必要があります。たとえば、文字列型です。そうでない場合、変更されるとハッシュコードも変更され、キーとして使用された場合、ハッシュテーブルで構造を見つけることができなくなります。 構造体の最初のフィールドが可変である場合、これによりGetHashCodeメソッドの標準ロジックが破壊されることがわかります。 これは、構造が可変であってはならないもう1つの理由です。 このフィールドの型へのポインター（MethodTablePointer）を持つこのフィールドのCLR xor-itハッシュコード。 CLRは静的フィールドを考慮しません。静的フィールドは同じ型のフィールドになる可能性があり、その結果、無限再帰に陥るからです。

ご注意

構造体には、独自のタイプのインスタンスフィールドを含めることはできません。 つまり、次のコードはコンパイルされません。

 public struct Node { int data; Node node; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これは、構造体がヌル値を取ることができないという事実によるものです。 次のコードは、これが不可能であることを確認しています。

 var myNode = new Node(); myNode.node.node.node.node.node.node.node.node.node.......
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ただし、独自の型の静的フィールドは、この構造体の型の単一のインスタンスに格納されるため、まったく受け入れられます。 つまり、次のコードは完全に有効です。

 public struct Node { int data; static Node node; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ご注意

状況をよりよく理解するには、次のコードを検討してください。

 var k1 = new KeyValuePair<int, int>(10, 29); var k2 = new KeyValuePair<int, int>(10, 31); Console.WriteLine("k1 - {0}, k2 - {1}", k1.GetHashCode(), k2.GetHashCode()); var v1 = new KeyValuePair<int, string>(10, "abc"); var v2 = new KeyValuePair<int, string>(10, "def"); Console.WriteLine("v1 - {0}, v2 - {1}", v1.GetHashCode(), v2.GetHashCode());
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

前者の場合、構造体には参照フィールドがなく、フィールド間の空き距離はありません。intフィールドは4バイトかかるため、ハッシュコードの計算には高速バージョンが使用され、コンソールに表示されます。



k1-411217769、k2-411217771



2番目のケースでは、構造に参照フィールド（文字列）があるため、低速バージョンが使用されます。 CLRはint型のフィールドをハッシュコードを生成するためのフィールドとして選択し、文字列フィールドは単に無視されます。その結果、以下がコンソールに出力されます：



v1-411217780、v2-411217780



CLR開発者が、ユーザーにとって重要なすべてのデータ型（および重要なだけでなく、すべて）がGetHashCodeメソッドを再定義すると言う理由は明らかだと思います。 最初に、例の2番目のケースのように、異なるオブジェクトのハッシュコードが等しい理由を誤解しないように、非常に高速に動作しない場合があります。



GetHashCodeメソッドをオーバーライドしない場合、ハッシュテーブルのキーとして重要なタイプを使用することで、パフォーマンスに大きな打撃を与えることができます。

GetHashCodeは文字列型でどのように機能しますか？

Stringクラスは、GetHashCodeメソッドをオーバーライドします。 .NET 4.5での実装は次のようになります。





これは64ビットマシン用のコードですが、ディレクティブ付きの一般的なコードを見ると





次に、32ビットまたは64ビットのマシンによって違いがあることに注意してください。



このメソッドの実装は、.NETの出力ごとに変わると言う必要があります。 これはEric Lippertによって書かれました。 彼は、.NETの次のリリースで実装を変更する可能性が高いため、標準パスによって生成されたハッシュをデータベースまたはディスクに格納しないことを警告しました。 そのため、.NETの最後の4つのリリース全体でそれが起こりました。



文字列型にハッシュを実装しても、結果がキャッシュされるわけではありません。 つまり、GetHashCodeメソッドを呼び出すたびに、文字列のハッシュコードを再計算します。 Eric Lippertによると、これはメモリを節約するために行われ、各文字列型オブジェクトに4バイトを追加しても価値はありません。 実装が非常に高速であることを考えると、これは正しいソリューションだと思います。



気づいた場合、GetHashCodeメソッドの実装では、以前は存在しなかったコードが表示されます。

 if (HashHelpers.s_UseRandomizedStringHashing) return string.InternalMarvin32HashString(this, this.Length, 0L);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

.NET 4.5には、各ドメインの文字列のハッシュコードを計算する機能があることがわかりました。 したがって、属性値を1に設定すると、メソッドが呼び出されたドメインに基づいてハッシュコードを計算することができます。 したがって、異なるドメインの同じ文字列は異なるハッシュコードを持ちます。 このハッシュコードを生成するメソッドは秘密であり、その実装は公開されていません。

デリゲートgethashcodeの仕組み

デリゲート用のGetHashCodeメソッドの実装の説明に移る前に、デリゲートの実装方法について説明します。



各デリゲートはMulticastDelegateクラスから継承し、MulticastDelegateクラスはDelegateクラスから継承します。 1つのクラスMulticastDelegateでできるため、この階層は歴史的に発展してきました。



DelegateクラスのGetHashCodeメソッドの実装は次のようになります

 public override int GetHashCode() { return this.GetType().GetHashCode(); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

つまり、デリゲート型のハッシュが実際に返されます。 呼び出しのための異なるメソッドを含む同じタイプのデリゲートは、常に同じハッシュコードを返すことがわかります。



ご存知のように、デリゲートにはメソッドのチェーンを含めることができます。つまり、1つのデリゲートを呼び出すと複数のメソッドが呼び出されます。この場合、メソッドの数に関係なく同じタイプのデリゲートは1つのハッシュコードを持つため、この実装は適切ではありません。したがって、MulticastDelegateでは、デリゲートの基礎となる各メソッドが関与するようにGetHashCodeメソッドが再定義されます。 ただし、メソッドの数とデリゲートの種類が同じ場合、ハッシュコードは同じになります。



MulticastDelegateクラスのメソッドの実装は次のようになります

 public override sealed int GetHashCode() { if (this.IsUnmanagedFunctionPtr()) return ValueType.GetHashCodeOfPtr(this._methodPtr) ^ ValueType.GetHashCodeOfPtr(this._methodPtrAux); object[] objArray = this._invocationList as object[]; if (objArray == null) return base.GetHashCode(); int num = 0; for (int index = 0; index < (int) this._invocationCount; ++index) num = num * 33 + objArray[index].GetHashCode(); return num; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ご存知のように、デリゲートは、メソッドが複数ある場合にのみ、メソッドを_invocationListリストに保存します。



デリゲートに含まれるメソッドが1つだけの場合、上記のコードではobjArray = nullであり、それに応じて、デリゲートのハッシュコードはデリゲートタイプのハッシュコードと等しくなります。

 object[] objArray = this._invocationList as object[]; if (objArray == null) return base.GetHashCode();
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

状況を明確にするために、次のコードを検討してください

 Func<int> f1 = () => 1; Func<int> f2 = () => 2;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これらのデリゲートのハッシュコードは、Func <int>型のハッシュコードと同じです。つまり、互いに等しいです。

 Func<int> f1 = () => 1; Func<int> f2 = () => 2; f1 += () => 3; f2 += () => 4;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

この場合、メソッドは異なりますが、デリゲートのハッシュコードも一致します。 この場合、次のコードを使用してハッシュコードを計算します。

 int num = 0; for (int index = 0; index < (int) this._invocationCount; ++index) num = num * 33 + objArray[index].GetHashCode(); return num;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

そして最後のケース

 Func<int> f1 = () => 1; Func<int> f2 = () => 2; f1 += () => 3; f1 += () => 5; f2 += () => 4;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これらのデリゲートのメソッドの数が等しくないため、ハッシュコードは異なります（各メソッドは結果のハッシュコードに影響します）。

匿名型に対するGetHashCodeの仕組み

ご存じのように、匿名型はC＃3.0の新機能です。 さらに、これはCLRがそれらについて何も知らないため、いわゆる構文糖と呼ばれる言語の機能です。



GetHashCodeメソッドは、各フィールドを使用するように再定義されます。 このような実装を使用すると、2つの匿名型は、すべてのフィールドが等しい場合にのみ同じハッシュコードを返します。 この実装により、匿名型はハッシュテーブルのキーに適したものになります。

 var newType = new { Name = "Timur", Age = 20, IsMale = true };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

そのような匿名型の場合、次のコードが生成されます。

 public override int GetHashCode() { return -1521134295 * (-1521134295 * (-1521134295 * -974875401 + EqualityComparer<string>.Default.GetHashCode(this.Name)) + EqualityComparer<int >.Default.GetHashCode(this.Age)) + EqualityComparer<bool>.Default.GetHashCode(this.IsMale); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ご注意

GetHashCodeメソッドがEqualsメソッドによってオーバーライドされている場合、それに応じてオーバーライドする必要があります。

 var newType = new { Name = "Timur", Age = 20, IsMale = true }; var newType1 = new { Name = "Timur", Age = 20, IsMale = true }; if (newType.Equals(newType1)) Console.WriteLine("method Equals return true"); else Console.WriteLine("method Equals return false"); if (newType == newType1) Console.WriteLine("operator == return true"); else Console.WriteLine("operator == return false");
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

以下がコンソールに表示されます。



メソッドEqualsはtrueを返します

演算子== falseを返します



匿名型は、ValueTypeで行ったように（リフレクションなしでのみ）すべてのフィールドをチェックするようにEqualsメソッドを再定義しますが、等値演算子は再定義しません。 したがって、Equalsメソッドは値で比較し、等価演算子は参照で比較します。



EqualsメソッドとGetHashCodeメソッドをオーバーライドする必要があるのはなぜですか？

匿名型はLINQでの作業を簡素化するために作成されたため、答えは明確になります。 匿名型は、LINQのグループおよび結合操作でハッシュキーとして便利に使用されます。

ご注意

おわりに

ご覧のとおり、ハッシュコードの生成は単純な問題ではありません。 良いハッシュを生成するには、多くの努力をする必要があり、CLR開発者は私たちの生活を楽にするために多くの譲歩をしなければなりませんでした。 ハッシュコードを生成することは良いことです。すべての場合において不可能です。したがって、カスタムタイプのGetHashCodeメソッドをオーバーライドして、特定の状況に合わせて調整することをお勧めします。



読んでくれてありがとう！ この記事がお役に立てば幸いです。



記事の更新された写真を親切に提供してくれたDreamWalkerのユーザーに感謝します。