Какие способы разрешения коллизий в хеш-таблицах вы знаете?

Основные методы разрешения коллизий в хеш-таблицах:

1. Метод цепочек (Separate Chaining) Элементы с одинаковым хэш-кодом хранятся в связном списке (или другой структуре) в одной ячейке.

// Пример реализации с цепочками
class HashTable<Key: Hashable, Value> {
    private var buckets: [[(Key, Value)]]

    func insert(key: Key, value: Value) {
        let index = abs(key.hashValue) % buckets.count
        buckets[index].append((key, value))
    }
}

2. Открытая адресация (Open Addressing) При коллизии элемент помещается в другую свободную ячейку согласно алгоритму поиска:

• Линейное пробирование: h(k, i) = (h'(k) + i) % m
• Квадратичное пробирование: h(k, i) = (h'(k) + c₁i + c₂i²) % m
• Двойное хеширование: h(k, i) = (h₁(k) + i * h₂(k)) % m

3. Robin Hood Hashing Вариант открытой адресации, где при вставке "богатый" элемент (с меньшим расстоянием от исходной позиции) может заменить "бедный" (с большим расстоянием). Используется в Swift Dictionary.

4. Cuckoo Hashing Использует две хеш-функции и две таблицы. При коллизии существующий элемент "вытесняется" в другую таблицу.

Практические рекомендации для Swift:

• Реализуйте hash(into:), комбинируя все значимые поля
• Используйте качественные хеш-функции для минимизации коллизий
• Swift Dictionary автоматически использует Robin Hood hashing с перехешированием при высокой нагрузке