Как реализовано внутреннее хранение уникальных значений в Swift Set?

Set в Swift реализован как хеш-таблица (hash table) с открытой адресацией и линейным пробированием для разрешения коллизий. Это обеспечивает среднюю сложность O(1) для операций вставки, удаления и поиска.

Принцип работы:

1. Ключ — хеш: Каждый элемент выступает в роли собственного ключа. Его хеш-значение (через Hashable) определяет начальный «бакет» (ячейку) в таблице.
2. Разрешение коллизий: Если два разных элемента имеют одинаковый хеш или вычисленный бакет уже занят другим неравным элементом, Set использует алгоритм пробирования для поиска следующей доступной ячейки.
3. Проверка уникальности: Перед вставкой в найденную ячейку происходит окончательная проверка на равенство (==), чтобы избежать дубликатов.

Пример, иллюстрирующий поведение:

var uniqueNumbers: Set<Int> = []
// Вставка: вычисляется хеш от 10, находится ячейка, элемент добавляется.
uniqueNumbers.insert(10) // [10]
// Вставка дубликата: хеш совпадает, == возвращает true -> вставка игнорируется.
uniqueNumbers.insert(10) // [10]
// Вставка другого элемента: даже при коллизии хешей (маловероятно для Int),
// если == возвращает false, элемент займет другую ячейку.
uniqueNumbers.insert(20) // [10, 20] (порядок не гарантирован)

Особенности реализации Swift:

• Set оптимизирован под разные размеры и типы данных.
• При достижении определенного коэффициента заполнения происходит рехэширование — увеличение размера внутренней таблицы и перераспределение всех элементов, что является операцией O(n).
• Из-за хеширования и пробирования порядок элементов в Set не определен и может меняться при разных запусках или при добавлении/удалении элементов.