Объясните принцип открытой адресации в реализации ассоциативных контейнеров типа map.

Открытая адресация — это метод разрешения коллизий в хеш-таблицах, таких как map. При добавлении пары ключ-значение, если вычисленный хеш указывает на занятую ячейку, поиск свободной ячейки происходит внутри массива по определённой последовательности (например, линейное или квадратичное пробирование).

Вместо использования связных списков для коллизий (цепочек), открытая адресация хранит все элементы внутри одного массива, последовательно проверяя соседние позиции до нахождения пустой.

Пример линейного пробирования:

// hash - функция хеширования
// table - массив для хранения элементов
// i - номер попытки
index := (hash(key) + i) % len(table)

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