Structures de données avancée
TBD à refaire bien propre.
TBD voir si toutes les structures de https://www.youtube.com/watch?v=6fnmXX8RK0s y sont.
Complexité amortie
TBD
Listes circulaires
liste circulaires ? Trouver le début.
Structures arborées
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 !