Ответ
Открытая адресация (open addressing) — это метод разрешения коллизий в хеш-таблицах. Его суть в том, что при возникновении коллизии (когда хеш-функция указывает на уже занятую ячейку) новый элемент помещается в другую свободную ячейку этой же таблицы, найденную по определенному правилу.
Основные стратегии поиска свободной ячейки (пробирования):
- Линейное пробирование: Последовательно проверяются ячейки
(hash(key) + i) % size. - Квадратичное пробирование: Проверяются ячейки
(hash(key) + i²) % size. - Двойное хеширование: Используется вторая хеш-функция:
(hash1(key) + i * hash2(key)) % size.
Важный момент: Стандартная реализация map в Go не использует открытую адресацию. Вместо этого Go применяет метод цепочек (chaining). Каждая ячейка (bucket) в хеш-таблице Go может хранить до 8 пар ключ-значение. Если бакет переполняется, создается дополнительный бакет (overflow bucket), и он связывается с основным.
Пример реализации хеш-таблицы с открытой адресацией на Go (для иллюстрации концепции):
// Этот код демонстрирует концепцию и не является реализацией map в Go
type OpenAddrMap struct {
keys []string
values []int
size int
}
func (m *OpenAddrMap) Set(key string, value int) {
// Упрощенный хеш для примера
idx := int(key[0]) % m.size
// Линейное пробирование для поиска свободной ячейки
for m.keys[idx] != "" && m.keys[idx] != key {
idx = (idx + 1) % m.size
}
m.keys[idx] = key
m.values[idx] = value
}Преимущества открытой адресации:
- Лучшая производительность из-за локальности кэша (все данные хранятся в одном массиве).
- Отсутствие накладных расходов на хранение указателей на списки или другие структуры.
Недостатки:
- Производительность сильно деградирует при высоком коэффициенте заполнения (load factor).
- Сложность при удалении элементов (требуется помечать ячейки как удаленные, а не просто очищать).