How does the new map implementation in Go (SwissTable) work, and how are collisions resolved?

The new implementation of map in Go, known as SwissTable, is based on ideas from Google's Abseil library and uses an open-addressing hash table with improved collision management.

Main features:

• Hashing and metadata storage: Instead of storing the full hash of the key, only a part (tag) is stored to speed up searches.
• Slot groups: Table cells are organized into fixed-size groups (e.g., 8), which allows efficient use of SIMD instructions for quick tag comparison.
• Collisions: Open addressing with linear or quadratic probing within a group is used for collisions, and table expansion is employed when full.
• Deletion: Special markers are used for deleted elements to avoid breaking search chains.

Thus, SwissTable improves performance by optimizing cache usage and reducing the number of comparisons during search and insertion, with collisions handled through efficient probing within slot groups.