68

パフォーマンスに影響があると思うので、ただ興味があります。文字列全体を考慮しますか？はいの場合、長い文字列では遅くなります。文字列の一部のみを考慮する場合、パフォーマンスが低下します (たとえば、文字列の先頭のみを考慮する場合、HashSet にほとんど同じ文字列が含まれている場合、パフォーマンスが低下します。

4

2 に答える 2

98

このような質問がある場合は、参照元のソース コードを必ず入手してください。逆コンパイラから見えるものよりも多くのものがあります。好みの .NET ターゲットに一致するものを選択してください。この方法は、バージョン間で大幅に変更されています。ここでは、Source.NET 4.5\4.6.0.0\net\clr\src\BCL\System\String.cs\604718\String.cs から取得した .NET 4.5 バージョンを再現します。

        public override int GetHashCode() { 

#if FEATURE_RANDOMIZED_STRING_HASHING
            if(HashHelpers.s_UseRandomizedStringHashing)
            { 
                return InternalMarvin32HashString(this, this.Length, 0);
            } 
#endif // FEATURE_RANDOMIZED_STRING_HASHING 

            unsafe { 
                fixed (char *src = this) {
                    Contract.Assert(src[this.Length] == '\0', "src[this.Length] == '\\0'");
                    Contract.Assert( ((int)src)%4 == 0, "Managed string should start at 4 bytes boundary");

#if WIN32
                    int hash1 = (5381<<16) + 5381; 
#else 
                    int hash1 = 5381;
#endif 
                    int hash2 = hash1;

#if WIN32
                    // 32 bit machines. 
                    int* pint = (int *)src;
                    int len = this.Length; 
                    while (len > 2) 
                    {
                        hash1 = ((hash1 << 5) + hash1 + (hash1 >> 27)) ^ pint[0]; 
                        hash2 = ((hash2 << 5) + hash2 + (hash2 >> 27)) ^ pint[1];
                        pint += 2;
                        len  -= 4;
                    } 

                    if (len > 0) 
                    { 
                        hash1 = ((hash1 << 5) + hash1 + (hash1 >> 27)) ^ pint[0];
                    } 
#else
                    int     c;
                    char *s = src;
                    while ((c = s[0]) != 0) { 
                        hash1 = ((hash1 << 5) + hash1) ^ c;
                        c = s[1]; 
                        if (c == 0) 
                            break;
                        hash2 = ((hash2 << 5) + hash2) ^ c; 
                        s += 2;
                    }
#endif
#if DEBUG 
                    // We want to ensure we can change our hash function daily.
                    // This is perfectly fine as long as you don't persist the 
                    // value from GetHashCode to disk or count on String A 
                    // hashing before string B.  Those are bugs in your code.
                    hash1 ^= ThisAssembly.DailyBuildNumber; 
#endif
                    return hash1 + (hash2 * 1566083941);
                }
            } 
        }

これはおそらくあなたが交渉した以上のものです。コードに少し注釈を付けます。

  • #if 条件付きコンパイル ディレクティブは、このコードをさまざまな .NET ターゲットに適合させます。FEATURE_XX 識別子は別の場所で定義されており、.NET ソース コード全体で機能を無効にしています。WIN32 は、ターゲットが 32 ビット バージョンのフレームワークである場合に定義され、64 ビット バージョンの mscorlib.dll は個別にビルドされ、GAC の別のサブディレクトリに格納されます。
  • s_UseRandomizedStringHashing 変数は、パスワードや暗号化などのハッシュを生成するために GetHashCode() を使用するなどの賢明でないことを行うプログラマーをトラブルから守るように設計された、ハッシュ アルゴリズムの安全なバージョンを有効にします。app.exe.config ファイルのエントリによって有効になります
  • fixedステートメントは、文字列のインデックスを安価に作成し続け、通常のインデクサーによって行われる境界チェックを回避します
  • 最初の Assert は、ループでの最適化を許可するために必要な、文字列が本来あるべきようにゼロで終了することを保証します
  • 2 番目の Assert は、ループのパフォーマンスを維持するために必要な 4 の倍数のアドレスに文字列が配置されるようにします。
  • ループは手動でアンロールされ、32 ビット バージョンではループごとに 4 文字を消費します。int* へのキャストは、2 文字 (2 x 16 ビット) を int (32 ビット) に格納するためのトリックです。ループの後の余分なステートメントは、長さが 4 の倍数ではない文字列を処理します。ゼロ ターミネータがハッシュに含まれる場合と含まれない場合があることに注意してください。長さが偶数の場合は含まれません。文字列内のすべての文字を調べて、質問に答えます
  • ループの 64 ビット バージョンは別の方法で行われ、手動で 2 だけアンロールされます。埋め込まれた 0 で早期に終了するため、すべての文字が表示されるわけではないことに注意してください。それ以外の場合は非常にまれです。これは非常に奇妙です。これは、文字列が非常に大きくなる可能性があることに関係していると推測できます。しかし、実用的な例を考えることができません
  • 最後のデバッグ コードは、実行間で再現可能なハッシュ コードに依存するフレームワーク内のコードがないことを保証します。
  • ハッシュアルゴリズムはかなり標準的です。値 1566083941 はマジック ナンバーであり、メルセンヌ ツイスターで一般的な素数です。
于 2013-03-02T16:10:19.217 に答える
6

ソースコード（ILSpyの提供）を調べると、文字列の長さにわたって反復されていることがわかります。

// string
[ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail), SecuritySafeCritical]
public unsafe override int GetHashCode()
{
    IntPtr arg_0F_0;
    IntPtr expr_06 = arg_0F_0 = this;
    if (expr_06 != 0)
    {
        arg_0F_0 = (IntPtr)((int)expr_06 + RuntimeHelpers.OffsetToStringData);
    }
    char* ptr = arg_0F_0;
    int num = 352654597;
    int num2 = num;
    int* ptr2 = (int*)ptr;
    for (int i = this.Length; i > 0; i -= 4)
    {
        num = ((num << 5) + num + (num >> 27) ^ *ptr2);
        if (i <= 2)
        {
            break;
        }
        num2 = ((num2 << 5) + num2 + (num2 >> 27) ^ ptr2[(IntPtr)4 / 4]);
        ptr2 += (IntPtr)8 / 4;
    }
    return num + num2 * 1566083941;
}
于 2013-03-02T12:34:07.660 に答える