Как Set определяет уникальность элемента?

Как Set определяет уникальность элемента в Swift

В Swift Set — это коллекция, которая хранит уникальные элементы одного типа без определенного порядка. Уникальность элемента определяется с помощью двух ключевых механизмов: Hashable и Equatable протоколов.

Основной механизм: Hashable

Когда элемент добавляется в Set, Swift использует его хэш-значение (hash value), вычисляемое по протоколу Hashable. Хэш-значение — это целое число, которое должно быть одинаковым для одинаковых объектов и разным для разных (с высокой вероятностью).

Пример требования Hashable:

struct Person: Hashable {
    let id: UUID
    let name: String
}

let person1 = Person(id: UUID(), name: "Алексей")
let person2 = Person(id: UUID(), name: "Алексей")
// Разные id → разные хэши → Set считает их разными элементами

Хэш используется для быстрого размещения элемента в «хэш-таблице» — внутренней структуре Set. При добавлении нового элемента сначала вычисляется его хэш и проверяется соответствующая «корзина» (bucket) в таблице.

Дополнительная проверка: Equatable

Если в корзине уже есть элементы с таким же хэшем, Swift дополнительно проверяет равенство через протокол Equatable. Это необходимо из-за возможности хэш-коллизий (разные объекты могут теоретически иметь одинаковый хэш).

Процесс добавления элемента в Set:

1. Вычисляется hashValue нового элемента.
2. По хэшу находится соответствующая корзина в хэш-таблице.
3. Если корзина пуста — элемент добавляется.
4. Если в корзине есть элементы:
   • Проверяется == (равенство) с каждым существующим элементом в этой корзине.
   • Если равенство найдено — элемент считается дубликатом и не добавляется.
   • Если все элементы в корзине не равны новому — он добавляется (несмотря на одинаковый хэш).

Пример реализации Hashable и Equatable

Для структур или классов, которые вы хотите хранить в Set, необходимо реализовать эти протоколы:

struct Product: Hashable {
    let code: Int
    let title: String
    
    // Hashable требует определить hash(into:) метод
    func hash(into hasher: inout Hasher) {
        hasher.combine(code) // Чаще комбинируют уникальные поля
    }
    
    // Equatable требует static func ==
    static func == (lhs: Product, rhs: Product) -> Bool {
        return lhs.code == rhs.code // Определяем равенство по коду
    }
}

// Использование в Set
var productSet: Set<Product> = []
productSet.insert(Product(code: 1, title: "Молоко"))
productSet.insert(Product(code: 1, title: "Молоко")) // Не добавится — одинаковый код
productSet.insert(Product(code: 2, title: "Молоко")) // Добавится — другой код
print(productSet.count) // Выведет 2

Ключевые особенности

• Порядок не гарантируется: Set оптимизирован для быстрого поиска и уникальности, не для порядка.
• Эффективность O(1): В среднем операции добавления, удаления и проверки наличия имеют постоянную сложность благодаря хэш-таблице.
• Автоматическая поддержка для многих типов: Swift предоставляет готовую реализацию Hashable для базовых типов (String, Int, Double), а также для типов, где все свойства уже Hashable.
• Collision resolution: Swift использует внутренние алгоритмы для разрешения коллизий хэшей (например, цепочки или открытая адресация).

Важные нюансы

• Хэш должен быть стабильным: Для одного объекта hashValue должен быть одинаковым в течение всего его жизненного цикла (иначе Set может потерять элемент).
• Сочетание свойств в Hasher: При реализации hash(into:) рекомендуется комбинировать только те свойства, которые участвуют в определении равенства (==).
• Нельзя использовать mutable объекты: Если объект изменяется после добавления в Set, его хэш может измениться, и он станет «недоступным» в коллекции.

Таким образом, уникальность в Set обеспечивается комбинацией хэширования (для быстрой группировки) и проверки равенства (для точного определения дубликатов). Это делает Set одной из наиболее эффективных коллекций для задач проверки уникальности и наличия элементов в Swift.