What is a collision? How was it resolved in the old map and how in the new one?

A collision in the context of hash tables is a situation where two different keys have the same hash value and attempt to occupy the same cell in the array.

In the old implementation of map in Go, collisions were resolved using linked lists (chaining). When a collision occurred, new elements were added to the linked list associated with the array cell.

In the new implementation (starting from Go 1.8), a more complex mechanism is used: instead of a simple linked list, a structure of arrays with open addressing and additional optimizations, such as using multiple hashes and transitioning to a tree when there are many collisions, is employed. This improves performance and reduces the likelihood of degradation to O(n).

A simplified example:

// old map: bucket -> linked list
// new map: bucket -> array + optimizations