À quelle vitesse peut-on trouver un élément en recherchant par index dans une tranche et dans une carte?

La recherche d’un élément par index dans une tranche ([]) et par clé dans une carte (map) en Go a des complexités temporelles différentes.

• Tranche (slice): La recherche par index est un accès direct à l’élément en mémoire par son décalage.

  Complexité temporelle : O(1) – temps constant. L’accès à l’élément ne dépend pas de la taille de la tranche.

  // Exemple d’accès par index dans une tranche
  mySlice := []int{1, 2, 3, 4, 5}
  element := mySlice[2] // Accès à l’élément avec l’index 2 (valeur 3)
  

• Carte (map): La carte est implémentée comme une table de hachage. La recherche par clé implique de calculer la valeur de hachage de la clé, puis d’accéder à la cellule correspondante dans la table de hachage.

  Complexité temporelle en moyenne : O(1) – temps constant. Avec une distribution uniforme des hachages, l’accès est rapide.

  Complexité temporelle dans le pire cas : O(n) – temps linéaire. Cela peut se produire en cas de fortes collisions de hachages, lorsque l’on doit parcourir une liste chaînée ou un autre arbre dans la cellule de la table de hachage. En pratique, cela est rare avec une bonne fonction de hachage.

  // Exemple d’accès par clé dans une carte
  myMap := map[string]int{"one": 1, "two": 2, "three": 3}
  value, ok := myMap["two"] // Accès à la valeur avec la clé "two"
  // La variable 'value' contiendra 2, 'ok' sera true
  

Comparaison :

Structure de données	Accès par	Complexité temporelle (moyenne)	Complexité temporelle (pire cas)
Tranche	Index	O(1)	O(1)
Carte	Clé (table de hachage)	O(1)	O(n)

Ainsi, dans des cas typiques, la recherche par index dans une tranche et par clé dans une carte est très rapide avec une complexité constante. Cependant, seul l’accès par index dans une tranche garantit O(1) dans tous les cas, tandis que pour la carte, il existe un cas théorique (mais rare en pratique) de O(n).