Kui kiiresti saab leida elementi, otsides indeksiga lõigus ja kaardil (map)?

In Go, searching for an element by index in a slice ([]) and by key in a map (map) has different time complexities.

• Slice: Accessing by index — this is direct memory access based on its offset.

  Time complexity: O(1) — constant time. Access to an element does not depend on the size of the slice.

  // Example of access by index in a slice
  mySlice := []int{1, 2, 3, 4, 5}
  element := mySlice[2] // Accessing element at index 2 (value 3)
  

• Map: Implemented as a hash table. Searching by key involves computing the hash value of the key and then accessing the corresponding cell in the hash table.

  Average time complexity: O(1) — constant time. If hashes are evenly distributed, access is fast.

  Worst-case time complexity: O(n) — linear time. This can occur in case of hash collisions, requiring traversal of a linked list or another structure in the cell.

  // Example of access by key in a map
  myMap := map[string]int{"one": 1, "two": 2, "three": 3}
  value, ok := myMap["two"] // Accessing value by key "two"
  // Variable 'value' will contain 2, 'ok' will be true
  

Comparison:

Data structure	Access by	Average time complexity	Worst-case time complexity
Slice	Index	O(1)	O(1)
Map	Key (hash table)	O(1)	O(n)

Thus, in typical cases, searching by index in a slice and by key in a map is very fast with constant time complexity. However, only access by index in a slice guarantees O(1) in all cases, while for a map, the worst-case O(n) is theoretical (but rarely occurs in practice).