Что такое коллизия? Как она разрешалась в старой map и как в новой?

Коллизия в контексте хеш-таблиц — это ситуация, когда два разных ключа имеют одинаковое значение хеша и пытаются занять одну и ту же ячейку в массиве.

В старой реализации map в Go коллизии разрешались с помощью связных списков (chaining). При коллизии новые элементы добавлялись в связный список, связанный с ячейкой массива.

В новой реализации (начиная с Go 1.8) используется более сложный механизм: вместо простого связного списка применяется структура из массивов с открытой адресацией и дополнительными оптимизациями, такими как использование нескольких хешей и переход на дерево при большом числе коллизий, что улучшает производительность и уменьшает вероятность деградации до O(n).

Пример упрощённо:

// старая map: bucket -> linked list
// новая map: bucket -> array + оптимизации