Jak rychle lze najít prvek, pokud hledáte podle indexu v řezu a v mapě?

Hledání prvku podle indexu v řezu ([]) a podle klíče v mapě (map) v Go má odlišnou časovou složitost.

• Řez (slice): Vyhledávání podle indexu je přímý přístup k prvku v paměti podle jeho posunu.

  Časová složitost: O(1) – konstantní čas. Přístup k prvku nezávisí na velikosti řezu.

  // Příklad přístupu podle indexu v řezu
  mySlice := []int{1, 2, 3, 4, 5}
  element := mySlice[2] // Přístup k prvku s indexem 2 (hodnota 3)
  

• Mapa (map): Mapa je implementována jako hash tabulka. Vyhledávání podle klíče zahrnuje výpočet hashové hodnoty klíče a následný přístup k odpovídající buňce v hash tabulce.

  Průměrná časová složitost: O(1) – konstantní čas. Při rovnoměrném rozložení hashů je přístup rychlý.

  Nejhorší případ: O(n) – lineární čas. To se může stát při silných kolizích hashů, kdy je třeba prohledat spojový seznam nebo jiné stromové struktury v buňce hash tabulky. V praxi je to vzácné s dobrými hash funkcemi.

  // Příklad přístupu podle klíče v mapě
  myMap := map[string]int{"one": 1, "two": 2, "three": 3}
  value, ok := myMap["two"] // Přístup k hodnotě podle klíče "two"
  // Proměnná 'value' bude obsahovat 2, 'ok' bude true
  

Porovnání:

Datová struktura	Přístup přes	Průměrná časová složitost	Nejhorší případ časové složitosti
Řez	Index	O(1)	O(1)
Mapa	Klíč (hash tabulka)	O(1)	O(n)

Tímto způsobem je v typických případech hledání podle indexu v řezu a podle klíče v mapě velmi rychlé s konstantní časovou složitostí. Nicméně, pouze přístup podle indexu v řezu garantuje O(1) za všech okolností, zatímco u mapy existuje teoretický (ale v praxi vzácný) případ O(n).