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

А, ну ты глянь, какие приёмы придумали, чтобы эти ёбанные коллизии в хеш-таблицах не превращали всё в ад! Это ж как в общаге, когда на одну комнату по пьяни заселяют пятерых — кто-то в шкафу, кто-то под кроватью. Вот и тут так же.

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. Просто, но если много коллизий, образуются кластеры — целые пробки из несчастных значений, которые все друг другу мешают. Пиздец, а не эффективность.
• Квадратичное пробирование: Шагаешь не на 1, а на i². 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:) правильно. Мешай в кучу все значимые поля, как салат. Одно пропустишь — и всё, коллизии обеспечены.
• Хеш-функция должна быть качественной, чтобы разбрасывать ключи равномерно. Не надо просто возвращать 1. Хуйня получится.
• И расслабься, за тебя уже всё придумали. Swift Dictionary сам использует того самого Робина Гуда и сам переезжает в новую квартиру (rehashing), когда в старой стало тесно. Доверяй, но проверяй, что хешируешь ты правильно.