Новая реализация map в Go (SwissTable) — как работает, как решаются коллизии?

Новая реализация map в Go, известная как SwissTable, основана на идеях из библиотеки Abseil от Google и использует хеш-таблицу с открытой адресацией и улучшенным управлением коллизиями.

Основные особенности:

• Хеширование и хранение метаданных: Вместо хранения полного хеша ключа, хранится только часть (тэг) для ускорения поиска.
• Группы слотов: Ячейки таблицы организованы в группы фиксированного размера (например, 8), что позволяет эффективно использовать SIMD-инструкции для быстрого сравнения тегов.
• Коллизии: При коллизиях используется метод открытой адресации с линейным или квадратичным пробированием внутри группы, а при переполнении — расширение таблицы.
• Удаление: Используются специальные маркеры для удалённых элементов, чтобы не нарушать цепочки поиска.

Таким образом, SwissTable повышает производительность за счёт оптимизации кеша и уменьшения количества сравнений при поиске и вставке, а коллизии решаются через эффективное пробирование внутри групп слотов.