Une solution alternative explore par Lucas De Marchi ingenieur chez Intel ( http://www.politreco.com/ ). En gros, au lieu d'avoir une structure simple derriere la table de hash, on fait appel a une structure un peu plus complexe qui permet de diminuer l'impact d'une collision. En passant a du O(log n) dans le pire cas.
Avec des donnees reelles, on se rend compte que dans ce cas, on peut utiliser une fonction de hash de type CRC32 qui va generer des collisions a foison, et obtenir de meilleur performance sur des cas reelles sans risque de faiblesse de la fonction de hash. De plus, CRC32 pouvant etre accelere en hardware, on se retrouve avec de plus un meilleur temps constant que les fonctions plus complexe.
Qt et la glib ont ete impacte par ce bug des tables de hash, il y a un peu plus d'un an. Leur solution a ete de rajouter un seed random pris au demarrage de l'application. Les EFL utilisaient deja une structure complexe (combine de rbtree et hash) et n'ont pas impacte (Ce qui a lance la reflection sur une fonction de hashage plus simple et rapide).
# Solution alternative
Posté par cedric . En réponse au journal OpenJDK JEP 180: HashMap, collisions & attaques par la complexité. Évalué à -1.
Une solution alternative explore par Lucas De Marchi ingenieur chez Intel ( http://www.politreco.com/ ). En gros, au lieu d'avoir une structure simple derriere la table de hash, on fait appel a une structure un peu plus complexe qui permet de diminuer l'impact d'une collision. En passant a du O(log n) dans le pire cas.
Avec des donnees reelles, on se rend compte que dans ce cas, on peut utiliser une fonction de hash de type CRC32 qui va generer des collisions a foison, et obtenir de meilleur performance sur des cas reelles sans risque de faiblesse de la fonction de hash. De plus, CRC32 pouvant etre accelere en hardware, on se retrouve avec de plus un meilleur temps constant que les fonctions plus complexe.
Qt et la glib ont ete impacte par ce bug des tables de hash, il y a un peu plus d'un an. Leur solution a ete de rajouter un seed random pris au demarrage de l'application. Les EFL utilisaient deja une structure complexe (combine de rbtree et hash) et n'ont pas impacte (Ce qui a lance la reflection sur une fonction de hashage plus simple et rapide).