Tagged with hashmap

OpenJDK JEP 180: HashMap vs collisions

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 ...

read full article
Tagged , , ,