42

Reflectorstring.GetHashCodeを使用するためのソースコードを一目見ると、次のことがわかります(mscorlib.dllバージョン4.0の場合)。

public override unsafe int GetHashCode()
{
    fixed (char* str = ((char*) this))
    {
        char* chPtr = str;
        int num = 0x15051505;
        int num2 = num;
        int* numPtr = (int*) chPtr;
        for (int i = this.Length; i > 0; i -= 4)
        {
            num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[0];
            if (i <= 2)
            {
                break;
            }
            num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[1];
            numPtr += 2;
        }
        return (num + (num2 * 0x5d588b65));
    }
}

の実装がGetHashCode指定されておらず、実装に依存していることに気付いたので、「GetHashCodeXまたはYの形式で実装されていますか?」という質問があります。本当に答えられません。私はいくつかのことに興味があります:

  1. ReflectorがDLLを正しく分解し、これGetHashCode(私の環境での)実装であるstring場合、この特定の実装に基づくオブジェクトがハッシュコードをキャッシュしないことを示すために、このコードを解釈するのは正しいですか?
  2. 答えがイエスだとすると、なぜそうなるのでしょうか。メモリコストは最小限であるように思われますが(32ビット整数が1つ増え、文字列自体のサイズと比較して池が低下します)、特に文字列が使用されている場合は、大幅な節約になります。のようなハッシュテーブルベースのコレクションのキーとしてDictionary<string, [...]>。また、stringクラスは不変であるため、によって返される値がGetHashCode変更されることはありません。

何が欠けている可能性がありますか?


更新:Andras Zoltanの閉会の辞に応えて:

ティムの答え(そこに+1)にもポイントがあります。彼が正しい場合、そして私が彼が正しいと思う場合、文字列が構築後に実際に不変であるという保証はありません。したがって、結果をキャッシュすることは間違っています。

おっと、おっ!これは興味深い点です(そしてそうです、それは非常に真実です)が、これがの実装で考慮されたことは本当に疑わしいGetHashCodeです。「したがって、結果をキャッシュするのは間違っている」というステートメントは、文字列に関するフレームワークの態度が「まあ、それらは不変であるはずですが、実際に開発者が卑劣になりたい場合は可変であるため、処理します」ということを意味しますそれら自体。」これは、フレームワークが文字列を表示する方法ではありません。それは非常に多くの方法でそれらの不変性に完全に依存しています(文字列リテラルのインターン、すべての長さゼロの文字列の割り当てstring.Emptyなど)、基本的に、文字列を変更すると、動作が完全に定義されておらず、予測できないコードを記述していることになります。

私のポイントは、この実装の作成者が「この文字列インスタンスが、公開されているクラスが不変であるにもかかわらず、呼び出し間で変更された場合はどうなるか」ということです。カジュアルな屋外バーベキューを計画している人が、「誰かが原子爆弾をパーティーに持ってきたらどうなるだろうか」と考えてみてはいかがでしょうか。ほら、誰かが原子爆弾を持ってきたら、パーティーは終わった。

4

6 に答える 6

28

明らかな潜在的な答え:それはメモリを消費するからです。

ここに費用便益分析があります:

コスト:文字列ごとに4バイト(およびGetHashCodeの呼び出しごとに簡単なテスト)。また、文字列オブジェクトを変更可能にします。これは、実装に注意する必要があることを意味します。ただし、ハッシュコードを常に事前に計算する場合を除きます。これは、文字列ごとに1回計算するコストであり、これまでに使用したかどうかは関係ありません。まったくハッシュします。

利点:複数回ハッシュされた文字列値のハッシュを再計算しないでください

多くの場合、文字列オブジェクトは非常に多く、複数回ハッシュされるものはごくわずかであるため、正味のコストが発生することをお勧めします。場合によっては、明らかにそうではありません。

どちらが頻繁に出てくるかを判断するのに適した立場にないと思います...MSがさまざまな実際のアプリをインストルメント化したことを願っています。(SunがJavaに対して同じことをしたことも願っています。Javaハッシュをキャッシュします...)

