In Swift, how do you choose between Array, Set and Dictionary, and what does a membership or key lookup cost in each?
answer
- order, uniqueness, lookup by key
- linear scan versus hash lookup
- Hashable elements and keys
- key subscript gives back an optional
basics
~20 sUse Array for ordered values that may repeat, Set for unique values you test for membership, and Dictionary to find a value by key. Array.contains(:) is a linear scan; Set.contains(:) is O(1); a Dictionary key lookup returns an optional.
solid answer
~40 sI pick by the question the code asks most often. If order matters or duplicates are allowed, it is an `Array`: reading by integer position is O(1), but `contains(_:)` walks every element, O(n). If I mostly ask "is this in there?" and duplicates make no sense, it is a `Set`: its `contains(_:)` is documented as O(1) and `insert(_:)` ignores a member that is already present. If I look things up by an identifier, it is a `Dictionary`: `dict[key]` returns `Value?` because the key may be missing. `Set` elements and `Dictionary` keys must be `Hashable`, and neither type keeps a stable insertion order, so anything displayed in order still needs an array.
code
swift · 28 linesstruct Thumbnail {
let id: Int
let title: String
}
var thumbnails: [Thumbnail] = [
Thumbnail(id: 7, title: "Beach"),
Thumbnail(id: 3, title: "Harbour"),
Thumbnail(id: 9, title: "Dunes"),
]
var selectedIDs: Set<Int> = []
var titleCache: [Int: String] = [:]
thumbnails.append(Thumbnail(id: 4, title: "Pier")) // keeps display order
print(thumbnails[0].title) // "Beach": O(1) by position
selectedIDs.insert(9)
selectedIDs.insert(9) // ignored: already a member
print(selectedIDs.count) // 1
print(selectedIDs.contains(9)) // hash lookup, O(1)
print(thumbnails.contains { $0.id == 9 }) // linear scan, O(n)
titleCache[9] = "Dunes"
if let title = titleCache[3] { // String?, nil when missing
print(title)
} else {
print("cache miss for 3")
}go deeper
Recall which container answers which question: order, membership or lookup by key. Know that array contains is linear and set contains is constant time.
Explain why hashing makes set and dictionary lookups constant time on average, what Hashable is needed for, and why iteration order of hashed collections is unpredictable.
Spot a linear contains call inside a loop in a pull request and replace it with a one-time Set conversion, and justify the extra memory against the data sizes involved.
Frame the choice as an access-pattern decision for shared model code: which lookups dominate, whether order is part of the contract, and what keeping two structures in sync costs.
## Three containers, three questions Swift's standard library ships three general-purpose collections, and all three are **value types** declared as structs: `Array<Element>`, `Set<Element>` and `Dictionary<Key, Value>`. Choosing between them is mostly a matter of which question your code asks most often. - **`Array`** keeps elements in the order you put them in and allows duplicates. Positions are integers from `0` up to, but not including, `count`. - **`Set`** keeps each value at most once and has no defined order. It exists to answer "is this value a member?" quickly. - **`Dictionary`** maps each unique key to one value, also with no defined order. It exists to answer "what is stored for this key?" The Swift book's chapter on collection types puts it in one line each: arrays are ordered collections of values, sets are unordered collections of unique values, and dictionaries are unordered collections of key-value associations. ## What each lookup costs The standard library documents complexity in a `Complexity:` line above each member, and those lines are what an interviewer expects you to know. | Operation | Cost or result | Why | |---|---|---| | `array[i]` (read) | O(1) | elements sit in one buffer, so the address is computed | | `array.contains(x)` | O(n) | `Sequence.contains(_:)` compares element by element | | `set.contains(x)` | O(1) | the element's hash picks the bucket | | `set.insert(x)` | returns `(inserted:memberAfterInsert:)` | a duplicate is not stored twice | | `dict[key]` | hash lookup, returns `Value?` | `nil` means the key is absent | The practical consequence: a loop that calls `array.contains(_:)` for each of *m* candidates against *n* elements does O(n * m) comparisons, while the same loop against a `Set` does about *m* hash lookups. Converting once, `Set(array)`, and then querying the set is the standard fix when membership checks dominate. ## A worked scenario: a photo gallery Imagine a gallery screen that shows thumbnails, lets the user select several, and caches titles fetched from disk. 1. The thumbnails are shown in a fixed order and the same photo may legitimately appear twice in different albums, so they live in an **array**. 2. The selected photo IDs have no order and a photo is either selected or not, so they live in a **set**. Tapping a thumbnail asks `selectedIDs.contains(id)` once per cell, which stays cheap however many photos are selected. 3. The title cache answers "what do I already know about photo 42?", so it is a **dictionary** keyed by ID. `titleCache[42]` returns `String?`; a `nil` is a cache miss, not a crash. The code example shows all three side by side. ## Requirements and trade-offs - **Hashable.** A `Set`'s elements and a `Dictionary`'s keys must conform to `Hashable`. Standard types such as `Int`, `String` and enums without associated values already do; how to write a correct conformance for your own type is covered in the lesson on equality and hashing. - **No order.** Iterating a set or a dictionary visits elements in an order the standard library calls stable between mutations but otherwise unpredictable. Never rely on it for display or for tests that compare printed output; sort first, or keep a separate array for order. - **Duplicates.** `Set.insert(_:)` returns a tuple whose `inserted` flag is `false` when the value was already present, so the set's count does not grow. - **Memory.** A hashed collection needs spare capacity to keep lookups fast, so for a handful of elements a plain array scan can be just as quick. Complexity matters as the data grows; for five items, pick what reads most clearly. - **Missing data.** An out-of-range array subscript traps at run time with `Index out of range`; a missing dictionary key just yields `nil`. That difference is why a dictionary is the natural shape for a cache. ## How to answer in an interview Name the question each container answers (order, membership, lookup by key), give the cost of `contains(_:)` on an array versus a set, mention that set elements and dictionary keys must be `Hashable`, and note that neither hashed collection preserves order. Then tie it to a concrete screen, like the gallery above, to show you choose by access pattern rather than by habit.
- You need both fast membership checks and a stable display order. What do you keep?Keep both: an `Array` for the order and a `Set` (or a `Dictionary` keyed by ID) for the lookups, and update them together in one method so they cannot drift apart. The standard library has no ordered set type, so the pairing is the usual answer when you stay inside it.
- Why does a set or dictionary print its contents in a different order than you inserted them?Both are hashed: the position of an element depends on its hash value, not on insertion time. The documentation calls the order stable between mutations but otherwise unpredictable, and hashing is seeded per process, so the order can differ between launches too. Sort before printing or comparing.
- Calling contains(_:) on a large array inside a loop and calling it free
- Expecting a Set or Dictionary to keep insertion order
- Thinking a missing dictionary key traps like an out-of-range array index
- Believing any type can be a Set element without Hashable
- Choosing Dictionary with dummy values instead of a Set for membership