Note: This article was first written for linuxfr, which is a french speaking website. I decided to publish it here too, but being lazy, err busy, I never took the time translate it.
Dans cet article, je vais parler de la JEP 180 d'OpenJDK 8 qui propose une solution intéressante aux problèmes d'attaques sur la complexité que rencontrent les tables de hachage.
On a déjà parlé de ce sujet ici même à plusieurs reprises. 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.
Présentation des tables de hachage
Une table de hachage est une implémentation du type abstrait tableau associatif. Un tableau associatif 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.
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é $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 …