Ответ
Все стандартные коллекции — структуры (value types) с семантикой Copy-on-Write.
1. Array
- Хранилище: Непрерывный буфер в памяти.
- Рост: При добавлении элементов и нехватке места (
count > capacity) выделяется новый буфер большего размера (емкость обычно удваивается), элементы копируются. - Производительность: Индексированный доступ O(1), вставка в конец O(1) в среднем, вставка/удаление в середину O(n).
2. Dictionary
- Хранилище: Хэш-таблица (hash table) с открытой адресацией (open addressing) и линейным пробированием (linear probing) для разрешения коллизий.
- Рост: При достижении определенного коэффициента заполнения (load factor) таблица увеличивается, и все элементы рехешируются.
- Производительность: Вставка, поиск, удаление — O(1) в среднем.
3. Set
- Хранилище: Реализован поверх
Dictionary, где ключи — это элементы множества, а значения — фиктивные (()). Наследует все свойства хэш-таблицы.
Пример, иллюстрирующий CoW:
var original = [1, 2, 3]
var copy = original // Буфер памяти общий, копирования нет
copy.append(4) // Только здесь создается новая копия буфера для `copy`
print(original) // [1, 2, 3]
print(copy) // [1, 2, 3, 4]