Расскажи о хэш-таблицах и их основном принципе работы.

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

Основной принцип работы:

1. Хеширование: Для каждого ключа вычисляется хеш-код — числовое значение фиксированного размера с помощью хеш-функции. Хорошая хеш-функция распределяет хеш-коды равномерно по всему диапазону выходов.
2. Индексирование: Вычисленный хеш-код используется для определения индекса (позиции) в массиве, где будет храниться соответствующее значение. Часто хеш-код по модулю размера массива (hash(key) % array_size) дает итоговый индекс.
3. Хранение: В массиве по рассчитанному индексу хранится пара (ключ, значение).
4. Поиск: Для нахождения значения по ключу, снова вычисляется хеш-код ключа, определяется индекс, и по этому индексу извлекается значение.
5. Коллизии: Возникают, когда разные ключи имеют одинаковый хеш-код. Существуют различные методы для разрешения коллизий:
   • Метод цепочек (Separate Chaining): По каждому индексу массива хранится список (или другая структура данных), содержащий все пары (ключ, значение), хеш-коды которых привели к этому индексу.
   • Метод открытой адресации (Open Addressing): При возникновении коллизии ищется другое свободное место в массиве по определенному правилу (линейное зондирование, квадратичное зондирование, двойное хеширование).

Преимущества:

• В среднем операции вставки, удаления и поиска имеют сложность O(1), если хеш-функция хорошая и коллизии редки.

Недостатки:

• Худший случай производительности может быть O(n), если все ключи хешируются в один и тот же индекс (например, при плохой хеш-функции или большом количестве коллизий).
• Требуется дополнительная память для массива и, возможно, для разрешения коллизий.

В Swift хеш-таблицы реализованы типом Dictionary.

// Пример использования Dictionary в Swift
var myDictionary: [String: Int] = ["apple": 1, "banana": 2, "orange": 3]

// Доступ по ключу
let value = myDictionary["banana"] // Получит Optional(2)

// Добавление/обновление
myDictionary["grape"] = 4 // Добавит новую пару
myDictionary["apple"] = 10 // Обновит значение для ключа "apple"

// Удаление
myDictionary["orange"] = nil // Удалит пару с ключом "orange"