Что такое коллизия в контексте хеширования в Swift?

Коллизия хешей — это ситуация, когда два разных объекта (с разными значениями свойств) возвращают одинаковое хеш-значение при вызове hashValue или hash(into:).

Почему это проблема? Коллизии влияют на производительность коллекций, основанных на хеш-таблицах (Dictionary, Set), но не нарушают их корректность, так как Swift использует дополнительное сравнение через оператор ==.

Пример коллизии:

struct Book: Hashable {
    let id: Int // Уникальный идентификатор
    let title: String
    // Упрощенная, плохая реализация хеша
    func hash(into hasher: inout Hasher) {
        hasher.combine(id % 2) // Хеш зависит только от четности id!
    }
    static func == (lhs: Book, rhs: Book) -> Bool {
        return lhs.id == rhs.id // Правильное сравнение
    }
}

let book1 = Book(id: 1, title: "Book A") // id=1 (нечетное) -> хеш X
let book2 = Book(id: 3, title: "Book B") // id=3 (нечетное) -> хеш X
// Коллизия! Разные книги, одинаковый хеш.

var library: Set<Book> = [book1, book2]
print(library.count) // 2. Коллизия обработана, оба объекта добавлены,
                     // но поиск будет медленнее из-за цепочек в хеш-таблице.

Как избегать коллизий и писать хороший Hashable:

1. Комбинируйте все значимые для равенства свойства в методе hash(into:).

   func hash(into hasher: inout Hasher) {
       hasher.combine(id)    // Уникальный id
       hasher.combine(title) // + название для полноты
   }

2. Согласованность с ==: Два объекта, которые равны (== возвращает true), обязаны иметь одинаковый хеш. Обратное не обязательно (коллизии разрешены).
3. Используйте Hasher: Не вычисляйте хеш вручную. Позвольте Swift-стандартной библиотеке сделать это эффективно, передавая свойства в hasher.combine(_:).

Итог: Коллизии ухудшают производительность коллекций (время поиска может деградировать до O(n)), но корректность работы гарантируется оператором ==.