Что такое коллизия в хеш-таблице и когда она возникает?

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

Почему это важно: Коллизии снижают производительность, превращая операции вставки и поиска из O(1) в O(n) в худшем случае, если используется метод цепочек.

Как Swift обрабатывает коллизии: Swift использует комбинацию методов (например, открытую адресацию), чтобы минимизировать влияние, но разработчик должен обеспечить хорошую хеш-функцию.

Ключевые правила для Hashable в Swift:

1. Если два объекта равны (==), их хеши должны быть одинаковыми.
2. Обратное не обязательно: разные объекты могут иметь одинаковый хеш (это и есть коллизия).
3. Хеш-функция должна быть эффективной и равномерно распределять значения.

Пример плохой и хорошей реализации:

struct Person: Hashable {
    let id: Int
    let name: String

    // ПЛОХО: Использует не уникальное поле, высокая вероятность коллизий
    func hash(into hasher: inout Hasher) {
        hasher.combine(name.count)
    }

    // ХОРОШО: Использует уникальный идентификатор
    func hash(into hasher: inout Hasher) {
        hasher.combine(id)
    }

    static func == (lhs: Person, rhs: Person) -> Bool {
        return lhs.id == rhs.id
    }
}

Best practice: Для хеширования комбинируйте все значимые для равенства поля, используя hasher.combine(_:).