Что представляют собой коллекции под капотом?

Архитектура коллекций в iOS / Swift

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

Основные типы и их внутреннее устройство

Массивы (Array) - наиболее сложно устроены из-за требований к производительности:

// Внутренне Array реализован как структура с буфером
struct _ArrayBuffer<Element> {
    var _storage: _ContiguousArrayStorage<Element>?
}

Массивы используют Contiguous Memory Allocation - непрерывное выделение памяти. При создании резервируется некоторый capacity, превышающий текущий count. При добавлении элементов сверх capacity происходит exponential growth strategy - увеличение буфера в 2 раза с копированием всех существующих элементов (O(n) операция).

// Пример поведения роста массива
var array: [Int] = []  // capacity = 0
array.append(1)        // capacity = 1
array.append(2)        // capacity = 2, переаллокация
array.append(3)        // capacity = 4, переаллокация

Словари (Dictionary) реализованы через хэш-таблицу с открытой адресацией:

// Упрощенное представление структуры словаря
struct Dictionary<Key: Hashable, Value> {
    var _variant: _Variant
    var _scale: Int  // емкость = 2^scale
    var _reservedScale: Int?
}

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

• Использует linear probing для разрешения коллизий
• Автоматическое рехэширование при достижении load factor (~75%)
• Buckets хранят либо элементы, либо tombstone для удаленных записей
• Оптимизация для маленьких словарей (до 3 элементов) через inline хранение

Множества (Set) - фактически словари без значений, используют ту же хэш-таблицу:

struct Set<Element: Hashable> {
    var _variant: _Variant  // та же реализация, что и у Dictionary
}

Ключевые оптимизации

Copy-on-Write (CoW)

Все коллекции - value types, но используют CoW для избежания ненужного копирования:

// Пример CoW в действии
var a = [1, 2, 3]
var b = a               // Обе переменные ссылаются на один буфер
a.append(4)             // Только здесь происходит фактическое копирование

Внутренний буфер оборачивается в класс, который подсчитывает ссылки. Копирование происходит только при модификации, когда reference count > 1.

Специализированные хранилища

Swift использует различные внутренние типы хранилищ:

• _ContiguousArrayStorage - для обычных массивов
• _ArrayBuffer - для обертки хранилища
• _NativeDictionaryBuffer - для нативных словарей
• _CocoaDictionaryBuffer - для моста с NSDictionary

Bridge to Objective-C

Для взаимодействия с Objective-C коллекции автоматически бриджатся:

let swiftArray = [1, 2, 3]
let nsArray = swiftArray as NSArray  // Легковесный бриджинг без копирования

Производительность и Big-O

• Array:

  • доступ по индексу - O(1)
  • поиск элемента - O(n)
  • добавление в конец - амортизированное O(1)
  • вставка в начало/середину - O(n)

• Dictionary/Set:

  • вставка, удаление, поиск - среднее O(1), худшее O(n)
  • итерация - O(n)

Экспериментальная проверка

Можно исследовать внутреннюю структуру через Mirror:

let array = [1, 2, 3]
let mirror = Mirror(reflecting: array)
print(mirror.children.count)  // Показывает внутренние свойства

Память и управление жизненным циклом

Коллекции используют Automatic Reference Counting (ARC) для управления памятью буферов. При освобождении последней ссылки на буфер, память немедленно возвращается системе.

Особенности реализации в стандартной библиотеке

Стандартная библиотека Swift содержит специализированные версии коллекций для:

• Маленьких коллекций (inline хранение в стеке)
• Коллекций с trivial типами (без ARC)
• Коллекций с единственной ссылкой (оптимизация CoW)

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