編集:私はこれについてEric Lippertに話しました(NDCは素晴らしいです:)そして基本的にそれ余分なメモリヒットと限られた利点についてです。

于 2010-06-16T13:51:22.413 に答える
13

Dictionary<string, ...>まず、IComparer を使用して文字列のハッシュコードを取得するため、必ずしも String.GetHashCode を使用するとは限らないため、この結果をキャッシュすることで実際に改善されるかどうかはわかりません。

StringComparer クラスの可能性のある呼び出しチェーンをたどると、最終的に System.Globalization.CompareInfo クラスに到達し、最終的にこのメソッドで終了します。

[SecurityCritical, SuppressUnmanagedCodeSecurity, DllImport("QCall",
   CharSet=CharSet.Unicode)]
private static extern int InternalGetGlobalizedHashCode(IntPtr handle, string
   localeName, string source, int length, int dwFlags);

そのライブラリ (ネイティブ メソッドのように見える) が、.Net ランタイム内で一度に取得できない、基礎となる .Net オブジェクト データ構造に基づく何らかの形式の内部キャッシュを使用しないかどうかはわかりません。

ただし、これに関して注意すべき重要なことは、文字の解釈方法に基づいて、1 つの文字列にさまざまなハッシュ コードが含まれる可能性があることです。確かに、この実装は文化に固有ではありません。そのため、これらの比較子には適していません。

したがって、追加のメモリストレージ要因になる可能性がありますが、実際には、文字列のインスタンスとともにハッシュコードを格納すると、呼び出し元、そして実際には .Net 内部開発チーム (!) が文字列がハッシュ コードは 1 つしかありませんが、実際にはそれをどのように解釈するかに完全に依存します - 一連のバイトとして (私たちのほとんどはそうではありません)、または一連の印刷可能な文字として。

パフォーマンスの観点から、Dictionary<,>etc によって使用されるこれらの比較子が内部実装を使用できないことも受け入れる場合、この結果をキャッシュしないことはおそらくあまり影響を与えません。実際には現実の世界で呼び出されます。ほとんどの場合、文字列のハッシュコードは他のメカニズムを介して計算される可能性が高いためです。

編集

ティムの答えにもポイントがあります(そこに+1)。彼が正しければ、そして私は彼が正しいと思うのですが、文字列が構築後に実際に不変であるという保証はありません。したがって、結果をキャッシュすることは間違っています。

追加の編集(!)

Dan は、文字列はネット領域内で不変であることを意図しているため、これに基づいて文字列は独自のハッシュコードを自由にキャッシュできるべきであると主張しています。ここでの問題は、.Net フレームワークが、特権リフレクションなどを含まない不変と思われる文字列を変更する正当な方法も提供することです。これは文字列の基本的な問題であり、制御できないバッファーへのポインターです。C# の世界では気にしないでください。メモリ バッファーのベクトル化と変更が一般的な C++ ではどうでしょうか。理想的にはそうすべきではないからといって、フレームワークがそうしないことを期待すべきだという意味ではありません。

.Net はたまたまこの機能を提供するため、これが Tim によって提案された種類のバイナリ攻撃に対する .Net チームによる設計上の決定であった場合、彼らはそれを考慮に入れたことは非常に賢明でした。彼らがそうしたかどうか、またはそれがまぐれによるものかどうかは、まったく別の問題です! :)

于 2010-06-16T14:07:18.173 に答える
12

ここで間違った結論を下した可能性がありますが、.NET String オブジェクトのコンテキストでは文字列は不変ですが、値を変更することは可能であるというのは本当ではないでしょうか?

たとえば、あなたがこれをやりたいと思っていたら...

String example = "Hello World";

unsafe
{
    fixed (char* strPointer = myString) {
        strPointer[1] = 'a';
    }
} 

...example同じ String オブジェクトを表すことはありませんが、今ではGetHashCode()?の異なる値を計算する値を使用しています。私はここで基地外かもしれませんが、これは(無意味ではないにしても)簡単に行うことができるため、問題が発生することもあります.

