Array, Set or Dictionary: how do you choose, and what does each operation cost?
Predict first
What does this print?
let a: Set = [1, 2, 3]
let b: Set = [3, 2, 1]
print(a == b)- true
- false
Predict first
What happens at runtime?
let k = "a"
let d = [k: 1, k: 2]
print(d.count)- Prints 2
- Prints 1
- Crashes
Mental model. An array is a numbered bookshelf. A set is a guest list at the door. A dictionary is a phone book.
Choose by the operation you do most. Array keeps order and gives O(1) access by position, but finding a value with contains is O(n). Set answers “is it in here?” in O(1) on average and keeps elements unique. Dictionary maps unique keys to values with O(1) average lookup by key.
Set and Dictionary need Hashable elements or keys, and neither promises any order. “O(1)” means average case: heavy hash collisions degrade it. If you need both order and fast lookup, keep an array and a set side by side, or use OrderedSet from swift-collections.
Sets compare by membership, never by order. Two arrays with these elements would not be equal.
A dictionary literal with a duplicate key traps at runtime. Building it with init(uniqueKeysWithValues:) traps the same way. Use Dictionary(_:uniquingKeysWith:) to merge instead.
| Array | Set | Dictionary | |
|---|---|---|---|
| Ordered | yes | no | no |
| Find a value | O(n) | O(1) average | O(1) average (by key) |
| Add at the end | O(1) amortised | O(1) average | O(1) average |
| Duplicates | allowed | no | unique keys |
| Elements must be | anything | Hashable | keys Hashable |
Common traps
- “Dictionary keeps insertion order.” It does not, and the order can change between launches.
- “
containsis fast.” Only on aSet. On anArrayit scans every element.
They might follow up with
- When is an array of 20 items faster than a set? Hashing has a fixed cost, so for tiny collections a linear scan can win. Measure before converting.
- How do you get a stable order out of a dictionary? Sort the keys when you present it, or use an ordered collection.
Related questions
- 2.1.2 What must Hashable guarantee, and why does iteration order change between launches?
- 2.1.3 When is the standard library not enough, and what does swift-collections add?
- 1.1.7 What is copy-on-write? Which types use it?
What must Hashable guarantee, and why does iteration order change… →