Structures de données avancée
TBD : Knuth dancing links https://www.youtube.com/watch?v=_cR9zDlvP88 avec pointeurs
hash 2.0 améliorations
- hash :
- open addressing
- perfect
- universal
Hash universel
Pour que notre structure de dictionnaire soit de complexité $\mathcal{O}(1)$ en moyenne, on a supposé que nos fonction de hachage étaient utiles : les probabilités sont uniformes si les clés sont choisies aléatoirement.
Cette hypothèse est cependant tres rarement vérifiée en pratique, les clés ont souvent quelque chose en commun (numéro de téléphones, noms d'utilisateurs, etc). Pour palier ce problème épineux on renverse le problème et plutôt que de choisir des clés aléatoire, on choisi aléatoirement une fonction de hash !