tag:linuxfr.org,2005:/tags/complexit%C3%A9/publicLinuxFr.org : les contenus étiquetés avec « complexité »2023-01-24T15:30:26+01:00/favicon.pngtag:linuxfr.org,2005:Bookmark/58212023-01-24T09:34:31+01:002023-01-24T09:34:31+01:00rationalisme, nihilisme et postmodernisme ou comment gérer la complexité des systèmes d'information<a href="https://ioc.exchange/@invisv/109740474201888576">https://ioc.exchange/@invisv/109740474201888576</a> <p>
<strong>Commentaires :</strong>
<a href="//linuxfr.org/nodes/130102/comments.atom">voir le flux Atom</a>
<a href="https://linuxfr.org/users/krunch/liens/rationalisme-nihilisme-et-postmodernisme-ou-comment-gerer-la-complexite-des-systemes-d-information#comments">ouvrir dans le navigateur</a>
</p>
Krunchhttps://linuxfr.org/nodes/130102/comments.atomtag:linuxfr.org,2005:Diary/385042019-05-10T13:43:56+02:002019-05-10T13:43:56+02:00Magic: the Gathering, le problème de l'arrêt, et une inférence un peu rapideLicence CC By‑SA http://creativecommons.org/licenses/by-sa/4.0/deed.fr<p>Slate m'offre, dans <a href="http://www.slate.fr/story/177057/jeux-cartes-magic-the-gathering-plus-dur-monde-quotient-complexite-informatique">un article récent</a>, le moyen de concilier mes trois passions : l'informatique théorique, le jeu de société, et me moquer des journalistes.</p>
<p>Ça commence donc par <a href="https://arxiv.org/abs/1904.09828">un article plutôt banal sur arXiv</a> : les auteurs ont, à partir de deux decks très spécifiques (mais légaux selon les règles du jeu de société <a href="https://fr.wikipedia.org/wiki/Magic_:_L%27Assembl%C3%A9e">Magic</a>), réussi à créer une <a href="https://fr.wikipedia.org/wiki/machine%20de%20Turing" title="Définition Wikipédia">machine de Turing</a>. Machine de Turing un peu particulière puisqu'elle mène à la victoire du joueur A si et seulement si elle s'arrête. Ils appliquent donc à cette machine de Turing le <a href="https://fr.wikipedia.org/wiki/probl%C3%A8me%20de%20l'arr%C3%AAt" title="Définition Wikipédia">problème de l'arrêt</a> : comme l'arrêt de cette machine de Turing précise est indécidable, il existe au moins un cas de partie de Magic indécidable. Les auteurs en concluent que construire une intelligence artificielle sous forme d'arbre des possibles pour Magic est impossible, ce qui est une maigre avancée, mais une avancée quand même : jusqu'ici, on savait "juste" que c'était une très mauvaise idée. </p>
<p>Le point qui est intéressant et nouveau, c'est que Magic devient ainsi le premier jeu réel (et non seulement théorique) indécidable : que ce soit le go, les échecs, <a href="https://fr.wikipedia.org/wiki/Dominion_(jeu)">Dominion</a> ou whatever, on ne connaissait pas de jeu réellement pratiqué dont on ne puisse prédire s'il allait s'arrêter (autrement dit : tous les jeux de société autres que Magic finissent nécessairement par atteindre leur condition de fin de partie, du moins jusqu'à de plus amples recherches).</p>
<p>À partir de là, la machine (médiatique, pas de Turing) s'est un peu emballée. Kotaku, site spécialisé dans le jeu vidéo et la culture geek, publie <a href="http://kotaku.com/magic-the-gathering-is-so-complex-it-could-stump-a-com-1834623872">Magic the Gathering est si complexe qu'il pourrait planter un ordinateur</a>. Ce qui est formellement vrai, mais uniquement dans la configuration très particulière décrite par les auteurs. Point amusant : l'article original fait abstraction de la grosse majorité des cartes de Magic (et donc de sa complexité), puisqu'il n'en utilise même pas 200 sur les plus de 20000 publiées à ce jour. Slate va alors reprendre l'info et achever de ruiner la (déjà maigre) crédibilité de sa rubrique sciences avec l'article cité plus haut : <a href="http://www.slate.fr/story/177057/jeux-cartes-magic-the-gathering-plus-dur-monde-quotient-complexite-informatique">«Magic: The Gathering» est le jeu le plus dur au monde</a>. On y trouve quekques phrases magiques comme :</p>
<blockquote>
<p>Magic a le plus grand quotient de complexité informatique connu</p>
</blockquote>
<p>(J'aimerais bien savoir ce qu'est ce quotient, je n'en ai jamais entendu parler)</p>
<blockquote>
<p>L'ordinateur, pensé pour calculer les pièges, les stratégies à adopter et les probabilités de victoire, a été incapable de déterminer qui remporterait la partie.</p>
</blockquote>
<p>(Alors… C'est juste sans aucun lien avec l'article en question)</p>
<p>Bref, on part de "nous avons réussi à coder une machine de Turing avec une partie vraiment très spéciale de Magic: the Gathering" pour arriver à "Magic: the Gatherinc est si complexe qu'il pourrait planter un ordinateur" et enfin à "Magic: the Gathering est le jeu le plus dur au monde". <br>
Ça me rappelle une <a href="//linuxfr.org/news/blagues-d-informaticiens#comment-1460933">histoire déjà publiée</a> sur linuxfr :</p>
<blockquote>
<p>C'est un biologiste, un physicien et un mathématicien qui vont à un congrès à Glasgow, en Écosse. Le biologiste regarde par la fenêtre, voit un mouton noir, et s'étonne :<br>
-- Tiens, je ne savais pas qu'en Écosse, les moutons étaient noirs !<br>
Le physicien le reprend :<br>
-- Votre inférence est un peu rapide. Tout ce que vous pouvez dire, c'est qu'il y a des moutons noirs en Écosse.<br>
Le mathématicien le reprend à son tour :<br>
-- Votre inférence est un peu rapide. Tout ce que vous pouvez dire, c'est qu'il existe en Écosse au moins un champ contenant au moins un mouton, dont au moins un côté est noir !</p>
</blockquote>
<div><a href="https://linuxfr.org/users/liorel/journaux/magic-the-gathering-le-probleme-de-l-arret-et-une-inference-un-peu-rapide.epub">Télécharger ce contenu au format EPUB</a></div> <p>
<strong>Commentaires :</strong>
<a href="//linuxfr.org/nodes/117177/comments.atom">voir le flux Atom</a>
<a href="https://linuxfr.org/users/liorel/journaux/magic-the-gathering-le-probleme-de-l-arret-et-une-inference-un-peu-rapide#comments">ouvrir dans le navigateur</a>
</p>
Liorelhttps://linuxfr.org/nodes/117177/comments.atomtag:linuxfr.org,2005:Diary/349442014-05-04T09:54:41+02:002014-05-05T13:28:40+02:00OpenJDK JEP 180: HashMap, collisions & attaques par la complexitéLicence CC By‑SA http://creativecommons.org/licenses/by-sa/4.0/deed.fr<h2 class="sommaire">Sommaire</h2>
<ul class="toc">
<li><ul>
<li><a href="#pr%C3%A9sentation-des-tables-de-hachage">Présentation des tables de hachage</a></li>
<li><a href="#attaques-par-la-complexit%C3%A9">Attaques par la complexité</a></li>
<li><a href="#java-7u6--alternative-string-hashing">Java 7u6 & "alternative string-hashing"</a></li>
<li><a href="#attaques-par-la-complexit%C3%A9-bis">Attaques par la complexité (bis)</a></li>
<li><a href="#jep-180-une-solution-int%C3%A9ressante">JEP 180: Une solution intéressante</a></li>
<li><a href="#conclusion">Conclusion</a></li>
</ul></li>
</ul><p>Dans ce journal, je vais parler de la <a href="http://openjdk.java.net/jeps/180">JEP 180</a> d'OpenJDK 8 qui propose une solution intéressante aux problèmes d'attaques sur la complexité que rencontrent les tables de hachage.</p>
<p>On a déjà parlé de ce sujet <a href="//linuxfr.org/users/alenvers/journaux/des-tables-de-hachage-en-milieu-hostile">ici même</a> à <a href="//linuxfr.org/news/le-colonel-moutarde-sur-la-table-de-hachage-avec-un-livre-de-maths">plusieurs reprises</a>. Je vais cependant rapidement représenter le problème et l'évolution des discutions. Le lecteur averti sur le sujet ira directement au dernier paragraphe pour voir la proposition de la JEP 180.</p>
<h3 id="présentation-des-tables-de-hachage">Présentation des tables de hachage</h3>
<p>Une table de hachage est une implémentation du type abstrait tableau associatif. Un <a href="http://fr.wikipedia.org/wiki/Tableau_associatif">tableau associatif</a> permet d'associer une clé à une ou plusieurs valeurs, on le nomme aussi parfois dictionnaire. Il fait partie des types abstraits les plus utilisé avec les listes.</p>
<p>Une table de hachage est une implémentation particulière d'un tableau associatif. Elle est aussi la plus courante. Basiquement il s'agit d'un tableau dont les cases contiennent un pointeur vers nil, un élément ou une liste d'élément. On détermine la case à utiliser en appliquant une fonction de hachage à la clé. Idéalement, chaque case ne pointera que vers un unique élément. Dans ce cas les opérations d'insertion, de consultation et de suppression se font en temps constant, noté <img style="display: inline; max-height: 1em;" class="mathjax" src="data:image/svg+xml;base64,PHN2ZyB4bWxuczp4bGluaz0iaHR0cDovL3d3dy53My5vcmcvMTk5OS94bGlu%0AayIgc3R5bGU9IndpZHRoOiA0LjQyOWV4OyBoZWlnaHQ6IDIuMTQzZXg7IHZl%0AcnRpY2FsLWFsaWduOiAtMC41NzFleDsgbWFyZ2luLXRvcDogMXB4OyBtYXJn%0AaW4tcmlnaHQ6IDBweDsgbWFyZ2luLWJvdHRvbTogMXB4OyBtYXJnaW4tbGVm%0AdDogMHB4OyBwb3NpdGlvbjogc3RhdGljOyAiIHZpZXdCb3g9IjAgLTcwMi4y%0ANTgxMjMyNTUxNTQ5IDE5MDggOTA1LjUxNjI0NjUxMDMxIiB4bWxucz0iaHR0%0AcDovL3d3dy53My5vcmcvMjAwMC9zdmciPjxkZWZzIGlkPSJNYXRoSmF4X1NW%0AR19nbHlwaHMiPjxwYXRoIGlkPSJTVElYV0VCTUFJTkktNEYiIHN0cm9rZS13%0AaWR0aD0iMTAiIGQ9Ik02OTkgNDE4YzAgLTE0NiAtODggLTI4NSAtMjA3IC0z%0ANjVjLTY1IC00NCAtMTQwIC03MSAtMjE0IC03MWMtMTMwIDAgLTIxOCA4NSAt%0AMjE4IDIzNGMwIDEyMiA3MyAyNjIgMTc3IDM1M2M2OSA2MCAxNTIgOTcgMjM3%0AIDk3YzE0NCAxIDIyNSAtOTYgMjI1IC0yNDh6TTU5NCA0ODFjMCA5NCAtNDkg%0AMTUyIC0xMjkgMTUyYy03NCAwIC0xMzcgLTUxIC0xODYgLTExN2MtNzMgLTk5%0AIC0xMTQgLTIzMiAtMTE0IC0zMzIgYzAgLTEwOSA0NiAtMTY5IDEzMCAtMTY5%0AYzY3IDAgMTI0IDM5IDE3MCA5NWM4NCAxMDQgMTI5IDI2OSAxMjkgMzcxWiI+%0APC9wYXRoPjxwYXRoIGlkPSJTVElYV0VCTUFJTi0yOCIgc3Ryb2tlLXdpZHRo%0APSIxMCIgZD0iTTMwNCAtMTYxbC0xMiAtMTZjLTE1OCA5MCAtMjQ0IDI1OSAt%0AMjQ0IDQyOWMwIDE4NSA4NyAzMjkgMjQ3IDQyNGw5IC0xNmMtMTM5IC0xMTkg%0ALTE3MCAtMjEyIC0xNzAgLTQwNWMwIC0xODYgMzAgLTI5OSAxNzAgLTQxNloi%0APjwvcGF0aD48cGF0aCBpZD0iU1RJWFdFQk1BSU4tMzEiIHN0cm9rZS13aWR0%0AaD0iMTAiIGQ9Ik0zOTQgMGgtMjc2djE1Yzc0IDQgOTUgMjUgOTUgODB2NDQ5%0AYzAgMzQgLTkgNDkgLTMwIDQ5Yy0xMCAwIC0yNyAtNSAtNDUgLTEybC0yNyAt%0AMTB2MTRsMTc5IDkxbDkgLTN2LTU5N2MwIC00MyAyMCAtNjEgOTUgLTYxdi0x%0ANVoiPjwvcGF0aD48cGF0aCBpZD0iU1RJWFdFQk1BSU4tMjkiIHN0cm9rZS13%0AaWR0aD0iMTAiIGQ9Ik0yOSA2NjBsMTIgMTZjMTUzIC05MiAyNDQgLTI1OSAy%0ANDQgLTQyOWMwIC0xODUgLTg4IC0zMjcgLTI0NyAtNDI0bC05IDE2YzE0MiAx%0AMTcgMTcwIDIxMSAxNzAgNDA1YzAgMTg3IC0yNSAzMDIgLTE3MCA0MTZaIj48%0AL3BhdGg+PC9kZWZzPjxnIHN0cm9rZT0iYmxhY2siIGZpbGw9ImJsYWNrIiBz%0AdHJva2Utd2lkdGg9IjAiIHRyYW5zZm9ybT0ibWF0cml4KDEgMCAwIC0xIDAg%0AMCkiPjx1c2UgaHJlZj0iI1NUSVhXRUJNQUlOSS00RiIgeGxpbms6aHJlZj0i%0AI1NUSVhXRUJNQUlOSS00RiI+PC91c2U+PHVzZSBocmVmPSIjU1RJWFdFQk1B%0ASU4tMjgiIHg9IjcyNyIgeT0iMCIgeGxpbms6aHJlZj0iI1NUSVhXRUJNQUlO%0ALTI4Ij48L3VzZT48dXNlIGhyZWY9IiNTVElYV0VCTUFJTi0zMSIgeD0iMTA2%0ANSIgeT0iMCIgeGxpbms6aHJlZj0iI1NUSVhXRUJNQUlOLTMxIj48L3VzZT48%0AdXNlIGhyZWY9IiNTVElYV0VCTUFJTi0yOSIgeD0iMTU3MCIgeT0iMCIgeGxp%0Abms6aHJlZj0iI1NUSVhXRUJNQUlOLTI5Ij48L3VzZT48L2c+PC9zdmc+%0A" alt="O(1)">, c'est à dire qui ne dépend pas du nombre d'élément présent dans la table de hachage. Cependant si la fonction de hachage retourne deux fois la même valeur pour deux clés différentes, ce que l'on nomme collision, alors les deux valeurs sont généralement stockées comme une liste. C'est à dire que maintenant il va falloir parcourir toute cette liste. Dans le pire cas, la fonction de hachage retourne toujours la même valeur, toutes les valeurs vont donc être stockées dans la même case et l'on va devoir parcourir la liste pour chaque opération. La complexité est alors linéaire par rapport au nombre d'éléments dans la structure, noté <img style="display: inline; max-height: 1em;" class="mathjax" src="data:image/svg+xml;base64,PHN2ZyB4bWxuczp4bGluaz0iaHR0cDovL3d3dy53My5vcmcvMTk5OS94bGlu%0AayIgc3R5bGU9IndpZHRoOiA0LjQyOWV4OyBoZWlnaHQ6IDIuMTQzZXg7IHZl%0AcnRpY2FsLWFsaWduOiAtMC41NzFleDsgbWFyZ2luLXRvcDogMXB4OyBtYXJn%0AaW4tcmlnaHQ6IDBweDsgbWFyZ2luLWJvdHRvbTogMXB4OyBtYXJnaW4tbGVm%0AdDogMHB4OyBwb3NpdGlvbjogc3RhdGljOyAiIHZpZXdCb3g9IjAgLTcwMi4y%0ANTgxMjMyNTUxNTQ5IDE5MDggOTA1LjUxNjI0NjUxMDMxIiB4bWxucz0iaHR0%0AcDovL3d3dy53My5vcmcvMjAwMC9zdmciPjxkZWZzIGlkPSJNYXRoSmF4X1NW%0AR19nbHlwaHMiPjxwYXRoIGlkPSJTVElYV0VCTUFJTkktNEYiIHN0cm9rZS13%0AaWR0aD0iMTAiIGQ9Ik02OTkgNDE4YzAgLTE0NiAtODggLTI4NSAtMjA3IC0z%0ANjVjLTY1IC00NCAtMTQwIC03MSAtMjE0IC03MWMtMTMwIDAgLTIxOCA4NSAt%0AMjE4IDIzNGMwIDEyMiA3MyAyNjIgMTc3IDM1M2M2OSA2MCAxNTIgOTcgMjM3%0AIDk3YzE0NCAxIDIyNSAtOTYgMjI1IC0yNDh6TTU5NCA0ODFjMCA5NCAtNDkg%0AMTUyIC0xMjkgMTUyYy03NCAwIC0xMzcgLTUxIC0xODYgLTExN2MtNzMgLTk5%0AIC0xMTQgLTIzMiAtMTE0IC0zMzIgYzAgLTEwOSA0NiAtMTY5IDEzMCAtMTY5%0AYzY3IDAgMTI0IDM5IDE3MCA5NWM4NCAxMDQgMTI5IDI2OSAxMjkgMzcxWiI+%0APC9wYXRoPjxwYXRoIGlkPSJTVElYV0VCTUFJTi0yOCIgc3Ryb2tlLXdpZHRo%0APSIxMCIgZD0iTTMwNCAtMTYxbC0xMiAtMTZjLTE1OCA5MCAtMjQ0IDI1OSAt%0AMjQ0IDQyOWMwIDE4NSA4NyAzMjkgMjQ3IDQyNGw5IC0xNmMtMTM5IC0xMTkg%0ALTE3MCAtMjEyIC0xNzAgLTQwNWMwIC0xODYgMzAgLTI5OSAxNzAgLTQxNloi%0APjwvcGF0aD48cGF0aCBpZD0iU1RJWFdFQk1BSU5JLTZFIiBzdHJva2Utd2lk%0AdGg9IjEwIiBkPSJNNDYwIDExN2wxNCAtMTNjLTY4IC05MyAtOTMgLTExMyAt%0AMTQwIC0xMTNjLTI1IDAgLTQ3IDE2IC00NyA1NGMwIDEwIDIgMjMgMTYgNzVs%0ANDQgMTYyYzggMzEgMTQgNjcgMTQgNzljMCAxOCAtOSAyOSAtMjQgMjljLTQw%0AIDAgLTg1IC00OSAtMTQ4IC0xNDJjLTQ1IC02NyAtNTMgLTkwIC0xMDAgLTI0%0AOGgtNzVsOTYgMzUwYzEgNSAyIDExIDIgMTdjMCAyMCAtMTQgMjYgLTY1IDI3%0AdjE2YzgxIDE2IDEwOSAyMCAxNjIgMzFsNCAtMmwtNjcgLTIxOCBjMTAwIDE2%0AMCAxNjcgMjIwIDIzMSAyMjBjNDMgMCA2NSAtMjUgNjUgLTYxYzAgLTE4IC00%0AIC0zOSAtMTAgLTYwbC01NiAtMjAzYy0xMCAtMzYgLTE0IC01MyAtMTQgLTYx%0AYzAgLTkgNCAtMTggMTYgLTE4YzE0IDAgMzIgMTYgNjEgNTNjNyA4IDE0IDE3%0AIDIxIDI2WiI+PC9wYXRoPjxwYXRoIGlkPSJTVElYV0VCTUFJTi0yOSIgc3Ry%0Ab2tlLXdpZHRoPSIxMCIgZD0iTTI5IDY2MGwxMiAxNmMxNTMgLTkyIDI0NCAt%0AMjU5IDI0NCAtNDI5YzAgLTE4NSAtODggLTMyNyAtMjQ3IC00MjRsLTkgMTZj%0AMTQyIDExNyAxNzAgMjExIDE3MCA0MDVjMCAxODcgLTI1IDMwMiAtMTcwIDQx%0ANloiPjwvcGF0aD48L2RlZnM+PGcgc3Ryb2tlPSJibGFjayIgZmlsbD0iYmxh%0AY2siIHN0cm9rZS13aWR0aD0iMCIgdHJhbnNmb3JtPSJtYXRyaXgoMSAwIDAg%0ALTEgMCAwKSI+PHVzZSBocmVmPSIjU1RJWFdFQk1BSU5JLTRGIiB4bGluazpo%0AcmVmPSIjU1RJWFdFQk1BSU5JLTRGIj48L3VzZT48dXNlIGhyZWY9IiNTVElY%0AV0VCTUFJTi0yOCIgeD0iNzI3IiB5PSIwIiB4bGluazpocmVmPSIjU1RJWFdF%0AQk1BSU4tMjgiPjwvdXNlPjx1c2UgaHJlZj0iI1NUSVhXRUJNQUlOSS02RSIg%0AeD0iMTA2NSIgeT0iMCIgeGxpbms6aHJlZj0iI1NUSVhXRUJNQUlOSS02RSI+%0APC91c2U+PHVzZSBocmVmPSIjU1RJWFdFQk1BSU4tMjkiIHg9IjE1NzAiIHk9%0AIjAiIHhsaW5rOmhyZWY9IiNTVElYV0VCTUFJTi0yOSI+PC91c2U+PC9nPjwv%0Ac3ZnPg==%0A" alt="O(n)">, ce qui est très peu performant. Une table de hachage a donc une complexité moyenne d'<img style="display: inline; max-height: 1em;" class="mathjax" src="data:image/svg+xml;base64,PHN2ZyB4bWxuczp4bGluaz0iaHR0cDovL3d3dy53My5vcmcvMTk5OS94bGlu%0AayIgc3R5bGU9IndpZHRoOiA0LjQyOWV4OyBoZWlnaHQ6IDIuMTQzZXg7IHZl%0AcnRpY2FsLWFsaWduOiAtMC41NzFleDsgbWFyZ2luLXRvcDogMXB4OyBtYXJn%0AaW4tcmlnaHQ6IDBweDsgbWFyZ2luLWJvdHRvbTogMXB4OyBtYXJnaW4tbGVm%0AdDogMHB4OyBwb3NpdGlvbjogc3RhdGljOyAiIHZpZXdCb3g9IjAgLTcwMi4y%0ANTgxMjMyNTUxNTQ5IDE5MDggOTA1LjUxNjI0NjUxMDMxIiB4bWxucz0iaHR0%0AcDovL3d3dy53My5vcmcvMjAwMC9zdmciPjxkZWZzIGlkPSJNYXRoSmF4X1NW%0AR19nbHlwaHMiPjxwYXRoIGlkPSJTVElYV0VCTUFJTkktNEYiIHN0cm9rZS13%0AaWR0aD0iMTAiIGQ9Ik02OTkgNDE4YzAgLTE0NiAtODggLTI4NSAtMjA3IC0z%0ANjVjLTY1IC00NCAtMTQwIC03MSAtMjE0IC03MWMtMTMwIDAgLTIxOCA4NSAt%0AMjE4IDIzNGMwIDEyMiA3MyAyNjIgMTc3IDM1M2M2OSA2MCAxNTIgOTcgMjM3%0AIDk3YzE0NCAxIDIyNSAtOTYgMjI1IC0yNDh6TTU5NCA0ODFjMCA5NCAtNDkg%0AMTUyIC0xMjkgMTUyYy03NCAwIC0xMzcgLTUxIC0xODYgLTExN2MtNzMgLTk5%0AIC0xMTQgLTIzMiAtMTE0IC0zMzIgYzAgLTEwOSA0NiAtMTY5IDEzMCAtMTY5%0AYzY3IDAgMTI0IDM5IDE3MCA5NWM4NCAxMDQgMTI5IDI2OSAxMjkgMzcxWiI+%0APC9wYXRoPjxwYXRoIGlkPSJTVElYV0VCTUFJTi0yOCIgc3Ryb2tlLXdpZHRo%0APSIxMCIgZD0iTTMwNCAtMTYxbC0xMiAtMTZjLTE1OCA5MCAtMjQ0IDI1OSAt%0AMjQ0IDQyOWMwIDE4NSA4NyAzMjkgMjQ3IDQyNGw5IC0xNmMtMTM5IC0xMTkg%0ALTE3MCAtMjEyIC0xNzAgLTQwNWMwIC0xODYgMzAgLTI5OSAxNzAgLTQxNloi%0APjwvcGF0aD48cGF0aCBpZD0iU1RJWFdFQk1BSU4tMzEiIHN0cm9rZS13aWR0%0AaD0iMTAiIGQ9Ik0zOTQgMGgtMjc2djE1Yzc0IDQgOTUgMjUgOTUgODB2NDQ5%0AYzAgMzQgLTkgNDkgLTMwIDQ5Yy0xMCAwIC0yNyAtNSAtNDUgLTEybC0yNyAt%0AMTB2MTRsMTc5IDkxbDkgLTN2LTU5N2MwIC00MyAyMCAtNjEgOTUgLTYxdi0x%0ANVoiPjwvcGF0aD48cGF0aCBpZD0iU1RJWFdFQk1BSU4tMjkiIHN0cm9rZS13%0AaWR0aD0iMTAiIGQ9Ik0yOSA2NjBsMTIgMTZjMTUzIC05MiAyNDQgLTI1OSAy%0ANDQgLTQyOWMwIC0xODUgLTg4IC0zMjcgLTI0NyAtNDI0bC05IDE2YzE0MiAx%0AMTcgMTcwIDIxMSAxNzAgNDA1YzAgMTg3IC0yNSAzMDIgLTE3MCA0MTZaIj48%0AL3BhdGg+PC9kZWZzPjxnIHN0cm9rZT0iYmxhY2siIGZpbGw9ImJsYWNrIiBz%0AdHJva2Utd2lkdGg9IjAiIHRyYW5zZm9ybT0ibWF0cml4KDEgMCAwIC0xIDAg%0AMCkiPjx1c2UgaHJlZj0iI1NUSVhXRUJNQUlOSS00RiIgeGxpbms6aHJlZj0i%0AI1NUSVhXRUJNQUlOSS00RiI+PC91c2U+PHVzZSBocmVmPSIjU1RJWFdFQk1B%0ASU4tMjgiIHg9IjcyNyIgeT0iMCIgeGxpbms6aHJlZj0iI1NUSVhXRUJNQUlO%0ALTI4Ij48L3VzZT48dXNlIGhyZWY9IiNTVElYV0VCTUFJTi0zMSIgeD0iMTA2%0ANSIgeT0iMCIgeGxpbms6aHJlZj0iI1NUSVhXRUJNQUlOLTMxIj48L3VzZT48%0AdXNlIGhyZWY9IiNTVElYV0VCTUFJTi0yOSIgeD0iMTU3MCIgeT0iMCIgeGxp%0Abms6aHJlZj0iI1NUSVhXRUJNQUlOLTI5Ij48L3VzZT48L2c+PC9zdmc+%0A" alt="O(1)"> mais un pire cas en <img style="display: inline; max-height: 1em;" class="mathjax" src="data:image/svg+xml;base64,PHN2ZyB4bWxuczp4bGluaz0iaHR0cDovL3d3dy53My5vcmcvMTk5OS94bGlu%0AayIgc3R5bGU9IndpZHRoOiA0LjQyOWV4OyBoZWlnaHQ6IDIuMTQzZXg7IHZl%0AcnRpY2FsLWFsaWduOiAtMC41NzFleDsgbWFyZ2luLXRvcDogMXB4OyBtYXJn%0AaW4tcmlnaHQ6IDBweDsgbWFyZ2luLWJvdHRvbTogMXB4OyBtYXJnaW4tbGVm%0AdDogMHB4OyBwb3NpdGlvbjogc3RhdGljOyAiIHZpZXdCb3g9IjAgLTcwMi4y%0ANTgxMjMyNTUxNTQ5IDE5MDggOTA1LjUxNjI0NjUxMDMxIiB4bWxucz0iaHR0%0AcDovL3d3dy53My5vcmcvMjAwMC9zdmciPjxkZWZzIGlkPSJNYXRoSmF4X1NW%0AR19nbHlwaHMiPjxwYXRoIGlkPSJTVElYV0VCTUFJTkktNEYiIHN0cm9rZS13%0AaWR0aD0iMTAiIGQ9Ik02OTkgNDE4YzAgLTE0NiAtODggLTI4NSAtMjA3IC0z%0ANjVjLTY1IC00NCAtMTQwIC03MSAtMjE0IC03MWMtMTMwIDAgLTIxOCA4NSAt%0AMjE4IDIzNGMwIDEyMiA3MyAyNjIgMTc3IDM1M2M2OSA2MCAxNTIgOTcgMjM3%0AIDk3YzE0NCAxIDIyNSAtOTYgMjI1IC0yNDh6TTU5NCA0ODFjMCA5NCAtNDkg%0AMTUyIC0xMjkgMTUyYy03NCAwIC0xMzcgLTUxIC0xODYgLTExN2MtNzMgLTk5%0AIC0xMTQgLTIzMiAtMTE0IC0zMzIgYzAgLTEwOSA0NiAtMTY5IDEzMCAtMTY5%0AYzY3IDAgMTI0IDM5IDE3MCA5NWM4NCAxMDQgMTI5IDI2OSAxMjkgMzcxWiI+%0APC9wYXRoPjxwYXRoIGlkPSJTVElYV0VCTUFJTi0yOCIgc3Ryb2tlLXdpZHRo%0APSIxMCIgZD0iTTMwNCAtMTYxbC0xMiAtMTZjLTE1OCA5MCAtMjQ0IDI1OSAt%0AMjQ0IDQyOWMwIDE4NSA4NyAzMjkgMjQ3IDQyNGw5IC0xNmMtMTM5IC0xMTkg%0ALTE3MCAtMjEyIC0xNzAgLTQwNWMwIC0xODYgMzAgLTI5OSAxNzAgLTQxNloi%0APjwvcGF0aD48cGF0aCBpZD0iU1RJWFdFQk1BSU5JLTZFIiBzdHJva2Utd2lk%0AdGg9IjEwIiBkPSJNNDYwIDExN2wxNCAtMTNjLTY4IC05MyAtOTMgLTExMyAt%0AMTQwIC0xMTNjLTI1IDAgLTQ3IDE2IC00NyA1NGMwIDEwIDIgMjMgMTYgNzVs%0ANDQgMTYyYzggMzEgMTQgNjcgMTQgNzljMCAxOCAtOSAyOSAtMjQgMjljLTQw%0AIDAgLTg1IC00OSAtMTQ4IC0xNDJjLTQ1IC02NyAtNTMgLTkwIC0xMDAgLTI0%0AOGgtNzVsOTYgMzUwYzEgNSAyIDExIDIgMTdjMCAyMCAtMTQgMjYgLTY1IDI3%0AdjE2YzgxIDE2IDEwOSAyMCAxNjIgMzFsNCAtMmwtNjcgLTIxOCBjMTAwIDE2%0AMCAxNjcgMjIwIDIzMSAyMjBjNDMgMCA2NSAtMjUgNjUgLTYxYzAgLTE4IC00%0AIC0zOSAtMTAgLTYwbC01NiAtMjAzYy0xMCAtMzYgLTE0IC01MyAtMTQgLTYx%0AYzAgLTkgNCAtMTggMTYgLTE4YzE0IDAgMzIgMTYgNjEgNTNjNyA4IDE0IDE3%0AIDIxIDI2WiI+PC9wYXRoPjxwYXRoIGlkPSJTVElYV0VCTUFJTi0yOSIgc3Ry%0Ab2tlLXdpZHRoPSIxMCIgZD0iTTI5IDY2MGwxMiAxNmMxNTMgLTkyIDI0NCAt%0AMjU5IDI0NCAtNDI5YzAgLTE4NSAtODggLTMyNyAtMjQ3IC00MjRsLTkgMTZj%0AMTQyIDExNyAxNzAgMjExIDE3MCA0MDVjMCAxODcgLTI1IDMwMiAtMTcwIDQx%0ANloiPjwvcGF0aD48L2RlZnM+PGcgc3Ryb2tlPSJibGFjayIgZmlsbD0iYmxh%0AY2siIHN0cm9rZS13aWR0aD0iMCIgdHJhbnNmb3JtPSJtYXRyaXgoMSAwIDAg%0ALTEgMCAwKSI+PHVzZSBocmVmPSIjU1RJWFdFQk1BSU5JLTRGIiB4bGluazpo%0AcmVmPSIjU1RJWFdFQk1BSU5JLTRGIj48L3VzZT48dXNlIGhyZWY9IiNTVElY%0AV0VCTUFJTi0yOCIgeD0iNzI3IiB5PSIwIiB4bGluazpocmVmPSIjU1RJWFdF%0AQk1BSU4tMjgiPjwvdXNlPjx1c2UgaHJlZj0iI1NUSVhXRUJNQUlOSS02RSIg%0AeD0iMTA2NSIgeT0iMCIgeGxpbms6aHJlZj0iI1NUSVhXRUJNQUlOSS02RSI+%0APC91c2U+PHVzZSBocmVmPSIjU1RJWFdFQk1BSU4tMjkiIHg9IjE1NzAiIHk9%0AIjAiIHhsaW5rOmhyZWY9IiNTVElYV0VCTUFJTi0yOSI+PC91c2U+PC9nPjwv%0Ac3ZnPg==%0A" alt="O(n)">. Il est donc crucial d'avoir une fonction de hachage performante. Les personnes n'étant pas à l'aise avec l'implémentation d'une table de hachage ou les concepts précédant auront tout intérêt à consulter la page <a href="http://fr.wikipedia.org/wiki/Table_de_hachage">Wikipédia</a> qui est assez complète.</p>
<p>Cet article s'accompagne d'un benchmark écrit avec <a href="http://openjdk.java.net/projects/code-tools/jmh/">JMH</a> qui va nous permettre d'observer comment se comporte la classe <a href="http://docs.oracle.com/javase/7/docs/api/java/util/HashMap.html">HashMap</a> de Java dans différentes circonstances. Le code de ce benchmark est extrêmement simple:</p>
<pre><code class="java"> <span class="nd">@GenerateMicroBenchmark</span>
<span class="kd">public</span> <span class="kt">int</span> <span class="nf">put</span><span class="o">()</span> <span class="o">{</span>
<span class="n">HashMap</span><span class="o"><</span><span class="n">String</span><span class="o">,</span> <span class="n">Object</span><span class="o">></span> <span class="n">map</span> <span class="o">=</span> <span class="k">new</span> <span class="n">HashMap</span><span class="o"><</span><span class="n">String</span><span class="o">,</span> <span class="n">Object</span><span class="o">>();</span>
<span class="k">for</span> <span class="o">(</span><span class="n">String</span> <span class="nl">s:</span> <span class="n">strings</span><span class="o">)</span> <span class="o">{</span>
<span class="n">map</span><span class="o">.</span><span class="na">put</span><span class="o">(</span><span class="n">s</span><span class="o">,</span> <span class="n">s</span><span class="o">);</span>
<span class="o">}</span>
<span class="k">return</span> <span class="n">map</span><span class="o">.</span><span class="na">size</span><span class="o">();</span>
<span class="o">}</span></code></pre>
<p>Nous insérons une collection de chaîne de caractère dans une HashMap et nous mesurons le temps moyen de cette opération. Mesurer l'insertion est une métrique correcte pour ce que nous souhaitons mesurer car lors d'une insertion, dans le cas où la clé existe déjà il faut remplacer la valeur existante. Il faut donc rechercher parmi toutes les clés déjà existantes dans cette case. Les comportements en consultation et en suppressions seront similaires à celui que nous observons. Dans tous les cas, en cas de collision, il faudra traverser toutes les valeurs de cette case. Exemple du code de la méthode <em>put()</em>:</p>
<pre><code class="java"> <span class="kd">public</span> <span class="n">V</span> <span class="nf">put</span><span class="o">(</span><span class="n">K</span> <span class="n">key</span><span class="o">,</span> <span class="n">V</span> <span class="n">value</span><span class="o">)</span> <span class="o">{</span>
<span class="k">if</span> <span class="o">(</span><span class="n">key</span> <span class="o">==</span> <span class="kc">null</span><span class="o">)</span>
<span class="k">return</span> <span class="nf">putForNullKey</span><span class="o">(</span><span class="n">value</span><span class="o">);</span>
<span class="kt">int</span> <span class="n">hash</span> <span class="o">=</span> <span class="n">hash</span><span class="o">(</span><span class="n">key</span><span class="o">.</span><span class="na">hashCode</span><span class="o">());</span>
<span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="n">indexFor</span><span class="o">(</span><span class="n">hash</span><span class="o">,</span> <span class="n">table</span><span class="o">.</span><span class="na">length</span><span class="o">);</span>
<span class="k">for</span> <span class="o">(</span><span class="n">Entry</span><span class="o"><</span><span class="n">K</span><span class="o">,</span><span class="n">V</span><span class="o">></span> <span class="n">e</span> <span class="o">=</span> <span class="n">table</span><span class="o">[</span><span class="n">i</span><span class="o">];</span> <span class="n">e</span> <span class="o">!=</span> <span class="kc">null</span><span class="o">;</span> <span class="n">e</span> <span class="o">=</span> <span class="n">e</span><span class="o">.</span><span class="na">next</span><span class="o">)</span> <span class="o">{</span>
<span class="n">Object</span> <span class="n">k</span><span class="o">;</span>
<span class="k">if</span> <span class="o">(</span><span class="n">e</span><span class="o">.</span><span class="na">hash</span> <span class="o">==</span> <span class="n">hash</span> <span class="o">&&</span> <span class="o">((</span><span class="n">k</span> <span class="o">=</span> <span class="n">e</span><span class="o">.</span><span class="na">key</span><span class="o">)</span> <span class="o">==</span> <span class="n">key</span> <span class="o">||</span> <span class="n">key</span><span class="o">.</span><span class="na">equals</span><span class="o">(</span><span class="n">k</span><span class="o">)))</span> <span class="o">{</span>
<span class="n">V</span> <span class="n">oldValue</span> <span class="o">=</span> <span class="n">e</span><span class="o">.</span><span class="na">value</span><span class="o">;</span>
<span class="n">e</span><span class="o">.</span><span class="na">value</span> <span class="o">=</span> <span class="n">value</span><span class="o">;</span>
<span class="n">e</span><span class="o">.</span><span class="na">recordAccess</span><span class="o">(</span><span class="k">this</span><span class="o">);</span>
<span class="k">return</span> <span class="n">oldValue</span><span class="o">;</span>
<span class="o">}</span>
<span class="o">}</span>
<span class="n">modCount</span><span class="o">++;</span>
<span class="n">addEntry</span><span class="o">(</span><span class="n">hash</span><span class="o">,</span> <span class="n">key</span><span class="o">,</span> <span class="n">value</span><span class="o">,</span> <span class="n">i</span><span class="o">);</span>
<span class="k">return</span> <span class="kc">null</span><span class="o">;</span>
<span class="o">}</span></code></pre>
<p>On peut clairement y voir les étapes suivantes:</p>
<ul>
<li>On calcule le <code>hash</code> de la clé, qui va déterminer la case <code>i</code>
</li>
<li>On itère sur toutes les clés présente dans la case <code>i</code> pour regarder si une correspond à <code>key</code>
<ul>
<li>Si oui, alors on remplace la valeur existante par <code>value</code>
</li>
<li>Sinon, on ajoute un nouvel élément pour cette clé à la fin de la liste</li>
</ul>
</li>
</ul><p>Comme on le voit avec la ligne suivante <code>int hash = hash(key.hashCode());</code>, en java la case est calculée à partir de la valeur retourné par <code>hashCode()</code>. On applique en plus la fonction <code>hash()</code> afin d'améliorer un peu la distribution des clés. En effet, <code>i</code> est calculé modulo la taille de la table qui est une puissance de deux, et il est facile d'avoir des effets néfastes:</p>
<pre><code class="java"> <span class="cm">/**</span>
<span class="cm"> * Applies a supplemental hash function to a given hashCode, which</span>
<span class="cm"> * defends against poor quality hash functions. This is critical</span>
<span class="cm"> * because HashMap uses power-of-two length hash tables, that</span>
<span class="cm"> * otherwise encounter collisions for hashCodes that do not differ</span>
<span class="cm"> * in lower bits. Note: Null keys always map to hash 0, thus index 0.</span>
<span class="cm"> */</span>
<span class="kd">static</span> <span class="kt">int</span> <span class="nf">hash</span><span class="o">(</span><span class="kt">int</span> <span class="n">h</span><span class="o">)</span> <span class="o">{</span>
<span class="c1">// This function ensures that hashCodes that differ only by</span>
<span class="c1">// constant multiples at each bit position have a bounded</span>
<span class="c1">// number of collisions (approximately 8 at default load factor).</span>
<span class="n">h</span> <span class="o">^=</span> <span class="o">(</span><span class="n">h</span> <span class="o">>>></span> <span class="mi">20</span><span class="o">)</span> <span class="o">^</span> <span class="o">(</span><span class="n">h</span> <span class="o">>>></span> <span class="mi">12</span><span class="o">);</span>
<span class="k">return</span> <span class="n">h</span> <span class="o">^</span> <span class="o">(</span><span class="n">h</span> <span class="o">>>></span> <span class="mi">7</span><span class="o">)</span> <span class="o">^</span> <span class="o">(</span><span class="n">h</span> <span class="o">>>></span> <span class="mi">4</span><span class="o">);</span>
<span class="o">}</span></code></pre>
<p>Enfin le cas qui va nous intéresser particulièrement ici est celui des chaines de caractères comme clé car c'est une utilisation extrêmement courante et exposée aux attaques. Souvent les données fournis par l'utilisateur sont des chaînes de caractères plutôt que des objets complexes. Par exemple les en-tête HTTP sont souvent stocké dans un tableau associatif.</p>
<p>Regardons donc comment est implémenté le <code>hashCode</code> de la classe <code>String</code>:</p>
<pre><code class="java"> <span class="cm">/**</span>
<span class="cm"> * Returns a hash code for this string. The hash code for a</span>
<span class="cm"> * <code>String</code> object is computed as</span>
<span class="cm"> * <blockquote><pre></span>
<span class="cm"> * s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]</span>
<span class="cm"> * </pre></blockquote></span>
<span class="cm"> * using <code>int</code> arithmetic, where <code>s[i]</code> is the</span>
<span class="cm"> * <i>i</i>th character of the string, <code>n</code> is the length of</span>
<span class="cm"> * the string, and <code>^</code> indicates exponentiation.</span>
<span class="cm"> * (The hash value of the empty string is zero.)</span>
<span class="cm"> *</span>
<span class="cm"> * @return a hash code value for this object.</span>
<span class="cm"> */</span>
<span class="kd">public</span> <span class="kt">int</span> <span class="nf">hashCode</span><span class="o">()</span> <span class="o">{</span>
<span class="kt">int</span> <span class="n">h</span> <span class="o">=</span> <span class="n">hash</span><span class="o">;</span>
<span class="kt">int</span> <span class="n">len</span> <span class="o">=</span> <span class="n">count</span><span class="o">;</span>
<span class="k">if</span> <span class="o">(</span><span class="n">h</span> <span class="o">==</span> <span class="mi">0</span> <span class="o">&&</span> <span class="n">len</span> <span class="o">></span> <span class="mi">0</span><span class="o">)</span> <span class="o">{</span>
<span class="kt">int</span> <span class="n">off</span> <span class="o">=</span> <span class="n">offset</span><span class="o">;</span>
<span class="kt">char</span> <span class="n">val</span><span class="o">[]</span> <span class="o">=</span> <span class="n">value</span><span class="o">;</span>
<span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span> <span class="n">i</span> <span class="o"><</span> <span class="n">len</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span>
<span class="n">h</span> <span class="o">=</span> <span class="mi">31</span><span class="o">*</span><span class="n">h</span> <span class="o">+</span> <span class="n">val</span><span class="o">[</span><span class="n">off</span><span class="o">++];</span>
<span class="o">}</span>
<span class="n">hash</span> <span class="o">=</span> <span class="n">h</span><span class="o">;</span>
<span class="o">}</span>
<span class="k">return</span> <span class="n">h</span><span class="o">;</span>
<span class="o">}</span></code></pre>
<p>Cela correspond à une fonction de hachage non cryptographique très courante pour les chaînes de caractères. C'est une variante du <em>Bernstein hash</em>, aussi appelé djb2. Elle a ceci d'intéressant qu'elle est utilisée par beaucoup plateformes et qu'expliquer pourquoi elle marche et comment et pourquoi ont été choisi les valeurs est assez difficile. Les gens intéressés pourront découvrir d'<a href="http://www.eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx">autres fonctions</a> ainsi que passer beaucoup de temps à chercher les réponses à la question précédente.</p>
<p>Dans tous les cas nous appellerons cette variante de dbj2 sous le doux nom de DJBX31A.</p>
<p>Maintenant exécutons notre benchmark en utilisant Java 6u45 avec des chaines aléatoires de taille constante, 15 caractères, pour des collections allant de 10 à 30.000 éléments. Le résultat est le suivant:</p>
<p><img src="//img.linuxfr.org/img/68747470733a2f2f7261772e67697468756275736572636f6e74656e742e636f6d2f756e706f7274616e742d74686f75676874732f3230313430355f4a45505f3138302f6d61737465722f4a45505f3138305f616e616c797369735f66696c65732f4a45505f3138305f616e616c797369735f31305f312e706e673f7261773d74727565/JEP_180_analysis_10_1.png?raw=true" alt="png" title="Source : https://raw.githubusercontent.com/unportant-thoughts/201405_JEP_180/master/JEP_180_analysis_files/JEP_180_analysis_10_1.png?raw=true"></p>
<p>Dans ce cas nous avons le comportement normal attendu. Il y a peu de collisions. En moyenne le temps d'insertion est constant et ne dépend pas de la taille de la collection, <img style="display: inline; max-height: 1em;" class="mathjax" src="data:image/svg+xml;base64,PHN2ZyB4bWxuczp4bGluaz0iaHR0cDovL3d3dy53My5vcmcvMTk5OS94bGlu%0AayIgc3R5bGU9IndpZHRoOiA0LjQyOWV4OyBoZWlnaHQ6IDIuMTQzZXg7IHZl%0AcnRpY2FsLWFsaWduOiAtMC41NzFleDsgbWFyZ2luLXRvcDogMXB4OyBtYXJn%0AaW4tcmlnaHQ6IDBweDsgbWFyZ2luLWJvdHRvbTogMXB4OyBtYXJnaW4tbGVm%0AdDogMHB4OyBwb3NpdGlvbjogc3RhdGljOyAiIHZpZXdCb3g9IjAgLTcwMi4y%0ANTgxMjMyNTUxNTQ5IDE5MDggOTA1LjUxNjI0NjUxMDMxIiB4bWxucz0iaHR0%0AcDovL3d3dy53My5vcmcvMjAwMC9zdmciPjxkZWZzIGlkPSJNYXRoSmF4X1NW%0AR19nbHlwaHMiPjxwYXRoIGlkPSJTVElYV0VCTUFJTkktNEYiIHN0cm9rZS13%0AaWR0aD0iMTAiIGQ9Ik02OTkgNDE4YzAgLTE0NiAtODggLTI4NSAtMjA3IC0z%0ANjVjLTY1IC00NCAtMTQwIC03MSAtMjE0IC03MWMtMTMwIDAgLTIxOCA4NSAt%0AMjE4IDIzNGMwIDEyMiA3MyAyNjIgMTc3IDM1M2M2OSA2MCAxNTIgOTcgMjM3%0AIDk3YzE0NCAxIDIyNSAtOTYgMjI1IC0yNDh6TTU5NCA0ODFjMCA5NCAtNDkg%0AMTUyIC0xMjkgMTUyYy03NCAwIC0xMzcgLTUxIC0xODYgLTExN2MtNzMgLTk5%0AIC0xMTQgLTIzMiAtMTE0IC0zMzIgYzAgLTEwOSA0NiAtMTY5IDEzMCAtMTY5%0AYzY3IDAgMTI0IDM5IDE3MCA5NWM4NCAxMDQgMTI5IDI2OSAxMjkgMzcxWiI+%0APC9wYXRoPjxwYXRoIGlkPSJTVElYV0VCTUFJTi0yOCIgc3Ryb2tlLXdpZHRo%0APSIxMCIgZD0iTTMwNCAtMTYxbC0xMiAtMTZjLTE1OCA5MCAtMjQ0IDI1OSAt%0AMjQ0IDQyOWMwIDE4NSA4NyAzMjkgMjQ3IDQyNGw5IC0xNmMtMTM5IC0xMTkg%0ALTE3MCAtMjEyIC0xNzAgLTQwNWMwIC0xODYgMzAgLTI5OSAxNzAgLTQxNloi%0APjwvcGF0aD48cGF0aCBpZD0iU1RJWFdFQk1BSU4tMzEiIHN0cm9rZS13aWR0%0AaD0iMTAiIGQ9Ik0zOTQgMGgtMjc2djE1Yzc0IDQgOTUgMjUgOTUgODB2NDQ5%0AYzAgMzQgLTkgNDkgLTMwIDQ5Yy0xMCAwIC0yNyAtNSAtNDUgLTEybC0yNyAt%0AMTB2MTRsMTc5IDkxbDkgLTN2LTU5N2MwIC00MyAyMCAtNjEgOTUgLTYxdi0x%0ANVoiPjwvcGF0aD48cGF0aCBpZD0iU1RJWFdFQk1BSU4tMjkiIHN0cm9rZS13%0AaWR0aD0iMTAiIGQ9Ik0yOSA2NjBsMTIgMTZjMTUzIC05MiAyNDQgLTI1OSAy%0ANDQgLTQyOWMwIC0xODUgLTg4IC0zMjcgLTI0NyAtNDI0bC05IDE2YzE0MiAx%0AMTcgMTcwIDIxMSAxNzAgNDA1YzAgMTg3IC0yNSAzMDIgLTE3MCA0MTZaIj48%0AL3BhdGg+PC9kZWZzPjxnIHN0cm9rZT0iYmxhY2siIGZpbGw9ImJsYWNrIiBz%0AdHJva2Utd2lkdGg9IjAiIHRyYW5zZm9ybT0ibWF0cml4KDEgMCAwIC0xIDAg%0AMCkiPjx1c2UgaHJlZj0iI1NUSVhXRUJNQUlOSS00RiIgeGxpbms6aHJlZj0i%0AI1NUSVhXRUJNQUlOSS00RiI+PC91c2U+PHVzZSBocmVmPSIjU1RJWFdFQk1B%0ASU4tMjgiIHg9IjcyNyIgeT0iMCIgeGxpbms6aHJlZj0iI1NUSVhXRUJNQUlO%0ALTI4Ij48L3VzZT48dXNlIGhyZWY9IiNTVElYV0VCTUFJTi0zMSIgeD0iMTA2%0ANSIgeT0iMCIgeGxpbms6aHJlZj0iI1NUSVhXRUJNQUlOLTMxIj48L3VzZT48%0AdXNlIGhyZWY9IiNTVElYV0VCTUFJTi0yOSIgeD0iMTU3MCIgeT0iMCIgeGxp%0Abms6aHJlZj0iI1NUSVhXRUJNQUlOLTI5Ij48L3VzZT48L2c+PC9zdmc+%0A" alt="O(1)">. Nous voyons donc que la courbe est linéaire puisque nous répétons <img style="display: inline; max-height: 1em;" class="mathjax" src="data:image/svg+xml;base64,PHN2ZyB4bWxuczp4bGluaz0iaHR0cDovL3d3dy53My5vcmcvMTk5OS94bGlu%0AayIgc3R5bGU9IndpZHRoOiAxLjcxNGV4OyBoZWlnaHQ6IDEuNzE0ZXg7IHZl%0AcnRpY2FsLWFsaWduOiAtMC4xNDNleDsgbWFyZ2luLXRvcDogMXB4OyBtYXJn%0AaW4tcmlnaHQ6IDBweDsgbWFyZ2luLWJvdHRvbTogMXB4OyBtYXJnaW4tbGVm%0AdDogMHB4OyBwb3NpdGlvbjogc3RhdGljOyAiIHZpZXdCb3g9Ii0xNSAtNjc5%0ALjI1ODEyMzI1NTE1NDkgNzQ3IDcyMC41MTYyNDY1MTAzMSIgeG1sbnM9Imh0%0AdHA6Ly93d3cudzMub3JnLzIwMDAvc3ZnIj48ZGVmcyBpZD0iTWF0aEpheF9T%0AVkdfZ2x5cGhzIj48cGF0aCBpZD0iU1RJWFdFQk1BSU5JLTRFIiBzdHJva2Ut%0Ad2lkdGg9IjEwIiBkPSJNNzI3IDY1M3YtMTZjLTYzIC0xNCAtNjUgLTE2IC0x%0AMDIgLTE0NWwtMTQ2IC01MDdoLTE4bC0yMzAgNTUwbC0xMTQgLTQyMmMtNiAt%0AMjEgLTkgLTQxIC05IC01NGMwIC0yOCAxOCAtMzkgNzAgLTQzdi0xNmgtMTk4%0AdjE2YzU2IDggNzAgMjQgMTA2IDE1MmwxMTcgNDE1Yy0xNSAzNSAtMzkgNTQg%0ALTg2IDU0djE2aDE2MGwyMDcgLTQ5OWwxMDYgMzg4YzYgMjEgOCAzMiA4IDQ0%0AYzAgMzYgLTEyIDQ2IC02OSA1MXYxNmgxOThaIj48L3BhdGg+PC9kZWZzPjxn%0AIHN0cm9rZT0iYmxhY2siIGZpbGw9ImJsYWNrIiBzdHJva2Utd2lkdGg9IjAi%0AIHRyYW5zZm9ybT0ibWF0cml4KDEgMCAwIC0xIDAgMCkiPjx1c2UgaHJlZj0i%0AI1NUSVhXRUJNQUlOSS00RSIgeGxpbms6aHJlZj0iI1NUSVhXRUJNQUlOSS00%0ARSI+PC91c2U+PC9nPjwvc3ZnPg==%0A" alt="N"> fois une opération prenant un temps donné. Nous voyons aussi que nous arrivons à insérer environ 20 000 éléments par milliseconde.</p>
<h3 id="attaques-par-la-complexité">Attaques par la complexité</h3>
<p>Si vous avez bien suivi la première partie, vous savez que la performance d'une table de hachage dépend du nombre de collisions et donc de la qualité de sa fonction de hachage. Par nature une table de hachage ne permet pas de garantir que les opérations seront en <img style="display: inline; max-height: 1em;" class="mathjax" src="data:image/svg+xml;base64,PHN2ZyB4bWxuczp4bGluaz0iaHR0cDovL3d3dy53My5vcmcvMTk5OS94bGlu%0AayIgc3R5bGU9IndpZHRoOiA0LjQyOWV4OyBoZWlnaHQ6IDIuMTQzZXg7IHZl%0AcnRpY2FsLWFsaWduOiAtMC41NzFleDsgbWFyZ2luLXRvcDogMXB4OyBtYXJn%0AaW4tcmlnaHQ6IDBweDsgbWFyZ2luLWJvdHRvbTogMXB4OyBtYXJnaW4tbGVm%0AdDogMHB4OyBwb3NpdGlvbjogc3RhdGljOyAiIHZpZXdCb3g9IjAgLTcwMi4y%0ANTgxMjMyNTUxNTQ5IDE5MDggOTA1LjUxNjI0NjUxMDMxIiB4bWxucz0iaHR0%0AcDovL3d3dy53My5vcmcvMjAwMC9zdmciPjxkZWZzIGlkPSJNYXRoSmF4X1NW%0AR19nbHlwaHMiPjxwYXRoIGlkPSJTVElYV0VCTUFJTkktNEYiIHN0cm9rZS13%0AaWR0aD0iMTAiIGQ9Ik02OTkgNDE4YzAgLTE0NiAtODggLTI4NSAtMjA3IC0z%0ANjVjLTY1IC00NCAtMTQwIC03MSAtMjE0IC03MWMtMTMwIDAgLTIxOCA4NSAt%0AMjE4IDIzNGMwIDEyMiA3MyAyNjIgMTc3IDM1M2M2OSA2MCAxNTIgOTcgMjM3%0AIDk3YzE0NCAxIDIyNSAtOTYgMjI1IC0yNDh6TTU5NCA0ODFjMCA5NCAtNDkg%0AMTUyIC0xMjkgMTUyYy03NCAwIC0xMzcgLTUxIC0xODYgLTExN2MtNzMgLTk5%0AIC0xMTQgLTIzMiAtMTE0IC0zMzIgYzAgLTEwOSA0NiAtMTY5IDEzMCAtMTY5%0AYzY3IDAgMTI0IDM5IDE3MCA5NWM4NCAxMDQgMTI5IDI2OSAxMjkgMzcxWiI+%0APC9wYXRoPjxwYXRoIGlkPSJTVElYV0VCTUFJTi0yOCIgc3Ryb2tlLXdpZHRo%0APSIxMCIgZD0iTTMwNCAtMTYxbC0xMiAtMTZjLTE1OCA5MCAtMjQ0IDI1OSAt%0AMjQ0IDQyOWMwIDE4NSA4NyAzMjkgMjQ3IDQyNGw5IC0xNmMtMTM5IC0xMTkg%0ALTE3MCAtMjEyIC0xNzAgLTQwNWMwIC0xODYgMzAgLTI5OSAxNzAgLTQxNloi%0APjwvcGF0aD48cGF0aCBpZD0iU1RJWFdFQk1BSU4tMzEiIHN0cm9rZS13aWR0%0AaD0iMTAiIGQ9Ik0zOTQgMGgtMjc2djE1Yzc0IDQgOTUgMjUgOTUgODB2NDQ5%0AYzAgMzQgLTkgNDkgLTMwIDQ5Yy0xMCAwIC0yNyAtNSAtNDUgLTEybC0yNyAt%0AMTB2MTRsMTc5IDkxbDkgLTN2LTU5N2MwIC00MyAyMCAtNjEgOTUgLTYxdi0x%0ANVoiPjwvcGF0aD48cGF0aCBpZD0iU1RJWFdFQk1BSU4tMjkiIHN0cm9rZS13%0AaWR0aD0iMTAiIGQ9Ik0yOSA2NjBsMTIgMTZjMTUzIC05MiAyNDQgLTI1OSAy%0ANDQgLTQyOWMwIC0xODUgLTg4IC0zMjcgLTI0NyAtNDI0bC05IDE2YzE0MiAx%0AMTcgMTcwIDIxMSAxNzAgNDA1YzAgMTg3IC0yNSAzMDIgLTE3MCA0MTZaIj48%0AL3BhdGg+PC9kZWZzPjxnIHN0cm9rZT0iYmxhY2siIGZpbGw9ImJsYWNrIiBz%0AdHJva2Utd2lkdGg9IjAiIHRyYW5zZm9ybT0ibWF0cml4KDEgMCAwIC0xIDAg%0AMCkiPjx1c2UgaHJlZj0iI1NUSVhXRUJNQUlOSS00RiIgeGxpbms6aHJlZj0i%0AI1NUSVhXRUJNQUlOSS00RiI+PC91c2U+PHVzZSBocmVmPSIjU1RJWFdFQk1B%0ASU4tMjgiIHg9IjcyNyIgeT0iMCIgeGxpbms6aHJlZj0iI1NUSVhXRUJNQUlO%0ALTI4Ij48L3VzZT48dXNlIGhyZWY9IiNTVElYV0VCTUFJTi0zMSIgeD0iMTA2%0ANSIgeT0iMCIgeGxpbms6aHJlZj0iI1NUSVhXRUJNQUlOLTMxIj48L3VzZT48%0AdXNlIGhyZWY9IiNTVElYV0VCTUFJTi0yOSIgeD0iMTU3MCIgeT0iMCIgeGxp%0Abms6aHJlZj0iI1NUSVhXRUJNQUlOLTI5Ij48L3VzZT48L2c+PC9zdmc+%0A" alt="O(1)">, il s'agit seulement du cas moyen quand tout se passe bien. La performance au pire cas est <img style="display: inline; max-height: 1em;" class="mathjax" src="data:image/svg+xml;base64,PHN2ZyB4bWxuczp4bGluaz0iaHR0cDovL3d3dy53My5vcmcvMTk5OS94bGlu%0AayIgc3R5bGU9IndpZHRoOiA0LjQyOWV4OyBoZWlnaHQ6IDIuMTQzZXg7IHZl%0AcnRpY2FsLWFsaWduOiAtMC41NzFleDsgbWFyZ2luLXRvcDogMXB4OyBtYXJn%0AaW4tcmlnaHQ6IDBweDsgbWFyZ2luLWJvdHRvbTogMXB4OyBtYXJnaW4tbGVm%0AdDogMHB4OyBwb3NpdGlvbjogc3RhdGljOyAiIHZpZXdCb3g9IjAgLTcwMi4y%0ANTgxMjMyNTUxNTQ5IDE5MDggOTA1LjUxNjI0NjUxMDMxIiB4bWxucz0iaHR0%0AcDovL3d3dy53My5vcmcvMjAwMC9zdmciPjxkZWZzIGlkPSJNYXRoSmF4X1NW%0AR19nbHlwaHMiPjxwYXRoIGlkPSJTVElYV0VCTUFJTkktNEYiIHN0cm9rZS13%0AaWR0aD0iMTAiIGQ9Ik02OTkgNDE4YzAgLTE0NiAtODggLTI4NSAtMjA3IC0z%0ANjVjLTY1IC00NCAtMTQwIC03MSAtMjE0IC03MWMtMTMwIDAgLTIxOCA4NSAt%0AMjE4IDIzNGMwIDEyMiA3MyAyNjIgMTc3IDM1M2M2OSA2MCAxNTIgOTcgMjM3%0AIDk3YzE0NCAxIDIyNSAtOTYgMjI1IC0yNDh6TTU5NCA0ODFjMCA5NCAtNDkg%0AMTUyIC0xMjkgMTUyYy03NCAwIC0xMzcgLTUxIC0xODYgLTExN2MtNzMgLTk5%0AIC0xMTQgLTIzMiAtMTE0IC0zMzIgYzAgLTEwOSA0NiAtMTY5IDEzMCAtMTY5%0AYzY3IDAgMTI0IDM5IDE3MCA5NWM4NCAxMDQgMTI5IDI2OSAxMjkgMzcxWiI+%0APC9wYXRoPjxwYXRoIGlkPSJTVElYV0VCTUFJTi0yOCIgc3Ryb2tlLXdpZHRo%0APSIxMCIgZD0iTTMwNCAtMTYxbC0xMiAtMTZjLTE1OCA5MCAtMjQ0IDI1OSAt%0AMjQ0IDQyOWMwIDE4NSA4NyAzMjkgMjQ3IDQyNGw5IC0xNmMtMTM5IC0xMTkg%0ALTE3MCAtMjEyIC0xNzAgLTQwNWMwIC0xODYgMzAgLTI5OSAxNzAgLTQxNloi%0APjwvcGF0aD48cGF0aCBpZD0iU1RJWFdFQk1BSU5JLTZFIiBzdHJva2Utd2lk%0AdGg9IjEwIiBkPSJNNDYwIDExN2wxNCAtMTNjLTY4IC05MyAtOTMgLTExMyAt%0AMTQwIC0xMTNjLTI1IDAgLTQ3IDE2IC00NyA1NGMwIDEwIDIgMjMgMTYgNzVs%0ANDQgMTYyYzggMzEgMTQgNjcgMTQgNzljMCAxOCAtOSAyOSAtMjQgMjljLTQw%0AIDAgLTg1IC00OSAtMTQ4IC0xNDJjLTQ1IC02NyAtNTMgLTkwIC0xMDAgLTI0%0AOGgtNzVsOTYgMzUwYzEgNSAyIDExIDIgMTdjMCAyMCAtMTQgMjYgLTY1IDI3%0AdjE2YzgxIDE2IDEwOSAyMCAxNjIgMzFsNCAtMmwtNjcgLTIxOCBjMTAwIDE2%0AMCAxNjcgMjIwIDIzMSAyMjBjNDMgMCA2NSAtMjUgNjUgLTYxYzAgLTE4IC00%0AIC0zOSAtMTAgLTYwbC01NiAtMjAzYy0xMCAtMzYgLTE0IC01MyAtMTQgLTYx%0AYzAgLTkgNCAtMTggMTYgLTE4YzE0IDAgMzIgMTYgNjEgNTNjNyA4IDE0IDE3%0AIDIxIDI2WiI+PC9wYXRoPjxwYXRoIGlkPSJTVElYV0VCTUFJTi0yOSIgc3Ry%0Ab2tlLXdpZHRoPSIxMCIgZD0iTTI5IDY2MGwxMiAxNmMxNTMgLTkyIDI0NCAt%0AMjU5IDI0NCAtNDI5YzAgLTE4NSAtODggLTMyNyAtMjQ3IC00MjRsLTkgMTZj%0AMTQyIDExNyAxNzAgMjExIDE3MCA0MDVjMCAxODcgLTI1IDMwMiAtMTcwIDQx%0ANloiPjwvcGF0aD48L2RlZnM+PGcgc3Ryb2tlPSJibGFjayIgZmlsbD0iYmxh%0AY2siIHN0cm9rZS13aWR0aD0iMCIgdHJhbnNmb3JtPSJtYXRyaXgoMSAwIDAg%0ALTEgMCAwKSI+PHVzZSBocmVmPSIjU1RJWFdFQk1BSU5JLTRGIiB4bGluazpo%0AcmVmPSIjU1RJWFdFQk1BSU5JLTRGIj48L3VzZT48dXNlIGhyZWY9IiNTVElY%0AV0VCTUFJTi0yOCIgeD0iNzI3IiB5PSIwIiB4bGluazpocmVmPSIjU1RJWFdF%0AQk1BSU4tMjgiPjwvdXNlPjx1c2UgaHJlZj0iI1NUSVhXRUJNQUlOSS02RSIg%0AeD0iMTA2NSIgeT0iMCIgeGxpbms6aHJlZj0iI1NUSVhXRUJNQUlOSS02RSI+%0APC91c2U+PHVzZSBocmVmPSIjU1RJWFdFQk1BSU4tMjkiIHg9IjE1NzAiIHk9%0AIjAiIHhsaW5rOmhyZWY9IiNTVElYV0VCTUFJTi0yOSI+PC91c2U+PC9nPjwv%0Ac3ZnPg==%0A" alt="O(n)">.</p>
<p>Ce fait est connu de tout étudiant ayant suivi une introduction à l'algorithmique. Seulement il y a quelques années certains ont eu l'idée d'utiliser ce pire cas pour faire des dénis de service. C'est une attaque par la complexité. L'idée est simple, beaucoup d'application stockent en mémoire des chaînes de caractères fournies par un utilisateur dans une table de hachage. S'il arrive à fournir des chaînes qui vont systématiquement créer des collisions, alors il va pouvoir ralentir très fortement le système.</p>
<p>L'idée n'est pas nouvelle, elle a été parfaitement <a href="http://madchat.fr/reseau/dos/CrosbyWallach_UsenixSec2003.pdf">documentée</a> en 2003 par Scott A. Crosby et Dan S. Wallach lors de l'Usenix-Sec. Ils avaient alors étudié Perl, qui avait réagi et fourni un correctif. Tout le monde a alors oublié cette histoire pendant quelques années.</p>
<p>En 2011, Alexander Klink et Julian Wälde se souviennent de cette histoire et partent alors explorer ce qu'il est possible de faire avec presque 10 ans après. Les <a href="http://events.ccc.de/congress/2011/Fahrplan/attachments/2007_28C3_Effective_DoS_on_web_application_platforms.pdf">slides</a> du 28C3 décrivent très bien ce qu'ils trouvent. En gros presque toutes les plateformes majeures sont vulnérable de PHP à Java en passant par Python puisque tout le monde ou presque utilise une variante de djb2, pour lequel il est très facile de générer des collisions. Le résultat c'est qu'on peut faire un déni de service sur a peu près n'importe quoi avec très peu de données. Avec 2MB de données ils arrivent à occuper un processeur pendant plus d'une demi-heure.</p>
<p>Le benchmark suivant compare la courbe précédente avec une où toutes les clés se retrouvent dans la même case car on génère spécialement les clés pour que DJBX31A retourne toujours la même valeur bien que les chaînes soient différentes.</p>
<p><img src="//img.linuxfr.org/img/68747470733a2f2f7261772e67697468756275736572636f6e74656e742e636f6d2f756e706f7274616e742d74686f75676874732f3230313430355f4a45505f3138302f6d61737465722f4a45505f3138305f616e616c797369735f66696c65732f4a45505f3138305f616e616c797369735f31355f312e706e673f7261773d74727565/JEP_180_analysis_15_1.png?raw=true" alt="png" title="Source : https://raw.githubusercontent.com/unportant-thoughts/201405_JEP_180/master/JEP_180_analysis_files/JEP_180_analysis_15_1.png?raw=true"></p>
<p>Comme on peut le voir l'effet est plutôt dramatique. Chaque insertion dépend donc maintenant du nombre d'éléments dans la table de hachage. Si vous vous rappelez du code de la méthode <em>put()</em>, nous avons à parcourir tous les éléments à chaque fois. Puisque nous allons insérer un nouvel élément, il faut vérifier tous les autres. La courbe devient donc quadratique. Pour 20 000 éléments on peut voir que l'on est déjà 1000 fois plus lent. Vous pouvez facilement extrapoler pour 50 000 ou 100 000.</p>
<h3 id="java-7u6--alternative-string-hashing">Java 7u6 & "alternative string-hashing"</h3>
<p>Comme la plupart des plateformes impactées par cette découverte, Java cherche une solution. Et beaucoup vont choisir une solution similaire. L'idée est qu'il faut empêcher à un utilisateur de pouvoir générer des collisions. Une solution est d'utiliser des fonctions de hachage cryptographique qui sont conçues pour cela. En pratique ce n'est pas possible car elles sont beaucoup trop lentes (grossièrement il y a minimum un ordre de grandeur d'écart). Le consensus est alors de migrer vers une autre fonction de hachage: <a href="http://en.wikipedia.org/wiki/MurmurHash">Murmur</a> 2 ou 3. Murmur est une bonne fonction de hachage non cryptographique, elle est rapide et fournie de bons résultats. En plus on peut l'initialiser avec une graine qui va conditionner la valeur de sortie. L'idée est donc de générer la graine à l'exécution. Il devient alors compliqué à l'utilisateur de générer des collisions car il a besoin de la graine et qu'il n'y a pas accès.</p>
<p>Python utilise cette solution et décide de <a href="http://bugs.python.org/issue13703">changer sa fonction de hachage pour Murmur</a>.</p>
<p>Java veut faire de même mais a un problème supplémentaire. La Javadoc de la méthode <code>hashCode</code> de String documente l'implémentation sous-jacente:</p>
<pre><code class="java"> <span class="cm">/**</span>
<span class="cm"> * Returns a hash code for this string. The hash code for a</span>
<span class="cm"> * <code>String</code> object is computed as</span>
<span class="cm"> * <blockquote><pre></span>
<span class="cm"> * s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]</span>
<span class="cm"> * </pre></blockquote></span>
<span class="cm"> * using <code>int</code> arithmetic, where <code>s[i]</code> is the</span>
<span class="cm"> * <i>i</i>th character of the string, <code>n</code> is the length of</span>
<span class="cm"> * the string, and <code>^</code> indicates exponentiation.</span>
<span class="cm"> * (The hash value of the empty string is zero.)</span>
<span class="cm"> *</span>
<span class="cm"> * @return a hash code value for this object.</span>
<span class="cm"> */</span></code></pre>
<p>DJBX31A fait donc partie du contrat de la classe, et on ne peut pas le changer sans risque de casser la compatibilité et le comportement des applications. C'est une règle stricte du côté de Java.</p>
<p>Pour cette raison on imagine donc ce qui est pour moi l'un des patchs les plus dégueulasses de l'histoire du JDK qui a été livré en Java <a href="http://www.oracle.com/technetwork/java/javase/7u6-relnotes-1729681.html">7u6</a>. En gros on ne touche à rien de ce qui existe. On rajoute une nouvelle méthode <code>hash32</code> à la classe String qui repose sur Murmur.</p>
<pre><code class="java"> <span class="kt">int</span> <span class="nf">hash32</span><span class="o">()</span> <span class="o">{</span>
<span class="kt">int</span> <span class="n">h</span> <span class="o">=</span> <span class="n">hash32</span><span class="o">;</span>
<span class="k">if</span> <span class="o">(</span><span class="mi">0</span> <span class="o">==</span> <span class="n">h</span><span class="o">)</span> <span class="o">{</span>
<span class="c1">// harmless data race on hash32 here.</span>
<span class="n">h</span> <span class="o">=</span> <span class="n">sun</span><span class="o">.</span><span class="na">misc</span><span class="o">.</span><span class="na">Hashing</span><span class="o">.</span><span class="na">murmur3_32</span><span class="o">(</span><span class="n">HASHING_SEED</span><span class="o">,</span> <span class="n">value</span><span class="o">,</span> <span class="mi">0</span><span class="o">,</span>
<span class="n">value</span><span class="o">.</span><span class="na">length</span><span class="o">);</span>
<span class="c1">// ensure result is not zero to avoid recalcing</span>
<span class="n">h</span> <span class="o">=</span> <span class="o">(</span><span class="mi">0</span> <span class="o">!=</span> <span class="n">h</span><span class="o">)</span> <span class="o">?</span> <span class="n">h</span> <span class="o">:</span> <span class="mi">1</span><span class="o">;</span>
<span class="n">hash32</span> <span class="o">=</span> <span class="n">h</span><span class="o">;</span>
<span class="o">}</span>
<span class="k">return</span> <span class="n">h</span><span class="o">;</span>
<span class="o">}</span></code></pre>
<p>Maintenant on patch les collections utilisant des fonctions de hachage pour faire la chose suivante: On regarde le type de l'élément, si c'est String alors on invoque <code>hash32</code> par une introspection dédiée car la méthode n'est pas publique, sinon on invoque <code>hashCode</code>. Seulement les String sont immutables, et la valeur de <code>hashCode</code> était cachée pour éviter de le recalculer à chaque fois. On doit donc faire de même avec <code>hash32</code> qui impose donc 4 octets supplémentaire à chaque instance de String. Pour finir on initialise <code>HASHING_SEED</code> dynamiquement à l'initialisation pour empêcher les collisions.</p>
<p>C'est cool on n'a pas touché à <code>hashCode</code> ! Seulement voilà le comportement des applications peut toujours changer même en remplaçant la fonction de hachage uniquement dans les collections. Alors on rajoute un flag pour décider si on veut oui ou non utiliser le <em>alternative string-hash</em> dans les collections.</p>
<p>Voir <a href="http://permalink.gmane.org/gmane.comp.java.openjdk.core-%20libs.devel/10361">le mail</a> sur la mailing list d'OpenJDK ainsi que le <a href="http://cr.openjdk.java.net/%7Emduigou/althashing7/8/webrev/">patch</a>.</p>
<p>Voilà ça pique les yeux mais ça fait le job ! Refaisons tourner le même benchmark avec Java 7u55:</p>
<p><img src="//img.linuxfr.org/img/68747470733a2f2f7261772e67697468756275736572636f6e74656e742e636f6d2f756e706f7274616e742d74686f75676874732f3230313430355f4a45505f3138302f6d61737465722f4a45505f3138305f616e616c797369735f66696c65732f4a45505f3138305f616e616c797369735f31395f312e706e673f7261773d74727565/JEP_180_analysis_19_1.png?raw=true" alt="png" title="Source : https://raw.githubusercontent.com/unportant-thoughts/201405_JEP_180/master/JEP_180_analysis_files/JEP_180_analysis_19_1.png?raw=true"></p>
<p>Ah oui j'ai dit qu'il y avait une option pour <em>l'alternative string-hashing</em> mais j'ai pas dit qu'elle était activée par défaut… Recommençons avec <code>-Djdk.map.althashing.threshold=1</code></p>
<p><img src="//img.linuxfr.org/img/68747470733a2f2f7261772e67697468756275736572636f6e74656e742e636f6d2f756e706f7274616e742d74686f75676874732f3230313430355f4a45505f3138302f6d61737465722f4a45505f3138305f616e616c797369735f66696c65732f4a45505f3138305f616e616c797369735f32315f312e706e673f7261773d74727565/JEP_180_analysis_21_1.png?raw=true" alt="png" title="Source : https://raw.githubusercontent.com/unportant-thoughts/201405_JEP_180/master/JEP_180_analysis_files/JEP_180_analysis_21_1.png?raw=true"></p>
<p>C'est mieux non ? Bon OK par défaut on est toujours vulnérable trois ans après…</p>
<h3 id="attaques-par-la-complexité-bis">Attaques par la complexité (bis)</h3>
<p>Seulement voilà, entre temps quelques-uns ont commencés à creuser le problème. Ils ont attaqué Murmur3 avec graine qui n'a pas <a href="http://www.eng.tau.ac.il/%7Eyash/C2_039_Wool.pdf">tenu</a> très longtemps. Ca a d'ailleurs été <a href="http://www.youtube.com/watch?v=wGYj8fhhUVA">présenté au 29c3</a>. Dans les speakers on notera DJB, oui c'est le même.</p>
<p>Rebelote, tous ceux qui sont passés à Murmur sont impactés ainsi que quelques copains dont les fonctions ont aussi été cassées. C'est un peu mois trivial de générer des collisions avec Murmur mais le travail difficile a été fait pour nous. On n'a qu'à écrire le code…</p>
<p>Essayons de refaire tourner notre benchmark en générant des collisions contre Murmur:</p>
<p><img src="//img.linuxfr.org/img/68747470733a2f2f7261772e67697468756275736572636f6e74656e742e636f6d2f756e706f7274616e742d74686f75676874732f3230313430355f4a45505f3138302f6d61737465722f4a45505f3138305f616e616c797369735f66696c65732f4a45505f3138305f616e616c797369735f32355f312e706e673f7261773d74727565/JEP_180_analysis_25_1.png?raw=true" alt="png" title="Source : https://raw.githubusercontent.com/unportant-thoughts/201405_JEP_180/master/JEP_180_analysis_files/JEP_180_analysis_25_1.png?raw=true"></p>
<p>Cette fois nous comparons le comportement usuel avec:</p>
<ul>
<li>Des collisions contre DJBX31A sans <em>l'alternative string-hashing</em>
</li>
<li>Des collisions contre Murmur3 avec <em>l'alternative string-hashing</em>
</li>
</ul><p>(Je n'ai pas investigué les deux points à 15k et 25k qui sont très étranges. Le générateur passe les tests unitaires et les résultats eux sont stables…)</p>
<p>C'est grosso modo la même chose. On a donc fait un patch moche qui ne sert plus à rien puisque dans les deux cas on est vulnérable…</p>
<h3 id="jep-180-une-solution-intéressante">JEP 180: Une solution intéressante</h3>
<p>Maintenant qu'est-ce qu'on fait ?</p>
<p>En même temps qu'ils ont cassé Murmur avec graine, DJB et ses potes ont proposé une nouvelle fonction de hachage: <a href="http://en.wikipedia.org/wiki/SipHash">SipHash</a>. Elle est vendue comme étant aussi rapide que les précédentes mais résistante aux attaques par collisions.</p>
<p>La plupart des plateformes ont migré vers SipHash. Python par exemple. Et comme on s'est déjà fait avoir une fois on en profite pour faire la <a href="http://legacy.python.org/dev/peps/pep-0456/">PEP 456</a> qui permet d'avoir des fonctions de hash interchangeable pour les chaîne de caractères et tableaux d'octets. On bascule à SipHash mais comme on sait que ca risque de recommencer, on prévoit le coup…</p>
<p>Du côté de Java on a toujours le même problème avec <code>hashCode</code>, rechanger hash32 fait prendre quelques risque aussi et le patch initial étant "crado" on aimerait bien s'en débarrasser. On choisit donc une approche radicalement différente. Plutôt que de chercher une fonction de hachage parfaite, on rebascule sur DJBX31A. On s'applique plutôt à résoudre le problème du <img style="display: inline; max-height: 1em;" class="mathjax" src="data:image/svg+xml;base64,PHN2ZyB4bWxuczp4bGluaz0iaHR0cDovL3d3dy53My5vcmcvMTk5OS94bGlu%0AayIgc3R5bGU9IndpZHRoOiA0LjQyOWV4OyBoZWlnaHQ6IDIuMTQzZXg7IHZl%0AcnRpY2FsLWFsaWduOiAtMC41NzFleDsgbWFyZ2luLXRvcDogMXB4OyBtYXJn%0AaW4tcmlnaHQ6IDBweDsgbWFyZ2luLWJvdHRvbTogMXB4OyBtYXJnaW4tbGVm%0AdDogMHB4OyBwb3NpdGlvbjogc3RhdGljOyAiIHZpZXdCb3g9IjAgLTcwMi4y%0ANTgxMjMyNTUxNTQ5IDE5MDggOTA1LjUxNjI0NjUxMDMxIiB4bWxucz0iaHR0%0AcDovL3d3dy53My5vcmcvMjAwMC9zdmciPjxkZWZzIGlkPSJNYXRoSmF4X1NW%0AR19nbHlwaHMiPjxwYXRoIGlkPSJTVElYV0VCTUFJTkktNEYiIHN0cm9rZS13%0AaWR0aD0iMTAiIGQ9Ik02OTkgNDE4YzAgLTE0NiAtODggLTI4NSAtMjA3IC0z%0ANjVjLTY1IC00NCAtMTQwIC03MSAtMjE0IC03MWMtMTMwIDAgLTIxOCA4NSAt%0AMjE4IDIzNGMwIDEyMiA3MyAyNjIgMTc3IDM1M2M2OSA2MCAxNTIgOTcgMjM3%0AIDk3YzE0NCAxIDIyNSAtOTYgMjI1IC0yNDh6TTU5NCA0ODFjMCA5NCAtNDkg%0AMTUyIC0xMjkgMTUyYy03NCAwIC0xMzcgLTUxIC0xODYgLTExN2MtNzMgLTk5%0AIC0xMTQgLTIzMiAtMTE0IC0zMzIgYzAgLTEwOSA0NiAtMTY5IDEzMCAtMTY5%0AYzY3IDAgMTI0IDM5IDE3MCA5NWM4NCAxMDQgMTI5IDI2OSAxMjkgMzcxWiI+%0APC9wYXRoPjxwYXRoIGlkPSJTVElYV0VCTUFJTi0yOCIgc3Ryb2tlLXdpZHRo%0APSIxMCIgZD0iTTMwNCAtMTYxbC0xMiAtMTZjLTE1OCA5MCAtMjQ0IDI1OSAt%0AMjQ0IDQyOWMwIDE4NSA4NyAzMjkgMjQ3IDQyNGw5IC0xNmMtMTM5IC0xMTkg%0ALTE3MCAtMjEyIC0xNzAgLTQwNWMwIC0xODYgMzAgLTI5OSAxNzAgLTQxNloi%0APjwvcGF0aD48cGF0aCBpZD0iU1RJWFdFQk1BSU5JLTZFIiBzdHJva2Utd2lk%0AdGg9IjEwIiBkPSJNNDYwIDExN2wxNCAtMTNjLTY4IC05MyAtOTMgLTExMyAt%0AMTQwIC0xMTNjLTI1IDAgLTQ3IDE2IC00NyA1NGMwIDEwIDIgMjMgMTYgNzVs%0ANDQgMTYyYzggMzEgMTQgNjcgMTQgNzljMCAxOCAtOSAyOSAtMjQgMjljLTQw%0AIDAgLTg1IC00OSAtMTQ4IC0xNDJjLTQ1IC02NyAtNTMgLTkwIC0xMDAgLTI0%0AOGgtNzVsOTYgMzUwYzEgNSAyIDExIDIgMTdjMCAyMCAtMTQgMjYgLTY1IDI3%0AdjE2YzgxIDE2IDEwOSAyMCAxNjIgMzFsNCAtMmwtNjcgLTIxOCBjMTAwIDE2%0AMCAxNjcgMjIwIDIzMSAyMjBjNDMgMCA2NSAtMjUgNjUgLTYxYzAgLTE4IC00%0AIC0zOSAtMTAgLTYwbC01NiAtMjAzYy0xMCAtMzYgLTE0IC01MyAtMTQgLTYx%0AYzAgLTkgNCAtMTggMTYgLTE4YzE0IDAgMzIgMTYgNjEgNTNjNyA4IDE0IDE3%0AIDIxIDI2WiI+PC9wYXRoPjxwYXRoIGlkPSJTVElYV0VCTUFJTi0yOSIgc3Ry%0Ab2tlLXdpZHRoPSIxMCIgZD0iTTI5IDY2MGwxMiAxNmMxNTMgLTkyIDI0NCAt%0AMjU5IDI0NCAtNDI5YzAgLTE4NSAtODggLTMyNyAtMjQ3IC00MjRsLTkgMTZj%0AMTQyIDExNyAxNzAgMjExIDE3MCA0MDVjMCAxODcgLTI1IDMwMiAtMTcwIDQx%0ANloiPjwvcGF0aD48L2RlZnM+PGcgc3Ryb2tlPSJibGFjayIgZmlsbD0iYmxh%0AY2siIHN0cm9rZS13aWR0aD0iMCIgdHJhbnNmb3JtPSJtYXRyaXgoMSAwIDAg%0ALTEgMCAwKSI+PHVzZSBocmVmPSIjU1RJWFdFQk1BSU5JLTRGIiB4bGluazpo%0AcmVmPSIjU1RJWFdFQk1BSU5JLTRGIj48L3VzZT48dXNlIGhyZWY9IiNTVElY%0AV0VCTUFJTi0yOCIgeD0iNzI3IiB5PSIwIiB4bGluazpocmVmPSIjU1RJWFdF%0AQk1BSU4tMjgiPjwvdXNlPjx1c2UgaHJlZj0iI1NUSVhXRUJNQUlOSS02RSIg%0AeD0iMTA2NSIgeT0iMCIgeGxpbms6aHJlZj0iI1NUSVhXRUJNQUlOSS02RSI+%0APC91c2U+PHVzZSBocmVmPSIjU1RJWFdFQk1BSU4tMjkiIHg9IjE1NzAiIHk9%0AIjAiIHhsaW5rOmhyZWY9IiNTVElYV0VCTUFJTi0yOSI+PC91c2U+PC9nPjwv%0Ac3ZnPg==%0A" alt="O(n)"> au pire cas. Le <img style="display: inline; max-height: 1em;" class="mathjax" src="data:image/svg+xml;base64,PHN2ZyB4bWxuczp4bGluaz0iaHR0cDovL3d3dy53My5vcmcvMTk5OS94bGlu%0AayIgc3R5bGU9IndpZHRoOiA0LjQyOWV4OyBoZWlnaHQ6IDIuMTQzZXg7IHZl%0AcnRpY2FsLWFsaWduOiAtMC41NzFleDsgbWFyZ2luLXRvcDogMXB4OyBtYXJn%0AaW4tcmlnaHQ6IDBweDsgbWFyZ2luLWJvdHRvbTogMXB4OyBtYXJnaW4tbGVm%0AdDogMHB4OyBwb3NpdGlvbjogc3RhdGljOyAiIHZpZXdCb3g9IjAgLTcwMi4y%0ANTgxMjMyNTUxNTQ5IDE5MDggOTA1LjUxNjI0NjUxMDMxIiB4bWxucz0iaHR0%0AcDovL3d3dy53My5vcmcvMjAwMC9zdmciPjxkZWZzIGlkPSJNYXRoSmF4X1NW%0AR19nbHlwaHMiPjxwYXRoIGlkPSJTVElYV0VCTUFJTkktNEYiIHN0cm9rZS13%0AaWR0aD0iMTAiIGQ9Ik02OTkgNDE4YzAgLTE0NiAtODggLTI4NSAtMjA3IC0z%0ANjVjLTY1IC00NCAtMTQwIC03MSAtMjE0IC03MWMtMTMwIDAgLTIxOCA4NSAt%0AMjE4IDIzNGMwIDEyMiA3MyAyNjIgMTc3IDM1M2M2OSA2MCAxNTIgOTcgMjM3%0AIDk3YzE0NCAxIDIyNSAtOTYgMjI1IC0yNDh6TTU5NCA0ODFjMCA5NCAtNDkg%0AMTUyIC0xMjkgMTUyYy03NCAwIC0xMzcgLTUxIC0xODYgLTExN2MtNzMgLTk5%0AIC0xMTQgLTIzMiAtMTE0IC0zMzIgYzAgLTEwOSA0NiAtMTY5IDEzMCAtMTY5%0AYzY3IDAgMTI0IDM5IDE3MCA5NWM4NCAxMDQgMTI5IDI2OSAxMjkgMzcxWiI+%0APC9wYXRoPjxwYXRoIGlkPSJTVElYV0VCTUFJTi0yOCIgc3Ryb2tlLXdpZHRo%0APSIxMCIgZD0iTTMwNCAtMTYxbC0xMiAtMTZjLTE1OCA5MCAtMjQ0IDI1OSAt%0AMjQ0IDQyOWMwIDE4NSA4NyAzMjkgMjQ3IDQyNGw5IC0xNmMtMTM5IC0xMTkg%0ALTE3MCAtMjEyIC0xNzAgLTQwNWMwIC0xODYgMzAgLTI5OSAxNzAgLTQxNloi%0APjwvcGF0aD48cGF0aCBpZD0iU1RJWFdFQk1BSU5JLTZFIiBzdHJva2Utd2lk%0AdGg9IjEwIiBkPSJNNDYwIDExN2wxNCAtMTNjLTY4IC05MyAtOTMgLTExMyAt%0AMTQwIC0xMTNjLTI1IDAgLTQ3IDE2IC00NyA1NGMwIDEwIDIgMjMgMTYgNzVs%0ANDQgMTYyYzggMzEgMTQgNjcgMTQgNzljMCAxOCAtOSAyOSAtMjQgMjljLTQw%0AIDAgLTg1IC00OSAtMTQ4IC0xNDJjLTQ1IC02NyAtNTMgLTkwIC0xMDAgLTI0%0AOGgtNzVsOTYgMzUwYzEgNSAyIDExIDIgMTdjMCAyMCAtMTQgMjYgLTY1IDI3%0AdjE2YzgxIDE2IDEwOSAyMCAxNjIgMzFsNCAtMmwtNjcgLTIxOCBjMTAwIDE2%0AMCAxNjcgMjIwIDIzMSAyMjBjNDMgMCA2NSAtMjUgNjUgLTYxYzAgLTE4IC00%0AIC0zOSAtMTAgLTYwbC01NiAtMjAzYy0xMCAtMzYgLTE0IC01MyAtMTQgLTYx%0AYzAgLTkgNCAtMTggMTYgLTE4YzE0IDAgMzIgMTYgNjEgNTNjNyA4IDE0IDE3%0AIDIxIDI2WiI+PC9wYXRoPjxwYXRoIGlkPSJTVElYV0VCTUFJTi0yOSIgc3Ry%0Ab2tlLXdpZHRoPSIxMCIgZD0iTTI5IDY2MGwxMiAxNmMxNTMgLTkyIDI0NCAt%0AMjU5IDI0NCAtNDI5YzAgLTE4NSAtODggLTMyNyAtMjQ3IC00MjRsLTkgMTZj%0AMTQyIDExNyAxNzAgMjExIDE3MCA0MDVjMCAxODcgLTI1IDMwMiAtMTcwIDQx%0ANloiPjwvcGF0aD48L2RlZnM+PGcgc3Ryb2tlPSJibGFjayIgZmlsbD0iYmxh%0AY2siIHN0cm9rZS13aWR0aD0iMCIgdHJhbnNmb3JtPSJtYXRyaXgoMSAwIDAg%0ALTEgMCAwKSI+PHVzZSBocmVmPSIjU1RJWFdFQk1BSU5JLTRGIiB4bGluazpo%0AcmVmPSIjU1RJWFdFQk1BSU5JLTRGIj48L3VzZT48dXNlIGhyZWY9IiNTVElY%0AV0VCTUFJTi0yOCIgeD0iNzI3IiB5PSIwIiB4bGluazpocmVmPSIjU1RJWFdF%0AQk1BSU4tMjgiPjwvdXNlPjx1c2UgaHJlZj0iI1NUSVhXRUJNQUlOSS02RSIg%0AeD0iMTA2NSIgeT0iMCIgeGxpbms6aHJlZj0iI1NUSVhXRUJNQUlOSS02RSI+%0APC91c2U+PHVzZSBocmVmPSIjU1RJWFdFQk1BSU4tMjkiIHg9IjE1NzAiIHk9%0AIjAiIHhsaW5rOmhyZWY9IiNTVElYV0VCTUFJTi0yOSI+PC91c2U+PC9nPjwv%0Ac3ZnPg==%0A" alt="O(n)"> vient du fait que les collisions sont gérées avec une liste chaînée. Si on utilise un arbre balancé plutôt qu'une liste on passe en <img style="display: inline; max-height: 1em;" class="mathjax" src="data:image/svg+xml;base64,PHN2ZyB4bWxuczp4bGluaz0iaHR0cDovL3d3dy53My5vcmcvMTk5OS94bGlu%0AayIgc3R5bGU9IndpZHRoOiA5ZXg7IGhlaWdodDogMi4xNDNleDsgdmVydGlj%0AYWwtYWxpZ246IC0wLjU3MWV4OyBtYXJnaW4tdG9wOiAxcHg7IG1hcmdpbi1y%0AaWdodDogMHB4OyBtYXJnaW4tYm90dG9tOiAxcHg7IG1hcmdpbi1sZWZ0OiAw%0AcHg7IHBvc2l0aW9uOiBzdGF0aWM7ICIgdmlld0JveD0iMCAtNzA5LjI1ODEy%0AMzI1NTE1NDkgMzg3OCA5NDEuNTE2MjQ2NTEwMzEiIHhtbG5zPSJodHRwOi8v%0Ad3d3LnczLm9yZy8yMDAwL3N2ZyI+PGRlZnMgaWQ9Ik1hdGhKYXhfU1ZHX2ds%0AeXBocyI+PHBhdGggaWQ9IlNUSVhXRUJNQUlOSS00RiIgc3Ryb2tlLXdpZHRo%0APSIxMCIgZD0iTTY5OSA0MThjMCAtMTQ2IC04OCAtMjg1IC0yMDcgLTM2NWMt%0ANjUgLTQ0IC0xNDAgLTcxIC0yMTQgLTcxYy0xMzAgMCAtMjE4IDg1IC0yMTgg%0AMjM0YzAgMTIyIDczIDI2MiAxNzcgMzUzYzY5IDYwIDE1MiA5NyAyMzcgOTdj%0AMTQ0IDEgMjI1IC05NiAyMjUgLTI0OHpNNTk0IDQ4MWMwIDk0IC00OSAxNTIg%0ALTEyOSAxNTJjLTc0IDAgLTEzNyAtNTEgLTE4NiAtMTE3Yy03MyAtOTkgLTEx%0ANCAtMjMyIC0xMTQgLTMzMiBjMCAtMTA5IDQ2IC0xNjkgMTMwIC0xNjljNjcg%0AMCAxMjQgMzkgMTcwIDk1Yzg0IDEwNCAxMjkgMjY5IDEyOSAzNzFaIj48L3Bh%0AdGg+PHBhdGggaWQ9IlNUSVhXRUJNQUlOLTI4IiBzdHJva2Utd2lkdGg9IjEw%0AIiBkPSJNMzA0IC0xNjFsLTEyIC0xNmMtMTU4IDkwIC0yNDQgMjU5IC0yNDQg%0ANDI5YzAgMTg1IDg3IDMyOSAyNDcgNDI0bDkgLTE2Yy0xMzkgLTExOSAtMTcw%0AIC0yMTIgLTE3MCAtNDA1YzAgLTE4NiAzMCAtMjk5IDE3MCAtNDE2WiI+PC9w%0AYXRoPjxwYXRoIGlkPSJTVElYV0VCTUFJTkktNkMiIHN0cm9rZS13aWR0aD0i%0AMTAiIGQ9Ik0yNzkgNjc4bC0xNTMgLTU4NWMtNSAtMTggLTggLTM1IC04IC00%0AM2MwIC0xMiA3IC0xOCAxNyAtMThjMTUgMCAzOCAxNiA2NyA1N2wyNSAzNWwx%0ANCAtMTBjLTYwIC05NSAtOTcgLTEyNSAtMTUxIC0xMjVjLTMyIDAgLTQ5IDE5%0AIC00OSA1NmMwIDggMSAyMCA0IDMwbDEzNyA1MjRjMyAxMCAzIDE2IDMgMTlj%0AMCAxMiAtMTcgMjIgLTQ5IDIyaC0xOHYxNmM1OSA3IDk2IDE0IDE1NSAyN1oi%0APjwvcGF0aD48cGF0aCBpZD0iU1RJWFdFQk1BSU5JLTZGIiBzdHJva2Utd2lk%0AdGg9IjEwIiBkPSJNNDY4IDMwMWMwIC03NiAtNDAgLTE2NCAtMTA2IC0yMjlj%0ALTU4IC01OCAtMTIyIC04MyAtMTg4IC04M2MtOTQgMCAtMTQ3IDUyIC0xNDcg%0AMTM5YzAgMTEyIDc1IDIyNyAxODAgMjgzYzM5IDIxIDc5IDMwIDEyMCAzMGM4%0AMSAwIDE0MSAtNTIgMTQxIC0xNDB6TTM4NCAzMjZjMCA2MSAtMjggOTQgLTcx%0AIDk0Yy00NCAwIC04OCAtMzEgLTEyOCAtOTFjLTQ2IC03MCAtNzQgLTE0OSAt%0ANzQgLTIyOGMwIC02MCAzMSAtOTEgNzggLTkxIGM0NCAwIDgyIDI5IDEyMSA4%0AM2M0NiA2MyA3NCAxNTcgNzQgMjMzWiI+PC9wYXRoPjxwYXRoIGlkPSJTVElY%0AV0VCTUFJTkktNjciIHN0cm9rZS13aWR0aD0iMTAiIGQ9Ik00NzEgMzY2aC00%0AOWM5IC0xOCA5IC0zNCA5IC01MWMwIC04NCAtOTIgLTE2NCAtMTg1IC0xNjRj%0ALTExIDAgLTIyIDEgLTMxIDNjLTMgMSAtNSAxIC03IDFjLTE3IDAgLTM2IC0y%0AMCAtMzYgLTQxYzAgLTE4IDI3IC0zMSA3MSAtNDJjOTYgLTIzIDE0MiAtNjcg%0AMTQyIC0xMjdjMCAtODcgLTc3IC0xNTEgLTIxMCAtMTUxYy0xMDIgMCAtMTY3%0AIDM2IC0xNjcgMTA4YzAgNTEgMTkgNzggMTE3IDEzN2MtMTggMTEgLTI3IDI2%0AIC0yNyAzOSBjMCAyOSAyMyA1OSA3NyA4NGMtNTYgMjAgLTc5IDU2IC03OSAx%0AMDhjMCAxMDIgMTAwIDE3MSAyMDEgMTcxYzM4IDAgNzEgLTkgOTggLTI4Yzgg%0ALTYgMTMgLTggMTYgLThoNjB2LTM5ek0zNTIgMzQ4YzAgNTMgLTE5IDcxIC01%0ANiA3MWMtNjIgMCAtMTIyIC03MyAtMTIyIC0xNzJjMCAtNDcgMjIgLTc1IDYw%0AIC03NWMzNCAwIDYxIDE4IDg1IDU5YzIwIDM0IDMzIDc1IDMzIDExN3pNMzI1%0AIC05MGMwIDQ2IC0zNiA3NCAtMTQzIDEwNyBjLTEzIDQgLTIzIDcgLTM0IDEx%0AYy05IDAgLTUxIC0zNCAtNjUgLTUyYy0xNSAtMTkgLTIwIC0zNSAtMjAgLTU4%0AYzAgLTcwIDQ3IC0xMDIgMTI3IC0xMDJjODEgMCAxMzUgNDMgMTM1IDk0WiI+%0APC9wYXRoPjxwYXRoIGlkPSJTVElYV0VCTUFJTi0yOCIgc3Ryb2tlLXdpZHRo%0APSIxMCIgZD0iTTMwNCAtMTYxbC0xMiAtMTZjLTE1OCA5MCAtMjQ0IDI1OSAt%0AMjQ0IDQyOWMwIDE4NSA4NyAzMjkgMjQ3IDQyNGw5IC0xNmMtMTM5IC0xMTkg%0ALTE3MCAtMjEyIC0xNzAgLTQwNWMwIC0xODYgMzAgLTI5OSAxNzAgLTQxNloi%0APjwvcGF0aD48cGF0aCBpZD0iU1RJWFdFQk1BSU5JLTZFIiBzdHJva2Utd2lk%0AdGg9IjEwIiBkPSJNNDYwIDExN2wxNCAtMTNjLTY4IC05MyAtOTMgLTExMyAt%0AMTQwIC0xMTNjLTI1IDAgLTQ3IDE2IC00NyA1NGMwIDEwIDIgMjMgMTYgNzVs%0ANDQgMTYyYzggMzEgMTQgNjcgMTQgNzljMCAxOCAtOSAyOSAtMjQgMjljLTQw%0AIDAgLTg1IC00OSAtMTQ4IC0xNDJjLTQ1IC02NyAtNTMgLTkwIC0xMDAgLTI0%0AOGgtNzVsOTYgMzUwYzEgNSAyIDExIDIgMTdjMCAyMCAtMTQgMjYgLTY1IDI3%0AdjE2YzgxIDE2IDEwOSAyMCAxNjIgMzFsNCAtMmwtNjcgLTIxOCBjMTAwIDE2%0AMCAxNjcgMjIwIDIzMSAyMjBjNDMgMCA2NSAtMjUgNjUgLTYxYzAgLTE4IC00%0AIC0zOSAtMTAgLTYwbC01NiAtMjAzYy0xMCAtMzYgLTE0IC01MyAtMTQgLTYx%0AYzAgLTkgNCAtMTggMTYgLTE4YzE0IDAgMzIgMTYgNjEgNTNjNyA4IDE0IDE3%0AIDIxIDI2WiI+PC9wYXRoPjxwYXRoIGlkPSJTVElYV0VCTUFJTi0yOSIgc3Ry%0Ab2tlLXdpZHRoPSIxMCIgZD0iTTI5IDY2MGwxMiAxNmMxNTMgLTkyIDI0NCAt%0AMjU5IDI0NCAtNDI5YzAgLTE4NSAtODggLTMyNyAtMjQ3IC00MjRsLTkgMTZj%0AMTQyIDExNyAxNzAgMjExIDE3MCA0MDVjMCAxODcgLTI1IDMwMiAtMTcwIDQx%0ANloiPjwvcGF0aD48cGF0aCBpZD0iU1RJWFdFQk1BSU4tMjkiIHN0cm9rZS13%0AaWR0aD0iMTAiIGQ9Ik0yOSA2NjBsMTIgMTZjMTUzIC05MiAyNDQgLTI1OSAy%0ANDQgLTQyOWMwIC0xODUgLTg4IC0zMjcgLTI0NyAtNDI0bC05IDE2YzE0MiAx%0AMTcgMTcwIDIxMSAxNzAgNDA1YzAgMTg3IC0yNSAzMDIgLTE3MCA0MTZaIj48%0AL3BhdGg+PC9kZWZzPjxnIHN0cm9rZT0iYmxhY2siIGZpbGw9ImJsYWNrIiBz%0AdHJva2Utd2lkdGg9IjAiIHRyYW5zZm9ybT0ibWF0cml4KDEgMCAwIC0xIDAg%0AMCkiPjx1c2UgaHJlZj0iI1NUSVhXRUJNQUlOSS00RiIgeGxpbms6aHJlZj0i%0AI1NUSVhXRUJNQUlOSS00RiI+PC91c2U+PHVzZSBocmVmPSIjU1RJWFdFQk1B%0ASU4tMjgiIHg9IjcyNyIgeT0iMCIgeGxpbms6aHJlZj0iI1NUSVhXRUJNQUlO%0ALTI4Ij48L3VzZT48dXNlIGhyZWY9IiNTVElYV0VCTUFJTkktNkMiIHg9IjEw%0ANjUiIHk9IjAiIHhsaW5rOmhyZWY9IiNTVElYV0VCTUFJTkktNkMiPjwvdXNl%0APjx1c2UgaHJlZj0iI1NUSVhXRUJNQUlOSS02RiIgeD0iMTM0OSIgeT0iMCIg%0AeGxpbms6aHJlZj0iI1NUSVhXRUJNQUlOSS02RiI+PC91c2U+PHVzZSBocmVm%0APSIjU1RJWFdFQk1BSU5JLTY3IiB4PSIxODU0IiB5PSIwIiB4bGluazpocmVm%0APSIjU1RJWFdFQk1BSU5JLTY3Ij48L3VzZT48dXNlIGhyZWY9IiNTVElYV0VC%0ATUFJTi0yOCIgeD0iMjM1OSIgeT0iMCIgeGxpbms6aHJlZj0iI1NUSVhXRUJN%0AQUlOLTI4Ij48L3VzZT48dXNlIGhyZWY9IiNTVElYV0VCTUFJTkktNkUiIHg9%0AIjI2OTciIHk9IjAiIHhsaW5rOmhyZWY9IiNTVElYV0VCTUFJTkktNkUiPjwv%0AdXNlPjx1c2UgaHJlZj0iI1NUSVhXRUJNQUlOLTI5IiB4PSIzMjAyIiB5PSIw%0AIiB4bGluazpocmVmPSIjU1RJWFdFQk1BSU4tMjkiPjwvdXNlPjx1c2UgaHJl%0AZj0iI1NUSVhXRUJNQUlOLTI5IiB4PSIzNTQwIiB5PSIwIiB4bGluazpocmVm%0APSIjU1RJWFdFQk1BSU4tMjkiPjwvdXNlPjwvZz48L3N2Zz4=%0A" alt="O(log(n))"> ce qui réduit drastiquement le problème.</p>
<p>C'est ce que propose la <a href="http://openjdk.java.net/jeps/180">JEP 180</a> et qui a été implémenté dans OpenJDK 8.</p>
<p>Refaisons tourner notre benchmark sur OpenJDK 8:</p>
<p><img src="//img.linuxfr.org/img/68747470733a2f2f7261772e67697468756275736572636f6e74656e742e636f6d2f756e706f7274616e742d74686f75676874732f3230313430355f4a45505f3138302f6d61737465722f4a45505f3138305f616e616c797369735f66696c65732f4a45505f3138305f616e616c797369735f32395f312e706e673f7261773d74727565/JEP_180_analysis_29_1.png?raw=true" alt="png" title="Source : https://raw.githubusercontent.com/unportant-thoughts/201405_JEP_180/master/JEP_180_analysis_files/JEP_180_analysis_29_1.png?raw=true"></p>
<p>Cette fois ci nous comparons le comportement normal d'OpenJDK 8 et Java 7u55 ainsi que le comportement d'OpenJDK8 avec des collisions.</p>
<p>Tout d'abord nous constatons que les performances dans le cas normal n'ont pas régressé. Ensuite nous voyons que contrairement à une solution qui vise a prévenir entièrement les collisions, l'utilisation d'arbre balancé a tout de même un coût. Les opérations passent de <img style="display: inline; max-height: 1em;" class="mathjax" src="data:image/svg+xml;base64,PHN2ZyB4bWxuczp4bGluaz0iaHR0cDovL3d3dy53My5vcmcvMTk5OS94bGlu%0AayIgc3R5bGU9IndpZHRoOiA0LjQyOWV4OyBoZWlnaHQ6IDIuMTQzZXg7IHZl%0AcnRpY2FsLWFsaWduOiAtMC41NzFleDsgbWFyZ2luLXRvcDogMXB4OyBtYXJn%0AaW4tcmlnaHQ6IDBweDsgbWFyZ2luLWJvdHRvbTogMXB4OyBtYXJnaW4tbGVm%0AdDogMHB4OyBwb3NpdGlvbjogc3RhdGljOyAiIHZpZXdCb3g9IjAgLTcwMi4y%0ANTgxMjMyNTUxNTQ5IDE5MDggOTA1LjUxNjI0NjUxMDMxIiB4bWxucz0iaHR0%0AcDovL3d3dy53My5vcmcvMjAwMC9zdmciPjxkZWZzIGlkPSJNYXRoSmF4X1NW%0AR19nbHlwaHMiPjxwYXRoIGlkPSJTVElYV0VCTUFJTkktNEYiIHN0cm9rZS13%0AaWR0aD0iMTAiIGQ9Ik02OTkgNDE4YzAgLTE0NiAtODggLTI4NSAtMjA3IC0z%0ANjVjLTY1IC00NCAtMTQwIC03MSAtMjE0IC03MWMtMTMwIDAgLTIxOCA4NSAt%0AMjE4IDIzNGMwIDEyMiA3MyAyNjIgMTc3IDM1M2M2OSA2MCAxNTIgOTcgMjM3%0AIDk3YzE0NCAxIDIyNSAtOTYgMjI1IC0yNDh6TTU5NCA0ODFjMCA5NCAtNDkg%0AMTUyIC0xMjkgMTUyYy03NCAwIC0xMzcgLTUxIC0xODYgLTExN2MtNzMgLTk5%0AIC0xMTQgLTIzMiAtMTE0IC0zMzIgYzAgLTEwOSA0NiAtMTY5IDEzMCAtMTY5%0AYzY3IDAgMTI0IDM5IDE3MCA5NWM4NCAxMDQgMTI5IDI2OSAxMjkgMzcxWiI+%0APC9wYXRoPjxwYXRoIGlkPSJTVElYV0VCTUFJTi0yOCIgc3Ryb2tlLXdpZHRo%0APSIxMCIgZD0iTTMwNCAtMTYxbC0xMiAtMTZjLTE1OCA5MCAtMjQ0IDI1OSAt%0AMjQ0IDQyOWMwIDE4NSA4NyAzMjkgMjQ3IDQyNGw5IC0xNmMtMTM5IC0xMTkg%0ALTE3MCAtMjEyIC0xNzAgLTQwNWMwIC0xODYgMzAgLTI5OSAxNzAgLTQxNloi%0APjwvcGF0aD48cGF0aCBpZD0iU1RJWFdFQk1BSU4tMzEiIHN0cm9rZS13aWR0%0AaD0iMTAiIGQ9Ik0zOTQgMGgtMjc2djE1Yzc0IDQgOTUgMjUgOTUgODB2NDQ5%0AYzAgMzQgLTkgNDkgLTMwIDQ5Yy0xMCAwIC0yNyAtNSAtNDUgLTEybC0yNyAt%0AMTB2MTRsMTc5IDkxbDkgLTN2LTU5N2MwIC00MyAyMCAtNjEgOTUgLTYxdi0x%0ANVoiPjwvcGF0aD48cGF0aCBpZD0iU1RJWFdFQk1BSU4tMjkiIHN0cm9rZS13%0AaWR0aD0iMTAiIGQ9Ik0yOSA2NjBsMTIgMTZjMTUzIC05MiAyNDQgLTI1OSAy%0ANDQgLTQyOWMwIC0xODUgLTg4IC0zMjcgLTI0NyAtNDI0bC05IDE2YzE0MiAx%0AMTcgMTcwIDIxMSAxNzAgNDA1YzAgMTg3IC0yNSAzMDIgLTE3MCA0MTZaIj48%0AL3BhdGg+PC9kZWZzPjxnIHN0cm9rZT0iYmxhY2siIGZpbGw9ImJsYWNrIiBz%0AdHJva2Utd2lkdGg9IjAiIHRyYW5zZm9ybT0ibWF0cml4KDEgMCAwIC0xIDAg%0AMCkiPjx1c2UgaHJlZj0iI1NUSVhXRUJNQUlOSS00RiIgeGxpbms6aHJlZj0i%0AI1NUSVhXRUJNQUlOSS00RiI+PC91c2U+PHVzZSBocmVmPSIjU1RJWFdFQk1B%0ASU4tMjgiIHg9IjcyNyIgeT0iMCIgeGxpbms6aHJlZj0iI1NUSVhXRUJNQUlO%0ALTI4Ij48L3VzZT48dXNlIGhyZWY9IiNTVElYV0VCTUFJTi0zMSIgeD0iMTA2%0ANSIgeT0iMCIgeGxpbms6aHJlZj0iI1NUSVhXRUJNQUlOLTMxIj48L3VzZT48%0AdXNlIGhyZWY9IiNTVElYV0VCTUFJTi0yOSIgeD0iMTU3MCIgeT0iMCIgeGxp%0Abms6aHJlZj0iI1NUSVhXRUJNQUlOLTI5Ij48L3VzZT48L2c+PC9zdmc+%0A" alt="O(1)"> à <img style="display: inline; max-height: 1em;" class="mathjax" src="data:image/svg+xml;base64,PHN2ZyB4bWxuczp4bGluaz0iaHR0cDovL3d3dy53My5vcmcvMTk5OS94bGlu%0AayIgc3R5bGU9IndpZHRoOiA5ZXg7IGhlaWdodDogMi4xNDNleDsgdmVydGlj%0AYWwtYWxpZ246IC0wLjU3MWV4OyBtYXJnaW4tdG9wOiAxcHg7IG1hcmdpbi1y%0AaWdodDogMHB4OyBtYXJnaW4tYm90dG9tOiAxcHg7IG1hcmdpbi1sZWZ0OiAw%0AcHg7IHBvc2l0aW9uOiBzdGF0aWM7ICIgdmlld0JveD0iMCAtNzA5LjI1ODEy%0AMzI1NTE1NDkgMzg3OCA5NDEuNTE2MjQ2NTEwMzEiIHhtbG5zPSJodHRwOi8v%0Ad3d3LnczLm9yZy8yMDAwL3N2ZyI+PGRlZnMgaWQ9Ik1hdGhKYXhfU1ZHX2ds%0AeXBocyI+PHBhdGggaWQ9IlNUSVhXRUJNQUlOSS00RiIgc3Ryb2tlLXdpZHRo%0APSIxMCIgZD0iTTY5OSA0MThjMCAtMTQ2IC04OCAtMjg1IC0yMDcgLTM2NWMt%0ANjUgLTQ0IC0xNDAgLTcxIC0yMTQgLTcxYy0xMzAgMCAtMjE4IDg1IC0yMTgg%0AMjM0YzAgMTIyIDczIDI2MiAxNzcgMzUzYzY5IDYwIDE1MiA5NyAyMzcgOTdj%0AMTQ0IDEgMjI1IC05NiAyMjUgLTI0OHpNNTk0IDQ4MWMwIDk0IC00OSAxNTIg%0ALTEyOSAxNTJjLTc0IDAgLTEzNyAtNTEgLTE4NiAtMTE3Yy03MyAtOTkgLTEx%0ANCAtMjMyIC0xMTQgLTMzMiBjMCAtMTA5IDQ2IC0xNjkgMTMwIC0xNjljNjcg%0AMCAxMjQgMzkgMTcwIDk1Yzg0IDEwNCAxMjkgMjY5IDEyOSAzNzFaIj48L3Bh%0AdGg+PHBhdGggaWQ9IlNUSVhXRUJNQUlOLTI4IiBzdHJva2Utd2lkdGg9IjEw%0AIiBkPSJNMzA0IC0xNjFsLTEyIC0xNmMtMTU4IDkwIC0yNDQgMjU5IC0yNDQg%0ANDI5YzAgMTg1IDg3IDMyOSAyNDcgNDI0bDkgLTE2Yy0xMzkgLTExOSAtMTcw%0AIC0yMTIgLTE3MCAtNDA1YzAgLTE4NiAzMCAtMjk5IDE3MCAtNDE2WiI+PC9w%0AYXRoPjxwYXRoIGlkPSJTVElYV0VCTUFJTkktNkMiIHN0cm9rZS13aWR0aD0i%0AMTAiIGQ9Ik0yNzkgNjc4bC0xNTMgLTU4NWMtNSAtMTggLTggLTM1IC04IC00%0AM2MwIC0xMiA3IC0xOCAxNyAtMThjMTUgMCAzOCAxNiA2NyA1N2wyNSAzNWwx%0ANCAtMTBjLTYwIC05NSAtOTcgLTEyNSAtMTUxIC0xMjVjLTMyIDAgLTQ5IDE5%0AIC00OSA1NmMwIDggMSAyMCA0IDMwbDEzNyA1MjRjMyAxMCAzIDE2IDMgMTlj%0AMCAxMiAtMTcgMjIgLTQ5IDIyaC0xOHYxNmM1OSA3IDk2IDE0IDE1NSAyN1oi%0APjwvcGF0aD48cGF0aCBpZD0iU1RJWFdFQk1BSU5JLTZGIiBzdHJva2Utd2lk%0AdGg9IjEwIiBkPSJNNDY4IDMwMWMwIC03NiAtNDAgLTE2NCAtMTA2IC0yMjlj%0ALTU4IC01OCAtMTIyIC04MyAtMTg4IC04M2MtOTQgMCAtMTQ3IDUyIC0xNDcg%0AMTM5YzAgMTEyIDc1IDIyNyAxODAgMjgzYzM5IDIxIDc5IDMwIDEyMCAzMGM4%0AMSAwIDE0MSAtNTIgMTQxIC0xNDB6TTM4NCAzMjZjMCA2MSAtMjggOTQgLTcx%0AIDk0Yy00NCAwIC04OCAtMzEgLTEyOCAtOTFjLTQ2IC03MCAtNzQgLTE0OSAt%0ANzQgLTIyOGMwIC02MCAzMSAtOTEgNzggLTkxIGM0NCAwIDgyIDI5IDEyMSA4%0AM2M0NiA2MyA3NCAxNTcgNzQgMjMzWiI+PC9wYXRoPjxwYXRoIGlkPSJTVElY%0AV0VCTUFJTkktNjciIHN0cm9rZS13aWR0aD0iMTAiIGQ9Ik00NzEgMzY2aC00%0AOWM5IC0xOCA5IC0zNCA5IC01MWMwIC04NCAtOTIgLTE2NCAtMTg1IC0xNjRj%0ALTExIDAgLTIyIDEgLTMxIDNjLTMgMSAtNSAxIC03IDFjLTE3IDAgLTM2IC0y%0AMCAtMzYgLTQxYzAgLTE4IDI3IC0zMSA3MSAtNDJjOTYgLTIzIDE0MiAtNjcg%0AMTQyIC0xMjdjMCAtODcgLTc3IC0xNTEgLTIxMCAtMTUxYy0xMDIgMCAtMTY3%0AIDM2IC0xNjcgMTA4YzAgNTEgMTkgNzggMTE3IDEzN2MtMTggMTEgLTI3IDI2%0AIC0yNyAzOSBjMCAyOSAyMyA1OSA3NyA4NGMtNTYgMjAgLTc5IDU2IC03OSAx%0AMDhjMCAxMDIgMTAwIDE3MSAyMDEgMTcxYzM4IDAgNzEgLTkgOTggLTI4Yzgg%0ALTYgMTMgLTggMTYgLThoNjB2LTM5ek0zNTIgMzQ4YzAgNTMgLTE5IDcxIC01%0ANiA3MWMtNjIgMCAtMTIyIC03MyAtMTIyIC0xNzJjMCAtNDcgMjIgLTc1IDYw%0AIC03NWMzNCAwIDYxIDE4IDg1IDU5YzIwIDM0IDMzIDc1IDMzIDExN3pNMzI1%0AIC05MGMwIDQ2IC0zNiA3NCAtMTQzIDEwNyBjLTEzIDQgLTIzIDcgLTM0IDEx%0AYy05IDAgLTUxIC0zNCAtNjUgLTUyYy0xNSAtMTkgLTIwIC0zNSAtMjAgLTU4%0AYzAgLTcwIDQ3IC0xMDIgMTI3IC0xMDJjODEgMCAxMzUgNDMgMTM1IDk0WiI+%0APC9wYXRoPjxwYXRoIGlkPSJTVElYV0VCTUFJTi0yOCIgc3Ryb2tlLXdpZHRo%0APSIxMCIgZD0iTTMwNCAtMTYxbC0xMiAtMTZjLTE1OCA5MCAtMjQ0IDI1OSAt%0AMjQ0IDQyOWMwIDE4NSA4NyAzMjkgMjQ3IDQyNGw5IC0xNmMtMTM5IC0xMTkg%0ALTE3MCAtMjEyIC0xNzAgLTQwNWMwIC0xODYgMzAgLTI5OSAxNzAgLTQxNloi%0APjwvcGF0aD48cGF0aCBpZD0iU1RJWFdFQk1BSU5JLTZFIiBzdHJva2Utd2lk%0AdGg9IjEwIiBkPSJNNDYwIDExN2wxNCAtMTNjLTY4IC05MyAtOTMgLTExMyAt%0AMTQwIC0xMTNjLTI1IDAgLTQ3IDE2IC00NyA1NGMwIDEwIDIgMjMgMTYgNzVs%0ANDQgMTYyYzggMzEgMTQgNjcgMTQgNzljMCAxOCAtOSAyOSAtMjQgMjljLTQw%0AIDAgLTg1IC00OSAtMTQ4IC0xNDJjLTQ1IC02NyAtNTMgLTkwIC0xMDAgLTI0%0AOGgtNzVsOTYgMzUwYzEgNSAyIDExIDIgMTdjMCAyMCAtMTQgMjYgLTY1IDI3%0AdjE2YzgxIDE2IDEwOSAyMCAxNjIgMzFsNCAtMmwtNjcgLTIxOCBjMTAwIDE2%0AMCAxNjcgMjIwIDIzMSAyMjBjNDMgMCA2NSAtMjUgNjUgLTYxYzAgLTE4IC00%0AIC0zOSAtMTAgLTYwbC01NiAtMjAzYy0xMCAtMzYgLTE0IC01MyAtMTQgLTYx%0AYzAgLTkgNCAtMTggMTYgLTE4YzE0IDAgMzIgMTYgNjEgNTNjNyA4IDE0IDE3%0AIDIxIDI2WiI+PC9wYXRoPjxwYXRoIGlkPSJTVElYV0VCTUFJTi0yOSIgc3Ry%0Ab2tlLXdpZHRoPSIxMCIgZD0iTTI5IDY2MGwxMiAxNmMxNTMgLTkyIDI0NCAt%0AMjU5IDI0NCAtNDI5YzAgLTE4NSAtODggLTMyNyAtMjQ3IC00MjRsLTkgMTZj%0AMTQyIDExNyAxNzAgMjExIDE3MCA0MDVjMCAxODcgLTI1IDMwMiAtMTcwIDQx%0ANloiPjwvcGF0aD48cGF0aCBpZD0iU1RJWFdFQk1BSU4tMjkiIHN0cm9rZS13%0AaWR0aD0iMTAiIGQ9Ik0yOSA2NjBsMTIgMTZjMTUzIC05MiAyNDQgLTI1OSAy%0ANDQgLTQyOWMwIC0xODUgLTg4IC0zMjcgLTI0NyAtNDI0bC05IDE2YzE0MiAx%0AMTcgMTcwIDIxMSAxNzAgNDA1YzAgMTg3IC0yNSAzMDIgLTE3MCA0MTZaIj48%0AL3BhdGg+PC9kZWZzPjxnIHN0cm9rZT0iYmxhY2siIGZpbGw9ImJsYWNrIiBz%0AdHJva2Utd2lkdGg9IjAiIHRyYW5zZm9ybT0ibWF0cml4KDEgMCAwIC0xIDAg%0AMCkiPjx1c2UgaHJlZj0iI1NUSVhXRUJNQUlOSS00RiIgeGxpbms6aHJlZj0i%0AI1NUSVhXRUJNQUlOSS00RiI+PC91c2U+PHVzZSBocmVmPSIjU1RJWFdFQk1B%0ASU4tMjgiIHg9IjcyNyIgeT0iMCIgeGxpbms6aHJlZj0iI1NUSVhXRUJNQUlO%0ALTI4Ij48L3VzZT48dXNlIGhyZWY9IiNTVElYV0VCTUFJTkktNkMiIHg9IjEw%0ANjUiIHk9IjAiIHhsaW5rOmhyZWY9IiNTVElYV0VCTUFJTkktNkMiPjwvdXNl%0APjx1c2UgaHJlZj0iI1NUSVhXRUJNQUlOSS02RiIgeD0iMTM0OSIgeT0iMCIg%0AeGxpbms6aHJlZj0iI1NUSVhXRUJNQUlOSS02RiI+PC91c2U+PHVzZSBocmVm%0APSIjU1RJWFdFQk1BSU5JLTY3IiB4PSIxODU0IiB5PSIwIiB4bGluazpocmVm%0APSIjU1RJWFdFQk1BSU5JLTY3Ij48L3VzZT48dXNlIGhyZWY9IiNTVElYV0VC%0ATUFJTi0yOCIgeD0iMjM1OSIgeT0iMCIgeGxpbms6aHJlZj0iI1NUSVhXRUJN%0AQUlOLTI4Ij48L3VzZT48dXNlIGhyZWY9IiNTVElYV0VCTUFJTkktNkUiIHg9%0AIjI2OTciIHk9IjAiIHhsaW5rOmhyZWY9IiNTVElYV0VCTUFJTkktNkUiPjwv%0AdXNlPjx1c2UgaHJlZj0iI1NUSVhXRUJNQUlOLTI5IiB4PSIzMjAyIiB5PSIw%0AIiB4bGluazpocmVmPSIjU1RJWFdFQk1BSU4tMjkiPjwvdXNlPjx1c2UgaHJl%0AZj0iI1NUSVhXRUJNQUlOLTI5IiB4PSIzNTQwIiB5PSIwIiB4bGluazpocmVm%0APSIjU1RJWFdFQk1BSU4tMjkiPjwvdXNlPjwvZz48L3N2Zz4=%0A" alt="O(log(n))">. Cependant si on regarde les chiffres ce n'est pas dramatique. À 20 000 éléments nous sommes maintenant à ~10ms plutôt que ~1ms loin de la seconde initiale.</p>
<p>Nous avons regardé le point de vue performance, cependant utiliser des arbres balancés a aussi un impact non négligeable sur la consommation mémoire. En effet au lieu d'avoir à stocker un bête pointeur sur l'élément suivant, on se retrouve avec quatre pointeurs et un booléen. Ce qui pourrait faire exploser la consommation mémoire. Cependant par défaut on utilise toujours une liste chaînée. Quand le nombre de collisions augmente dans une case et dépasse un seuil, on convertit tout ou une partie de la liste en arbre balancé pour optimiser le ratio consommation mémoire/performance. Cette technique est appliqué à chaque feuille de l'arbre. On démarre avec une liste, puis on convertit la feuille en arbre quand elle devient trop grande. Quand on supprime des éléments on peut rebasculer vers une liste chaînée. Les seuils de conversion étant respectivement à 8 et 6 éléments.</p>
<p>Si l'on observe la consommation mémoire avec <a href="http://openjdk.java.net/projects/code-tools/jol/">Jol</a> on peut voir que ça marche très bien:</p>
<p><img src="//img.linuxfr.org/img/68747470733a2f2f7261772e67697468756275736572636f6e74656e742e636f6d2f756e706f7274616e742d74686f75676874732f3230313430355f4a45505f3138302f6d61737465722f4a45505f3138305f616e616c797369735f66696c65732f4a45505f3138305f616e616c797369735f33315f312e706e673f7261773d74727565/JEP_180_analysis_31_1.png?raw=true" alt="png" title="Source : https://raw.githubusercontent.com/unportant-thoughts/201405_JEP_180/master/JEP_180_analysis_files/JEP_180_analysis_31_1.png?raw=true"></p>
<p>Ici on a fait attention à ce que les chaînes aient toujours la même taille dans les deux cas.</p>
<p>En pratique dans une utilisation courante avec une fonction de hachage correcte, les collisions seront rares et les arbres balancés ne seront jamais utilisés. Par contre quand ils rentrent en action cela permet d'éviter les DOS ou simplement d'avoir de bonnes performances quand la fonction <code>hashCode</code> de l'utilisateur est biaisée.</p>
<p>J'invite le lecteur intéressé à aller regarder <a href="http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/HashMap.java#l38">le code</a>. Le commentaire initial explique extrêmement clairement comment ça fonctionne et c'est plutôt rigolo à lire.</p>
<h3 id="conclusion">Conclusion</h3>
<p>L'approche d'OpenJDK 8 est intéressante et différente des autres plateformes puisqu'elle ne cherche pas à résoudre le problème des collisions mais à améliorer le pire cas. Changer de fonction de hachage pour les String étant compliqué on peut comprendre ce choix. Ils ont fait le pari que les performances offertes par les arbres balancés suffiront à se protéger et à offrir une bonne robustesse aux mauvaises fonctions de hachage. En pratique, au pire cas on observe un ralentissement constant de ~10x quelque soit la taille de la collection.</p>
<p>De l'autre côté beaucoup de plateformes ont changé de fonction de hachage pour éviter le pire cas mais n'ont pas chercher à l'améliorer et sont restés aux listes chainées. Ils se protègent donc des dénis de service selon les connaissances actuelles mais ne cherchent pas à se protéger pour le futur ni à offrir une réponse performante aux fonctions de hachage qui pourraient être légèrement biaisés pour certains autres type de données car implémentées par l'utilisateur.</p>
<p>Dans l'idéal les deux techniques devraient être appliquées mais je ne connais pas de plateforme qui le fasse. Et vous les outils que vous utilisez ils ont fait quoi ?</p>
<p>Voilà c'est un problème pas nouveau mais on en attendra certainement à nouveau parler. Dès qu'on lit une valeur du monde extérieur, celui-ci va s'arranger pour trouver un moyen de faire des choses "sympas". Les attaques algorithmiques permettent de varier un peu les plaisirs et forcent à s'interroger longuement à chaque fois qu'on stock une valeur que l'on ne contrôle pas.</p>
<p>Note: Tout le matériel créé pour écrire l'article est <a href="https://github.com/unportant-thoughts/201405_JEP_180">en ligne</a></p>
<p>NdM : <em>Le journal a été édité pour corriger plusieurs liens.</em></p><div><a href="https://linuxfr.org/users/cykl/journaux/openjdk-jep-180-hashmap-collisions-attaques-par-la-complexite.epub">Télécharger ce contenu au format EPUB</a></div> <p>
<strong>Commentaires :</strong>
<a href="//linuxfr.org/nodes/102078/comments.atom">voir le flux Atom</a>
<a href="https://linuxfr.org/users/cykl/journaux/openjdk-jep-180-hashmap-collisions-attaques-par-la-complexite#comments">ouvrir dans le navigateur</a>
</p>
ckylhttps://linuxfr.org/nodes/102078/comments.atomtag:linuxfr.org,2005:Diary/339532013-05-30T19:45:09+02:002013-05-30T19:45:09+02:00P=NP démontré ?Licence CC By‑SA http://creativecommons.org/licenses/by-sa/3.0/deed.fr<p>Xinwen Jiang a publié sur le site de la Cornell University un papier nommé «A Polynomial Time Algorithm for the Hamilton Circuit Problem» qui impliquerait que P=NP est vrai. </p>
<p>«In this paper, we introduce a so-called Multistage graph Simple Path (MSP) problem and show that the Hamilton Circuit (HC) problem can be polynomially reducible to the MSP problem. To solve the MSP problem, we propose a polynomial algorithm and prove its NP-completeness. Our result implies NP=P.»</p>
<p>Pour mémoire le lien wikipedia sur sur ce problème dont la résolution impliquerait quelques changements dans à peu près tous les domaines scientifiques : <a href="http://fr.wikipedia.org/wiki/Probl%C3%A8me_P_%3D_NP">http://fr.wikipedia.org/wiki/Probl%C3%A8me_P_%3D_NP</a> </p>
<p>Affaire à suivre, donc. Espérons qu'elle ait une autre fin que celle des neutrinos plus rapides que la lumière.</p><div><a href="https://linuxfr.org/users/finss/journaux/p-np-demontre.epub">Télécharger ce contenu au format EPUB</a></div> <p>
<strong>Commentaires :</strong>
<a href="//linuxfr.org/nodes/98488/comments.atom">voir le flux Atom</a>
<a href="https://linuxfr.org/users/finss/journaux/p-np-demontre#comments">ouvrir dans le navigateur</a>
</p>
finsshttps://linuxfr.org/nodes/98488/comments.atomtag:linuxfr.org,2005:News/289522011-12-30T20:42:47+01:002011-12-31T23:25:20+01:00Le colonel Moutarde, sur la table (de hachage), avec un livre de mathsLicence CC By‑SA http://creativecommons.org/licenses/by-sa/3.0/deed.fr<div><p>Quand des chercheurs en informatique font de la théorie, certains écoutent, comme les développeurs de Perl. D'autres dorment au fond de la classe : cette fois, le bonnet d'âne est pour PHP, Python, V8 (JavaScript par Google, qui sert par exemple dans node.js), Ruby (sauf CRuby), de nombreux serveurs d'applications en Java, mais aussi ASP.NET. Ils ont dû se réveiller brutalement mercredi, lors d'une <a href="http://events.ccc.de/congress/2011/Fahrplan/attachments/2007_28C3_Effective_DoS_on_web_application_platforms.pdf">présentation</a> d'Alexander Klink et Julian Wälde au Chaos Communication Congress montrant comment saturer très simplement un serveur grâce à une attaque basée sur la complexité algorithmique.</p></div><ul><li>lien nᵒ 1 : <a title="http://events.ccc.de/congress/2011/Fahrplan/attachments/2007_28C3_Effective_DoS_on_web_application_platforms.pdf" hreflang="fr" href="https://linuxfr.org/redirect/74514">Présentation d'Alexander Klink et Julian Wälde au Chaos Communication Congress [PDF, 6 Mo]</a></li></ul><div><h2 id="sommaire">Sommaire</h2>
<ul><li><a href="#toc_0">Ô ♫ mon ♬ tablo-o-o-oooooo ♩</a></li>
<li><a href="#toc_1">Un hacheur sachant hacher</a></li>
<li><a href="#toc_2">Un arrière-gout sucré</a></li>
<li><a href="#toc_3">What's in a name ?</a></li>
<li><a href="#toc_4">Savez-vous compter les trous ?</a></li>
<li><a href="#toc_5">Mais pourquoi est-il aussi méchant ?</a></li>
<li><a href="#toc_6">Dromadaire 1 – ânes 0</a></li>
<li><a href="#toc_7">Un grain de sel suffit</a></li>
<li><a href="#toc_8">En attendant…</a></li>
</ul><p>Le point commun entre tous ces logiciels : ils sont capables de recevoir par HTTP une requête accompagnée de variables et de leurs valeurs. Par exemple, lorsqu'on remplit un formulaire sur un site web, le navigateur envoie au serveur une variable nommée <strong>réponse</strong> avec la valeur <strong>42</strong>. C'est aussi ce qui sert à naviguer sur un site marchand ou un bouchot à trolls en restant identifié. Quand la requête arrive, il faut donc que chaque variable, accompagnée de sa valeur, soit disponible pour le programme qui va la traiter. Pratiquement tous les langages le font de la même façon : ils les insèrent dans une table de hachage.</p>
<h2 id="toc_0">Ô ♫ mon ♬ tablo-o-o-oooooo ♩</h2>
<p>
<em>[avertissement : ceux qui savent ce qu'est une table de hachage perdent leur temps s'ils lisent ce paragraphe. Bon, en même temps, ils sont déjà sur DLFP…]</em>
</p>
<p>Soit un langage de programmation dans lequel existent deux types de données : les nombres entiers et les chaînes de caractères. En combinant les deux, il est possible de construire un tableau dans lequel chaque case, numérotée, contient une chaîne de caractères.</p>
<p>1 → « Victorine continua sa lecture en fermant les yeux »<br />
2 → « La vache paît en paix dans ces gras pâturages »<br />
3 → « Ah ! dit don Manoel en portugais »</p>
<h2 id="toc_1">Un hacheur sachant hacher</h2>
<p>C'est pratique, mais malheureusement, les variables que l'on utilise sur des pages web sont nommées, pas numérotées. Le nom d'une variable est lui-même une chaîne de caractères. Il faudrait donc une méthode qui transforme une chaîne en entier, c'est-à-dire une fonction de hachage. Pour une chaîne c donnée, la fonction de hachage h renvoie un entier n : h(c)=n.</p>
<p>Ainsi, on a une façon bien pratique d'enregistrer les variables : on se donne une fonction de hachage et un tableau comme ci-dessus, que l'on nomme table de hachage, et on range les chaines à l'emplacement correspondant à leur image par la fonction de hachage. Par exemple, si on a une variable nommée question et contenant « six fois neuf », on calcule h(« question »)=42, et on enregistre donc la chaîne « six fois neuf » dans l'emplacement numéro 42 du tableau.</p>
<h2 id="toc_2">Un arrière-gout sucré</h2>
<p>À ce stade, le programme n'a pas encore la main. Cette étape préparatoire va servir par la suite, cachée sous une couche de sucre syntaxique. Par exemple, si le programmeur demande la valeur de POST['question'], l'environnement d'exécution va calculer h(« question »)=42 et aller chercher le contenu de la case numéro 42.</p>
<h2 id="toc_3">What's in a name ?</h2>
<p>Il y a tout de même un problème. Oh, un tout petit problème, un de ceux qui ne se posent qu'en théorie, jamais en pratique. Le nombre de seaux (« cases » du tableau) est nécessairement limité, contrairement au nombre de chaînes de caractères qu'il est possible de construire. Il existe donc forcément, pour une fonction h et une chaîne c1 données, une chaîne c2 telle que h(c1) = h(c2) = n. On dit alors que c2 est un <em>deuxième antécédent</em> de n par h, et qu'une <em>collision</em> se produit entre c1 et c2. Dans ce cas, comme une case ne peut accueillir qu'une chaîne, il faut recourir à une astuce : chaque case, en plus d'une chaîne, contient aussi l'adresse d'une nouvelle case. On peut ainsi chaîner les valeurs sans limite autre que la mémoire de la machine.</p>
<p>41 → « foo »<br />
42 → « A noir » → « E blanc » → « I rouge » → « O bleu » → « U vert » → « Voyelles »</p>
<h2 id="toc_4">Savez-vous compter les trous ?</h2>
<p>Insérer dans une case numérotée ou dans une liste chaînée, c'est la même chose. Sans doute… Sauf pour les quelques farfelus qui comptent les opérations nécessaires à l'exécution d'un programme en fonction de la taille de ses données d'entrée. C'est ce qu'on appelle la <em>complexité algorithmique</em>.</p>
<p>Dans le cas de l'insertion d'une valeur c dans une table de hachage, si on tombe toujours sur une case vide, ce nombre d'opérations ne dépend que du nombre d'opérations que va mettre la fonction de hachage pour calculer sa valeur. Pour une fonction de hachage classique, le temps d'une insertion est donc proportionnel à la longueur de c, ce que l'on note O(|c|). Comme les bonnes fonctions de hachage sont très rapides, cela ne pose pas de problème. Pour une application web, en pratique, la longueur des données à hacher sera forcément très faible, et on peut donc considérer (bouchez-vous les oreilles si un puriste est dans les environs : il va hurler) que ce temps est une constante. Pour insérer n éléments, il faut donc O(n) opérations. À la grosse louche, si l'insertion d'un élément prend 0,0000001 seconde, l'insertion de 10000 éléments prend 0,001 seconde et celle de 100000 éléments prend 0,01 seconde. Une paille.</p>
<p>En revanche, si la case choisie est toujours déjà occupée, c'est une toute autre histoire. En effet, il faut alors parcourir la liste des données insérées pour trouver la place de la nouvelle chaine, qui peut très bien être à la fin (si elles sont triées, ce qui est généralement le cas). On tombe alors dans le pire cas : l'insertion de n éléments qui ont la même image par h nécessite O(n²) opérations. Si l'insertion d'un élément prend toujours 0,0000001 seconde, l'insertion de 10 000 éléments prend désormais 10 secondes et celle de 100 000 éléments prend 1000 secondes. Il y a peu de chances que l'utilisateur soit toujours en train d'attendre, un quart d'heure après avoir envoyé ses données.</p>
<p>Heureusement, en pratique, il est très rare de tomber sur une case occupée. Les développeurs des principaux environnements d'exécution sont compétents et ont donc choisi de très bonnes fonctions de hachage, souvent issues des travaux du mathématicien américain <a href="http://cr.yp.to/djb.html">Daniel Bernstein</a>, un expert en cryptologie. Grâce à cela, il est extrêmement difficile de trouver plusieurs chaines de caractères qui ont le même antécédent. On peut donc oublier ce scénario pathologique certes, complètement théorique toutefois.</p>
<h2 id="toc_5">Mais pourquoi est-il aussi méchant ?</h2>
<p>Sauf, bien sûr, si on dispose d'une attaque contre ces fonctions de hachage. Une telle attaque est à la base des travaux de Klink et Wälde. En résumé, ils ont trouvé un moyen de fabriquer un grand nombre de chaines de caractères qui ont la même image par les fonctions de hachage utilisées par les bibliothèques des principaux langages. Ils peuvent ainsi construire une requête HTTP contenant un grand nombre de variables nommées exprès pour provoquer le scénario pathologique décrit ci-dessus : occupation à 100% du processeur dédié à cette tâche.</p>
<h2 id="toc_6">Dromadaire 1 – ânes 0</h2>
<p>Ce genre d'attaque ne date pourtant pas d'hier, du moins en théorie. Un <a href="http://www.cs.rice.edu/~scrosby/hash/CrosbyWallach_UsenixSec2003.pdf">article de Crosby et Wallach</a> paru en 2003 décrit le problème et apporte des solutions. Les développeurs de Perl ont réagi dans la foulée en modifiant légèrement leur fonction de hachage, ceux de CRuby également, et… c'est à peu près tout. Pratiquement tous les autres langages largement déployés sur des serveurs sont toujours vulnérables.</p>
<h2 id="toc_7">Un grain de sel suffit</h2>
<p>La solution est évidente : l'attaquant ne doit pas être capable de prévoir le résultat de la fonction de hachage. Comment est-ce possible si le code source des logiciels déployés est public ? Simplement en modifiant la fonction de hachage pour intégrer un élément de hasard, sur le même principe que le salage des mots de passe. En général, la méthode employée pour hacher consiste à prendre un entier valant initialement 0, puis modifier cet entier en fonction des données à hacher, caractère par caractère. Dans les versions actuelles de Perl, cet entier ne vaut plus initialement 0, mais une valeur aléatoire qui ne sort jamais de l'environnement d'exécution. Résultat : les collisions sont pratiquement impossibles à trouver, et paf l'attaque.</p>
<h2 id="toc_8">En attendant…</h2>
<p>Quelques mesures simples protègent efficacement contre ce genre d'attaque, mais il n'est pas toujours facile, voire pas toujours possible, de les mettre en place. On peut limiter la taille maximale d'une requête, mais c'est ballot si l'utilisateur est censé pouvoir envoyer beaucoup de données. Plus fin : on peut limiter le nombre maximum de variables, notamment avec Suhosin pour PHP. En tous cas, maintenant que le 25 décembre est passé, il est temps d'arrêter de croire au père Noël : le choix d'une structure de données et des fonctions associées est toujours important.</p></div><div><a href="https://linuxfr.org/news/le-colonel-moutarde-sur-la-table-de-hachage-avec-un-livre-de-maths.epub">Télécharger ce contenu au format EPUB</a></div> <p>
<strong>Commentaires :</strong>
<a href="//linuxfr.org/nodes/88844/comments.atom">voir le flux Atom</a>
<a href="https://linuxfr.org/news/le-colonel-moutarde-sur-la-table-de-hachage-avec-un-livre-de-maths#comments">ouvrir dans le navigateur</a>
</p>
ɹǝıʌıʃObaud123claudexBenoît Sibaudpatrick_ghttps://linuxfr.org/nodes/88844/comments.atom