Pourquoi le hashCode () de Ssortingng ne cache-t-il pas 0?

J’ai remarqué dans le code source Java 6 de Ssortingng que hashCode ne cache que des valeurs autres que 0. La différence de performances est illustrée par l’extrait de code suivant:

public class Main{ static void test(Ssortingng s) { long start = System.currentTimeMillis(); for (int i = 0; i < 10000000; i++) { s.hashCode(); } System.out.format("Took %d ms.%n", System.currentTimeMillis() - start); } public static void main(String[] args) { String z = "Allocator redistricts; strict allocator redistricts strictly."; test(z); test(z.toUpperCase()); } } 

L’exécuter dans ideone.com donne la sortie suivante:

 Took 1470 ms. Took 58 ms. 

Donc mes questions sont:

  • Pourquoi le hashCode () de Ssortingng ne cache-t-il pas 0?
  • Quelle est la probabilité qu’une chaîne Java soit hachée à 0?
  • Quelle est la meilleure façon d’éviter la pénalisation des performances de recalculer la valeur de hachage chaque fois que les chaînes sont hachées à 0?
  • Est-ce la meilleure façon de mettre en cache les valeurs? (c.-à-d. cachez tous sauf un?)

Pour votre amusement, chaque ligne ici est une chaîne de caractères hachée à 0:

 pollinating sandboxes amusement & hemophilias schoolworks = perversive electrolysissweeteners.net constitutionalunstableness.net grinnerslaphappier.org BLEACHINGFEMININELY.NET WWW.BUMRACEGOERS.ORG WWW.RACCOONPRUDENTIALS.NET Microcomputers: the unredeemed lollipop... Incentively, my dear, I don't tessellate a derangement. A person who never yodelled an apology, never preened vocalizing transsexuals. 

Vous vous inquiétez de rien. Voici une façon de penser à ce problème.

Supposons que vous ayez une application qui ne fait que restr assis autour des chaînes de hachage toute l’année. Disons qu’il faut un millier de chaînes, toutes en mémoire, appelle hashCode () de façon répétée à tour de rôle, un million de fois, puis récupère mille nouvelles chaînes et recommence.

Et supposons que la probabilité que le code de hachage d’une chaîne soit nul était en réalité très supérieure à 1/2 ^ 32. Je suis sûr que c’est un peu plus grand que 1/2 ^ 32, mais disons que c’est bien pire que ça, comme 1/2 ^ 16 (la racine carrée! Maintenant c’est bien pire!).

Dans cette situation, les ingénieurs d’Oracle ont davantage à gagner à améliorer la manière dont les codes de hachage de ces chaînes sont mis en cache que n’importe qui d’autre. Donc, vous leur écrivez et leur demandez de résoudre le problème. Et ils travaillent leur magie de sorte que chaque fois que s.hashCode () est à zéro, il retourne instantanément (même la première fois! Une amélioration de 100%!). Et disons qu’ils le font sans dégrader les performances pour aucun autre cas.

Hourra! Maintenant, votre application est … Voyons voir … 0.0015% plus vite!

Ce qui prenait une journée entière ne prend maintenant que 23 heures, 57 minutes et 48 secondes!

Et rappelez-vous, nous avons mis en place le scénario pour donner tous les avantages possibles du doute, souvent à un degré ridicule.

Cela vous semble-t-il utile?

EDIT: depuis que j’ai posté ça il y a quelques heures, j’ai laissé un de mes processeurs courir à la recherche de phrases de deux mots avec zéro code de hachage. Jusqu’à présent, il est arrivé à: bequirtle zorillo, schtoff chronogrammique, cloître ressemblif contersive, organzine de creashaks, boulderhead drumwood, exercable électroanalytique, et de préférence non-précieux. C’est à peu près 2 ^ 35 possibilités, donc avec une dissortingbution parfaite, nous nous attendrions à en voir seulement 8. Évidemment, au moment où cela sera fait, nous aurons quelques fois autant, mais pas excessivement. Ce qui est plus important, c’est que j’ai maintenant quelques noms de groupes / noms d’albums intéressants! Pas de vol juste!

Il utilise 0 pour indiquer “Je n’ai pas encore défini le hashcode”. L’alternative serait d’utiliser un indicateur booléen séparé, ce qui prendrait plus de mémoire. (Ou pour ne pas mettre le hashcode en cache, bien sûr.)

Je ne m’attends pas à beaucoup de chaînes de hachage à 0; sans doute, il serait logique que la routine de hachage évite délibérément 0 (par exemple, traduise un hachage de 0 à 1 et le cache). Cela augmenterait les collisions mais éviterait de ressasser. Il est toutefois trop tard pour le faire maintenant, car l’algorithme Ssortingng hashCode est explicitement documenté.

