Quanto velocemente si può trovare un elemento cercando per indice in un segmento e in una mappa?

La ricerca di un elemento per indice in una slice ([]) e per chiave in una mappa (map) in Go ha diverse complessità temporali.

• Slice: La ricerca per indice è un accesso diretto all’elemento in memoria tramite il suo offset.

  Complessità temporale: O(1) – tempo costante. L’accesso all’elemento non dipende dalla dimensione della slice.

  // Esempio di accesso per indice in una slice
  mySlice := []int{1, 2, 3, 4, 5}
  element := mySlice[2] // Accesso all’elemento con indice 2 (valore 3)
  

• Mappa (map): La mappa è implementata come una tabella hash. La ricerca per chiave implica calcolare il valore hash della chiave e poi accedere alla cella corrispondente nella tabella hash.

  Complessità temporale media: O(1) – tempo costante. Con una distribuzione uniforme degli hash, l’accesso è rapido.

  Complessità temporale nel caso peggiore: O(n) – tempo lineare. Questo può accadere in caso di forti collisioni di hash, quando è necessario attraversare una lista collegata o un altro albero nella cella della tabella hash. In pratica, ciò è raro con una buona funzione hash.

  // Esempio di accesso per chiave in una mappa
  myMap := map[string]int{"one": 1, "two": 2, "three": 3}
  value, ok := myMap["two"] // Accesso al valore con chiave "two"
  // La variabile 'value' conterrà 2, 'ok' sarà true
  

Confronto:

Struttura dati	Accesso tramite	Complessità temporale media	Complessità temporale nel peggiore caso
Slice	Indice	O(1)	O(1)
Mappa	Chiave (tabella hash)	O(1)	O(n)

In modo simile, nei casi tipici, la ricerca per indice in una slice e per chiave in una mappa avviene molto rapidamente con complessità costante. Tuttavia, solo l’accesso per indice in una slice garantisce O(1) in ogni caso, mentre per la mappa esiste un caso teorico (ma raro nella pratica) di O(n).