How are collisions resolved in Go (up to version 1.24) in maps? Tell me about buckets and overflow buckets.

In Go (up to version 1.24), a hash table with buckets is used to implement a map, where each bucket contains multiple slots for key-value pairs.

Collisions occur when different keys have the same hash and fall into the same bucket. To resolve collisions, Go uses:

• Buckets: fixed size (usually 8 slots), where key-value pairs are stored.
• If all slots in a bucket are occupied and a new pair needs to be added, an overflow bucket is created — an additional bucket linked to the main one, expanding storage space.

Thus, when a collision occurs, Go does not use chains or lists but adds overflow buckets, forming a chain of buckets. When searching for a key, it first checks the slots in the main bucket, then the overflow buckets along the chain.

This allows efficient storage and lookup of elements, maintaining good performance even in case of collisions.

The structure roughly looks like this:

Bucket -> Overflow Bucket -> Overflow Bucket -> ...

Each bucket contains arrays of keys and values, as well as metadata for quick searching.