于 2010-06-16T14:21:23.100 に答える
1

これのもう1つの潜在的な理由は、インターンされた文字列(特に、コンパイラによって共有読み取り専用データとして追加された文字列)が、他の文字列とまったく同じ形式になる可能性があることです。これらの文字列が読み取り専用メモリにロードされるという事実は、これらのデータページをプロセス間で簡単に共有できることを意味しますが、ハッシュコードをキャッシュすることもできません。

しかし、他の人が述べているように、値をキャッシュしない主な理由は、追加のメモリ使用量がハッシュコードキャッシングの潜在的な節約をはるかに上回る可能性があることです。GetHashCodeの実行時間は、文字列の長さに対してO(N)であるため、ハッシュを繰り返すという最悪のシナリオには十分な制限があります。

于 2010-06-16T15:25:26.917 に答える
0

int 値は有効な HashCode です。これは、HashCode をまだ計算していないことを示すために使用できる -1 や 0 のようなデフォルトの int 値がないことを意味します。したがって、文字列が HashCode をキャッシュする場合、次のいずれかを行う必要があります。

  • HashCode の int フィールドと、HashCode がまだ計算されているかどうかのフラグとして機能する bool フィールドを用意し、最初に要求されたときにのみ HashCode を計算する (遅延評価)、または
  • HashCode の int フィールドを用意し、文字列が構築されるときに常にHashCode を計算します。

どちらの選択肢にも欠点があります。1 つ目はさらに追加のメモリを必要とし、2 つ目は HashCode を計算するためのパフォーマンス コストが必要になることはありません。

の場合を考えてみましょうDictionary<TKey,TValue>。Dictionary で使用される HashCode は、使用されている比較子によって異なります。デフォルトの比較子は、オブジェクトの通常の GetHashCode() メソッドを使用します。ただし、たとえば、大文字と小文字を区別しない比較子を使用する Dictionary を作成すると、Dictionary で使用される HashCode がその比較子によって生成され、String.GetHashCode(). では、どの HashCode が文字列をキャッシュするのでしょうか? 文字列は 2 つの辞書にあり、それぞれが異なる比較子を使用しており、どちらも通常の文字列 GetHashCode を使用していません。したがって、文字列は、辞書でさえ使用されていない HashCode をキャッシュしている可能性があります。

の場合、Dictionary<TKey,TValue>文字列を HashCode にキャッシュしてもパフォーマンス上の利点が得られない可能性が高いというさらに重要な理由があります。Dictionary の内部実装は、新しいエントリが追加されると次のことを行います。

  • 構築時に提供された等値比較子の GetHashCode() メソッドを使用して、キーの HashCode を計算します。何も指定されていない場合はデフォルトの比較子を使用します。
  • HashCode から符号ビットを取り除きます
  • 上記の変更された HashCode、キー、値、および同じバケットにマップされるエントリのリスト内の次のエントリのインデックスで構成される新しいエントリを格納します。

ディクショナリがキー ルックアップを行う場合、検索対象のキーの変更された (つまり正の) HashCode を計算し、HashCode がマップするバケットを取得してから、そのバケット内のエントリのリストを調べます。エントリが一致するかどうかを確認するには、最初に変更された HashCode が一致するかどうかを確認し (キーが等しい場合、HashCode も一致する必要があります)、それらが等しい場合は、2 つのキーも等しいかどうかを確認します。文字列の場合、このアルゴリズムは 2 つのことを達成します。まず単純な整数比較を使用して多くの文字列比較を回避し、文字列比較を行う価値があるかどうかを確認します。次に、Dictionary 内のすべてのキーの HashCode をキャッシュします。Dictionary の各キーの HashCode は、キーと値のペアが Dictionary に追加されるときに 1 回だけ計算されます。

(Dictionary が HashCode から符号ビットを削除する理由が気になる場合は、現在空のエントリ スロットの hashCode フィールドのマーカー フラグ値として -1 を使用しているためです。)

于 2012-06-22T23:11:50.253 に答える