Какие существуют основные методы разрешения коллизий в хеш-таблицах?

Коллизия в хеш-таблице возникает, когда разные ключи дают одинаковый индекс (хеш). Существует два основных подхода к их разрешению.

1. Метод цепочек (Separate Chaining) Идея: Каждая ячейка массива (bucket) содержит связный список (или другую структуру) всех элементов, попавших в неё.

class HashTable<Key: Hashable, Value> {
    private typealias Element = (key: Key, value: Value)
    private typealias Bucket = [Element]
    private var buckets: [Bucket]

    init(capacity: Int) {
        buckets = Array(repeating: [], count: capacity)
    }

    private func index(for key: Key) -> Int {
        return abs(key.hashValue) % buckets.count
    }

    func insert(_ value: Value, for key: Key) {
        let index = self.index(for: key)
        // Ищем, есть ли уже такой ключ в цепочке
        if let existingIndex = buckets[index].firstIndex(where: { $0.key == key }) {
            buckets[index][existingIndex].value = value // Обновление
        } else {
            buckets[index].append((key: key, value: value)) // Добавление в конец списка
        }
    }
}

Плюсы: Простая реализация, эффективна при высокой нагрузке. Минусы: Дополнительные затраты памяти на хранение указателей списка.

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

• Линейное пробирование: newIndex = (hash + i) % capacity, где i — номер попытки.
  • Проблема: Образование кластеров (первичная кластеризация).
• Квадратичное пробирование: newIndex = (hash + i²) % capacity.
  • Уменьшает кластеризацию, но может не найти свободную ячейку даже при их наличии.
• Двойное хеширование: newIndex = (hash1 + i * hash2(key)) % capacity.
  • Использует вторую хеш-функцию для шага. Наиболее эффективный метод, минимизирует кластеризацию.