Как Set хранит уникальные значения?

Принцип работы Set в Swift для обеспечения уникальности

Set в Swift — это коллекция неупорядоченных уникальных значений. Его ключевая особенность — гарантированная уникальность элементов, достигаемая за счёт комбинации хеширования и протокола Hashable.

Основа: протокол Hashable

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

struct Book: Hashable {
    let id: Int
    let title: String
}

let book1 = Book(id: 1, title: "Swift Programming")
let book2 = Book(id: 1, title: "Swift Programming")
let bookSet: Set<Book> = [book1, book2]
print(bookSet.count) // 1, так как книги идентичны

Механизм хранения и проверки уникальности

1. Вычисление хеш-значения: При добавлении элемента сначала вычисляется его хеш-значение через метод hashValue или hash(into:). Хеш используется для определения "корзины" (bucket), в которую будет помещён элемент.
2. Разрешение коллизий: Разные элементы могут иметь одинаковый хеш (коллизия). В этом случае Set использует проверку равенства через метод == из протокола Equatable, чтобы определить, действительно ли элементы идентичны.
3. Добавление элемента: Если в целевой корзине нет элементов с таким же хешом, элемент добавляется. Если есть — проводится поочередное сравнение на равенство. При обнаружении дубликата добавление игнорируется.

Внутренняя реализация

Set в Swift реализован как хеш-таблица с оптимизациями для производительности. Основные характеристики:

• Динамическое изменение размера: При достижении определенного коэффициента заполнения (load factor) размер хеш-таблицы увеличивается, чтобы сохранить эффективность операций.
• Эффективность операций: В среднем, поиск, вставка и удаление выполняются за O(1) время, хотя в худшем случае (например, при множестве коллизий) это может деградировать до O(n).

Практический пример с дубликатами

let numbers = [1, 2, 2, 3, 4, 4, 4]
let uniqueNumbers = Set(numbers)
print(uniqueNumbers) // [2, 4, 3, 1] (порядок может отличаться)
print(uniqueNumbers.count) // 4

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

• Тип должен быть Hashable: Все стандартные типы (Int, String, Double и т.д.) уже соответствуют Hashable. Для пользовательских типов нужно реализовать протокол.
• Сравнение через hashValue и ==: Для корректной работы должны быть правильно реализованы оба механизма.
• Неупорядоченность: Элементы не имеют гарантированного порядка, но при итерации порядок будет стабильным в рамках одной экземпляра Set.
• Оптимизация под капотом: Swift использует интринсики компилятора и специализированные буферы для эффективного хранения примитивных типов.

Отличия от Array

// Array позволяет дубликаты и сохраняет порядок
let array = [1, 2, 1, 3]
print(array) // [1, 2, 1, 3]

// Set автоматически удаляет дубликаты и не гарантирует порядок
let set: Set = [1, 2, 1, 3]
print(set) // [2, 3, 1] (порядок произвольный)

Важно: При использовании пользовательских типов в Set крайне важно, чтобы реализация hash(into:) и == была согласованной — два равных объекта должны возвращать одинаковый хеш. Нарушение этого правила приведёт к некорректному поведению Set и потенциальной потере данных.