Асимптотика Set и Dictionary. Преимущество перед Array?

Junior PRO

Суть

Set — неупорядоченная коллекция уникальных элементов, Dictionary — пары ключ–значение с уникальными ключами. Обе — хеш-таблицы, поэтому:

• Поиск (contains, subscript), вставка, удаление — O(1) в среднем.
• Худший случай — O(n) (все ключи в одном бакете), на практике не встречается благодаря SipHash со случайным seed.
• Итерация — O(n), порядок не определён и меняется между запусками.
• Рост таблицы (рехеш) — O(n), но амортизируется; reserveCapacity убирает его.
• Операции над множествами (union, intersection, subtracting) — O(n + m).

Элемент Set и ключ Dictionary должны быть Hashable; значение словаря — любым.