Краткий ответ

Set использует результат hash(into:), чтобы быстро выбрать область поиска, а затем проверяет элементы в ней через ==. Поэтому проверка принадлежности обычно выполняется за амортизированное время O(1), но при большом числе коллизий в худшем случае может деградировать до O(n).

struct User: Hashable {
    let id: Int

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

    func hash(into hasher: inout Hasher) {
        hasher.combine(id)
    }
}

let users: Set = [User(id: 7)]
let containsUser = users.contains(User(id: 7))

Для двух экземпляров с одинаковым id результат contains будет true, поскольку они равны и имеют согласованный хеш.

Исторический контекст

Обычная последовательность требует последовательно сравнивать элементы при поиске, поэтому её проверка принадлежности обычно имеет линейную сложность. Структура Set появилась как абстракция для хранения уникальных значений и эффективной проверки принадлежности.

Хеширование позволяет не просматривать всю коллекцию: элемент сначала направляется в предполагаемую область хранения по своему хешу, а точное совпадение подтверждается сравнением равенства.

Постановка проблемы

Hashable задаёт не просто способ получить произвольное число. Он должен быть согласован с Equatable: если два значения равны через ==, их хеши обязаны совпадать.

Нарушение этого правила приводит к логическим ошибкам: Set может не найти значение, которое фактически считается равным уже сохранённому элементу, или некорректно обрабатывать вставку дубликата.

Важно также не изменять состояние, участвующее в равенстве и хешировании, пока значение находится в Set. После такой мутации элемент может оказаться не в той области, где структура будет его искать.

Подробное решение

При проверке contains Set вычисляет хеш искомого значения. На его основе выбирается позиция или группа позиций во внутренней хеш-таблице. Если там найден кандидат, Swift сравнивает его с искомым значением через ==, потому что одинаковый хеш ещё не означает равенство.

Коллизия возникает, когда разные значения получают один и тот же хеш или попадают в одну область таблицы. Она корректна с точки зрения API, но увеличивает количество сравнений. Поэтому средняя сложность операций вставки, поиска и удаления обычно O(1), а гарантии постоянного времени для любого набора данных нет.

Метод hash(into:) должен включать все свойства, которые участвуют в ==, и не должен включать свойства, игнорируемые равенством. Сам хеш нельзя считать стабильным идентификатором: его значение предназначено для работы структуры данных, а не для сохранения между запусками программы.

Set хранит только уникальные значения. При вставке Swift сначала использует хеш для поиска возможного совпадения, а затем == определяет, является ли новый элемент дубликатом.

Ситуация из практики

В сервисе нужно быстро проверять, имеет ли пользователь доступ к набору числовых идентификаторов. Вариант с массивом прост, но каждая проверка требует линейного поиска и плохо масштабируется при большом количестве идентификаторов.

Можно использовать отсортированный массив и бинарный поиск: он обеспечивает O(log n), но требует поддерживать сортировку. Можно выбрать Set: он обычно даёт O(1) на проверку, но использует дополнительную память и не сохраняет порядок элементов.

Для частых проверок принадлежности выбран Set, а данные, участвующие в равенстве, сделаны неизменяемыми. В результате проверки не зависят от порядка элементов и не требуют полного обхода коллекции.

Что кандидаты часто упускают

Достаточно ли одинакового хеша, чтобы два элемента считались равными?

Нет. Одинаковый хеш означает только возможную коллизию. Для окончательного решения Set вызывает ==. Разные значения обязаны допускать одинаковый хеш, поэтому реализация должна корректно обрабатывать коллизии.

Что произойдёт, если hash(into:) использует только часть свойств, участвующих в ==?

Если равные значения всё равно получают одинаковый хеш, непосредственное нарушение контракта не возникает, но распределение может стать хуже. Например, хеширование только одного часто повторяющегося поля увеличит число коллизий и ухудшит практическую производительность.

Почему нельзя менять ключевые свойства элемента после его добавления в Set?

После изменения хеш и результат равенства могут перестать соответствовать позиции элемента во внутренней таблице. Структура продолжит искать его по новому хешу, хотя он был размещён по старому. Безопасный подход — удалить элемент, изменить его и добавить заново либо использовать неизменяемое значение.