Comment GetHashCode () de la chaîne C # est-il implémenté?

Je suis juste curieux parce que je suppose que cela aura un impact sur la performance. Est-ce qu’il considère la chaîne complète? Si oui, il sera lent sur une longue chaîne. Si elle ne considère qu’une partie de la chaîne, elle aura de mauvaises performances (par exemple, si elle ne considère que le début de la chaîne, elle aura de mauvaises performances si un HashSet contient principalement des chaînes avec la même chose).

Veillez à obtenir le code source de la source de référence lorsque vous avez des questions de ce type. Il y a beaucoup plus que ce que vous pouvez voir dans un décompilateur. Choisissez celui qui correspond à votre cible .NET préférée, la méthode a beaucoup changé entre les versions. Je vais juste en reproduire la version .NET 4.5 ici, extraite de Source.NET 4.5 \ 4.6.0.0 \ net \ clr \ src \ BCL \ System \ Ssortingng.cs \ 604718 \ Ssortingng.cs

  public override int GetHashCode() { #if FEATURE_RANDOMIZED_STRING_HASHING if(HashHelpers.s_UseRandomizedSsortingngHashing) { return InternalMarvin32HashSsortingng(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 ssortingng 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); } } } 

C'est peut-être plus que ce que vous aviez négocié, je vais un peu annoter le code:

  • Les directives de compilation conditionnelle #if adaptent ce code à différentes cibles .NET. Les identificateurs FEATURE_XX sont définis ailleurs et désactivent l'intégralité des ventes via le code source .NET. WIN32 est défini lorsque la cible est la version 32 bits de la structure, la version 64 bits de mscorlib.dll est générée séparément et stockée dans un sous-répertoire différent du GAC.
  • La variable s_UseRandomizedSsortingngHashing active une version sécurisée de l'algorithme de hachage, conçue pour empêcher les programmeurs de créer des problèmes, comme l'utilisation de GetHashCode () pour générer des mots de passe ou des mots de passe. Il est activé par une entrée dans le fichier app.exe.config
  • L'instruction fixe continue d'indexer la chaîne à bas prix, évite la vérification des limites effectuée par l'indexeur normal
  • Le premier Assert garantit que la chaîne est à zéro comme il se doit, nécessaire pour permettre l'optimisation dans la boucle
  • Le second Assert garantit que la chaîne est alignée sur une adresse multiple de 4, ce qui est nécessaire pour garder la boucle performante
  • La boucle est déroulée à la main, avec 4 caractères par boucle pour la version 32 bits. La conversion en int * est une astuce pour stocker 2 caractères (2 x 16 bits) dans un int (32 bits). Les instructions supplémentaires après la boucle traitent d'une chaîne dont la longueur n'est pas un multiple de 4. Notez que le terminateur zéro peut ou non être inclus dans le hachage, ce ne sera pas le cas si la longueur est égale. Il regarde tous les caractères de la chaîne, répondant à votre question
  • La version 64 bits de la boucle se fait différemment, déroulée à la main par 2. Notez qu'elle se termine tôt sur un zéro incorporé, donc ne regarde pas tous les caractères. Sinon très rare. C'est assez étrange, je ne peux que deviner que cela a quelque chose à voir avec les chaînes potentiellement très grandes. Mais ne peut pas penser à un exemple pratique
  • Le code de débogage à la fin garantit qu'aucun code dans le framework ne prend une dépendance sur le code de hachage reproductible entre les exécutions.
  • L'algorithme de hachage est assez standard. La valeur 1566083941 est un nombre magique, un nombre premier commun à un twister de Mersenne .

En examinant le code source (avec la permission de ILSpy ), nous pouvons voir qu’il parcourt la longueur de la chaîne.

 // ssortingng [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.OffsetToSsortingngData); } 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; }