En fait lorsque j'ai lu ton journal (avec intérêt, même si je ne suis pas développeur Java pour deux sous), j'ai été très étonné de voir que la technique de la liste chaînée était utilisée, plutôt que le hachage ouvert pour les tableaux associatifs. Dans tous les cas, entre arbre équilibré (type rouge-noir ou AVL) et table à hachage ouvert, on se retrouve avec une complexité amortie de O(n log n), alors qu'avec une table + liste chaînée, on dépend « bien plus » d'une bonne fonction de hachage : dans le cas de l'adressage ouvert, il faut doubler la taille de la table et re-hacher les valeurs pour les réinsérer dans la table, ce qui fait qu'une attaque sur les collisions ne devrait avoir qu'un impact limité. Ceci dit je me trompe peut-être (je suis loin d'être un expert en algorithmique).
[^] # Re: Python
Posté par lasher . En réponse à la dépêche OpenJDK JEP 180: HashMap, collisions & attaques par la complexité. Évalué à 2.
En fait lorsque j'ai lu ton journal (avec intérêt, même si je ne suis pas développeur Java pour deux sous), j'ai été très étonné de voir que la technique de la liste chaînée était utilisée, plutôt que le hachage ouvert pour les tableaux associatifs. Dans tous les cas, entre arbre équilibré (type rouge-noir ou AVL) et table à hachage ouvert, on se retrouve avec une complexité amortie de O(n log n), alors qu'avec une table + liste chaînée, on dépend « bien plus » d'une bonne fonction de hachage : dans le cas de l'adressage ouvert, il faut doubler la taille de la table et re-hacher les valeurs pour les réinsérer dans la table, ce qui fait qu'une attaque sur les collisions ne devrait avoir qu'un impact limité. Ceci dit je me trompe peut-être (je suis loin d'être un expert en algorithmique).