Pour ce qui est de savoir si c’est une bonne idée en général: c’est un mécanisme de cache certainement efficace, et pourrait (voir edit) être encore mieux avec un changement pour éviter de réutiliser les valeurs qui aboutissent à un hachage de 0. les données qui ont amené Sun à croire que cela en valait la peine – cela prend 4 octets supplémentaires pour chaque chaîne jamais créée, aussi souvent ou rarement qu’elle soit hachée, et le seul avantage est pour les chaînes qui sont hachées plus d’une fois .

EDIT: Comme le fait remarquer KevinB dans un commentaire ailleurs, la suggestion “Eviter 0” ci-dessus peut bien avoir un coût net car elle aide un cas très rare , mais nécessite une comparaison supplémentaire pour chaque calcul de hachage.

Je pense qu’il y a quelque chose d’important que les autres réponses manquent jusqu’à présent: la valeur zéro existe pour que le mécanisme hashCode-cache fonctionne de manière robuste dans un environnement multi-thread.

Si vous aviez deux variables, comme cachedHashCode lui-même et une valeur booléenne isHashCodeCalculated pour indiquer si cachedHashCode avait été calculé, vous auriez besoin de la synchronisation des threads pour que les choses fonctionnent dans un environnement multithread. Et la synchronisation serait néfaste pour les performances, d’autant plus que les chaînes sont très fréquemment réutilisées dans plusieurs threads.

Ma compréhension du modèle de mémoire Java est un peu sommaire, mais voici en gros ce qui se passe:

  1. Lorsque plusieurs threads accèdent à une variable (comme le hashCode en cache), rien ne garantit que chaque thread verra la dernière valeur. Si une variable commence à zéro, alors A la met à jour (la met à une valeur différente de zéro), puis le thread B le lit peu après, le thread B peut encore voir la valeur zéro.

  2. Il y a un autre problème avec l’access aux valeurs partagées à partir de plusieurs threads (sans synchronisation) – vous pouvez finir par essayer d’utiliser un object qui n’a été que partiellement initialisé (la construction d’un object n’est pas un processus atomique). Les lectures et écritures multi-threads de primitives 64 bits comme les longues et les doubles ne sont pas nécessairement atomiques, donc si deux threads essaient de lire et de modifier la valeur d’un long ou d’un double, un thread peut voir quelque chose de bizarre et partiellement défini . Ou quelque chose comme ça de toute façon. Il y a des problèmes similaires si vous essayez d’utiliser deux variables ensemble, comme cachedHashCode et isHashCodeCalculated – un thread peut facilement apparaître et voir la dernière version de l’une de ces variables, mais une ancienne version d’une autre.

  3. La manière habituelle de contourner ces problèmes de multithreading consiste à utiliser la synchronisation. Par exemple, vous pouvez mettre tous les access au hashCode mis en cache dans un bloc synchronisé, ou utiliser le mot-clé volatile (mais soyez prudent car la sémantique prête à confusion).

  4. Cependant, la synchronisation ralentit les choses. Mauvaise idée pour quelque chose comme un hashCode de chaîne. Les chaînes sont très souvent utilisées comme clés dans HashMaps. Vous avez donc besoin de la méthode hashCode pour obtenir de bons résultats, y compris dans les environnements multithread.

  5. Les primitives Java de 32 bits ou moins, telles que int, sont spéciales. Contrairement à, disons, un long (valeur de 64 bits), vous pouvez être sûr de ne jamais lire une valeur partiellement initialisée d’un int (32 bits). Lorsque vous lisez un int sans synchronisation, vous ne pouvez pas être sûr d’obtenir la dernière valeur définie, mais vous pouvez être sûr que la valeur que vous obtenez est explicitement définie à un moment donné par votre thread. un autre fil

Le mécanisme de mise en cache hashCode dans java.lang.Ssortingng est configuré pour s’appuyer sur le point 5 ci-dessus. Vous pourriez mieux le comprendre en regardant la source de java.lang.Ssortingng.hashCode (). Fondamentalement, avec plusieurs threads appelant hashCode à la fois, hashCode pourrait finir par être calculé plusieurs fois (si la valeur calculée est zéro ou si plusieurs threads appellent hashCode en même temps et que les deux voient une valeur mise en cache nulle), () renverra toujours la même valeur. Il est donc robuste et performant (car il n’y a pas de synchronisation pour agir comme un goulot d’étranglement dans des environnements multithread).

Comme je l’ai dit, ma compréhension du modèle de mémoire Java est un peu sommaire, mais je suis sûr que j’ai bien compris l’essentiel. En fin de compte, c’est un idiome très intelligent pour mettre en cache le hashCode sans la surcharge de la synchronisation.

0 n’est pas mis en cache car l’implémentation interprète une valeur mise en cache de 0 comme “valeur mise en cache pas encore initialisée”. L’alternative aurait été d’utiliser un java.lang.Integer , où null impliquait que la valeur n’était pas encore mise en cache. Cependant, cela aurait entraîné une surcharge de stockage supplémentaire.

