How quickly can an element be found when searching by index in a slice and in a map?

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

• Slice: Accessing by index is a direct memory access by offset.

  Time complexity: O(1) – constant time. Access does not depend on the size of the slice.

  // Example of index access 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. Access by key involves computing the hash value of the key and then accessing the corresponding hash table bucket.

  Average time complexity: O(1) – constant time. With uniform hash distribution, access is fast.

  Worst-case time complexity: O(n) – linear time. This can occur in case of hash collisions, where a linked list or other structure in the bucket must be traversed. In practice, this is rare with a good hash function.

  // Example of key access in a map
  myMap := map[string]int{"one": 1, "two": 2, "three": 3}
  value, ok := myMap["two"] // Accessing value by key "two"
  // '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 index access in a slice guarantees O(1) in all cases, while for a map, there is a theoretical (but rare in practice) worst case of O(n).