Struture de données Flashcards
Aperçu sur les structures de donnée en algorithmique (10 cards)
Qu’est-ce qu’une hashmap ?
Une structure de données qui stocke des paires clé-valeur et permet un accès rapide via une fonction de hachage.
Quelle est la complexité moyenne d’accès à une valeur dans une hashmap ?
O(1) en moyenne, grâce au hachage direct.
À quoi sert la fonction de hachage dans une hashmap ?
À transformer une clé en un index dans le tableau sous-jacent de la hashmap.
C’est quoi une collision dans une hashmap ?
Quand deux clés différentes ont le même index après passage dans la fonction de hachage.
Qu’est-ce que le chaînage ?
Une méthode pour gérer les collisions en stockant plusieurs paires clé-valeur dans une liste à un même index.
Quelle est la complexité temporelle dans le pire cas si beaucoup de collisions ?
O(n)O(n), car on doit parcourir une liste de tous les éléments à cet index.
Qu’est-ce qu’une fonction de hachage parfaite ?
Une fonction qui génère des index uniques pour chaque clé, sans collision.
Peut-on avoir une fonction de hachage parfaite en pratique ?
Oui, mais seulement si on connaît toutes les clés à l’avance. Sinon, c’est quasi impossible.
Quels sont les risques si la fonction de hachage est mauvaise ?
Trop de collisions, ralentissement des performances, complexité proche de O(n).
Quelles stratégies permettent de garder de bonnes performances avec une hashmap ?
Utiliser une bonne fonction de hachage
Éviter un taux de remplissage trop élevé
Redimensionner la table quand elle devient trop pleine