En ce qui concerne la probabilité qu’un code de hachage d’une chaîne soit calculé comme 0, je dirais que la probabilité est assez faible et peut se produire dans les cas suivants:

  • La chaîne est vide (bien que le recalcul de ce code de hachage à chaque fois soit effectivement O (1)).
  • Un débordement se produit eg Integer.MAX_VALUE + h(c1) + h(c2) + ... h(cn) == 0 code de hachage calculé final est 0 ( eg Integer.MAX_VALUE + h(c1) + h(c2) + ... h(cn) == 0 ).
  • La chaîne ne contient que le caractère Unicode 0. Très improbable car il s’agit d’un caractère de contrôle sans signification dans le monde du papier (!):

De Wikipedia :

Le code 0 (nom de code ASCII NUL) est un cas particulier. Dans les bandes de papier, c’est le cas lorsqu’il n’y a pas de trous. Il convient de traiter ceci comme un caractère de remplissage sans autre sens .

Cela s’avère être une bonne question, liée à une vulnérabilité de sécurité .

“Lors du hachage d’une chaîne, Java met également en cache la valeur de hachage dans l’atsortingbut de hachage, mais uniquement si le résultat est différent de zéro. La valeur cible zéro est donc particulièrement intéressante pour un attaquant car elle empêche la mise en mémoire cache.”

  • Pourquoi le hashCode () de Ssortingng ne cache-t-il pas 0?

La valeur zéro est réservée à la signification “le code de hachage n’est pas mis en cache”.

  • Quelle est la probabilité qu’une chaîne Java soit hachée à 0?

Selon le Javadoc, la formule pour le code de hachage d’un Ssortingng est la suivante:

 s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] 

en utilisant l’arithmétique int , où s[i] est le caractère ith de la chaîne et n la longueur de la chaîne. (Le hachage de la chaîne vide est défini sur zéro en tant que cas particulier.)

Mon intuition est que la fonction de hashcode comme ci-dessus donne une répartition uniforme des valeurs de hachage Ssortingng dans la plage des valeurs int . Un étalement uniforme signifierait que la probabilité d’un hachage de chaîne généré de manière aléatoire à zéro est de 1 sur 2 ^ 32.

  • Quelle est la meilleure façon d’éviter la pénalisation des performances de recalculer la valeur de hachage chaque fois que les chaînes sont hachées à 0?

La meilleure stratégie consiste à ignorer le problème. Si vous hachez à plusieurs resockets la même valeur de chaîne, votre algorithme a quelque chose d’étrange.

  • Est-ce la meilleure façon de mettre en cache les valeurs? (c.-à-d. cachez tous sauf un?)

C’est un compromis entre l’espace et le temps. AFAIK, les alternatives sont:

  • Ajoutez un indicateur cached à chaque object Ssortingng, en faisant en sorte que chaque chaîne Java prenne un mot supplémentaire.

  • Utilisez le bit supérieur du membre de hash comme indicateur mis en cache. De cette façon, vous pouvez mettre en cache toutes les valeurs de hachage, mais vous ne disposez que de la moitié des valeurs de hachage de chaînes possibles.

  • Ne mettez pas en cache les codes de hachage sur les chaînes.

Je pense que les concepteurs de Java ont fait le bon appel pour Ssortingngs, et je suis sûr qu’ils ont effectué un profilage complet qui confirme la validité de leur décision. Cependant, cela ne signifie pas que ce serait toujours le meilleur moyen de gérer la mise en cache.

(Notez qu’il y a deux valeurs de chaîne “communes” qui mettent à zéro le hachage; la chaîne vide et la chaîne ne contenant qu’un caractère NUL. Cependant, le coût de calcul des codes de hachage pour ces valeurs est faible par rapport au coût de calcul hashcode pour une valeur de chaîne typique.)

Eh bien les gens, il garde 0 parce que si c’est la longueur zéro, il finira de toute façon par zéro.

Et il ne faut pas longtemps pour comprendre que le len est nul et que le hashcode doit l’être également.

Donc, pour votre code-reviewz! La voici dans toute sa gloire Java 8:

  public int hashCode() { int h = hash; if (h == 0 && value.length > 0) { char val[] = value; for (int i = 0; i < value.length; i++) { h = 31 * h + val[i]; } hash = h; } return h; } 

Comme vous pouvez le voir, cela retournera toujours un zéro rapide si la chaîne est vide:

  if (h == 0 && value.length > 0) ... 

La suggestion “Eviter 0” semble appropriée pour être recommandée, car elle aide à résoudre un problème réel (dégradation des performances sérieusement inattendue dans des cas constructibles pouvant être fournis par un attaquant) pour le coût modeste d’une opération de twig avant une écriture. Il rest une «dégradation inattendue des performances» qui peut être exercée si les seules choses entrant dans un hachage défini correspondent à la valeur ajustée spéciale. Mais au pire, il s’agit d’une dégradation de 2 fois plus que de la limite.

Bien entendu, l’implémentation de Ssortingng ne peut pas être modifiée mais il n’est pas nécessaire de perpétuer le problème.