Collections in Swift — Array, Set, Dictionary, and Why Order Isn't Guaranteed

Swift gives us three collection types, and almost every program reaches for them constantly. An Array is an ordered list that allows duplicates. A Set is an unordered bag of unique values. A Dictionary maps keys to values, also unordered. Same data, three different shapes — and each one keeps something the others throw away.



Here's the part newcomers from Java or C# often miss: all three are generic structs, not classes. Their full names are Array<Element>, Set<Element>, and Dictionary<Key, Value>. The square-bracket syntax we write every day is just sugar — [Int] means Array<Int>, [String: Int] means Dictionary<String, Int>.

let langs: [String] = ["swift", "kotlin", "dart", "swift"]
let unique: Set<String> = ["swift", "kotlin", "dart"]
let released: [String: Int] = ["swift": 2014, "go": 2009]

Because they are structs, they have value semantics. Assigning one collection to another, or passing it into a function, gives the recipient its own independent value — not a shared reference. That single design choice ripples through everything else in this episode, so hold onto it. It is the opposite of how arrays and maps behave in most object-oriented languages, where you pass a reference and a callee can mutate your data behind your back.

An Array stores its elements in a single contiguous buffer in memory — one block, elements laid out back to back. That layout is why indexing is O(1): the machine multiplies the index by the element size, adds it to the buffer's base address, and reads. No searching involved.

So what happens when we append and the buffer is full? Swift allocates a new buffer, copies the old elements across, and frees the old one. To keep that from happening on every single append, it grows the buffer geometrically — roughly doubling the capacity each time it runs out of room.



Most appends just write into a spare slot, which is genuinely O(1). Once in a while an append triggers a doubling, which is O(n) because everything must be copied. Spread across all the appends, the average cost stays constant — that is what amortised O(1) means. Swift exposes two numbers that make this visible: count is how many elements we have, and capacity is how many the current buffer can hold before it must grow.

var nums = [Int]()
print(nums.count, nums.capacity)   // 0 0
nums.append(1)
print(nums.count, nums.capacity)   // 1 1, then grows: 1, 3, 6, 12...

// If we know the size, skip the doublings entirely:
var ready = [Int]()
ready.reserveCapacity(10_000)      // one allocation, no copies

Two operations deserve a warning. insert(_:at:) and remove(at:) near the front of an array are O(n), because every element after the insertion point has to shuffle along to make room or close the gap. Appending and removing at the end are the cheap operations. If you find yourself inserting at index 0 in a loop, that loop is quietly O(n squared).

Array's contains has to walk the buffer element by element. Set and Dictionary do something cleverer: they are hash tables. Instead of searching, they compute where a value should live and jump straight to it.

When we look up a key, Swift feeds it to a Hasher, which produces an integer hash value. That integer, reduced modulo the number of buckets, points at exactly one bucket. We then check just that bucket. No scan of the whole collection.



Sometimes two different keys hash to the same bucket. That is a collision, and it is normal — the table just keeps both in that bucket and compares keys with == to tell them apart. As long as the buckets stay short, lookup, insertion, and contains all average out to O(1).

For any of this to work, the element type of a Set, or the key type of a Dictionary, must conform to the Hashable protocol. Swift's standard types — Int, String, Bool, and so on — already conform. For our own types, the compiler can synthesise the conformance automatically when every stored property is itself Hashable.

struct Point: Hashable {
    let x: Int
    let y: Int
    // == and hash(into:) are synthesised for free
}

var seen: Set<Point> = []
seen.insert(Point(x: 1, y: 2))   // works, because Point is Hashable

One rule binds Hashable and Equatable together: if two values are equal, they must produce the same hash. Break that contract — for instance by hashing only some of the properties you compare in == — and the table will quietly fail to find values it definitely contains.

Now we can answer the practical question: which collection should hold our data? The honest answer is that it depends on the operation we run most often. Indexed access wants an Array. Membership testing wants a Set. Lookup by key wants a Dictionary. The cost table makes the trade-offs concrete.



The trap that catches people is Array.contains. On a handful of elements it is perfectly fine — the constant factors are tiny and the code reads naturally. The cost only bites when the array is large and we call contains repeatedly, perhaps inside a loop. That pattern is secretly O(n times m), and it is the classic reason a feature feels instant on test data and crawls in production.

// Slow when ids is large and we check many times: O(n) per lookup
let ids: [Int] = loadThousands()
for query in queries where ids.contains(query) { ... }

// Fast: build a Set once, then each check is O(1)
let idSet = Set(ids)
for query in queries where idSet.contains(query) { ... }

The rule of thumb: if you are repeatedly asking "is this thing in here?", a Set will almost always beat an Array. If you mostly care about order and indexed access, stay with the Array.

Because Array, Set, and Dictionary are structs, copying one ought to copy all its elements. For a million-element array that would be ruinous. Swift dodges the cost with a trick called copy-on-write, or COW.

When we assign a collection to a second variable, Swift does not copy the buffer. Both variables point at the same underlying storage, and the storage keeps a reference count. The expensive copy is deferred until someone actually mutates a buffer that is shared. At that moment, and only then, Swift makes a private copy so the mutation can't be seen by the other holder.

var a = [1, 2, 3]
var b = a          // no copy yet — both share one buffer
b.append(4)        // b is shared, so it copies, then appends
print(a)           // [1, 2, 3]  — a is untouched
print(b)           // [1, 2, 3, 4]

The payoff is the best of both worlds: collections behave like independent values, yet passing them around stays cheap. We only pay for a copy when we change a buffer that someone else is still holding.

There is one more consequence of value semantics worth burning in. A collection declared with let is immutable in its entirety — not just the variable binding, but the contents. Calling append on a let array is a compile error, full stop. This is unlike a class reference, where let only freezes the reference and you can still mutate the object it points to. With Swift's value-type collections, let means genuinely constant.

let fixed = [1, 2, 3]
// fixed.append(4)   // error: cannot use mutating member on a 'let' constant
var growable = [1, 2, 3]
growable.append(4)   // fine

Run this twice and you may get two different printouts:

let s: Set<Int> = [1, 2, 3, 4, 5]
for value in s { print(value) }
// Run 1:  3 1 5 2 4
// Run 2:  2 4 1 3 5   — a different order, same program

This is not a bug. Swift deliberately refuses to promise an iteration order for Set and Dictionary. Since Swift 4.2 (the proposal was SE-0206), Hashable hashing uses the SipHash algorithm seeded with a per-process random seed. Every time the program launches, the seed changes, so the bucket positions change, so the iteration order changes.

Why on earth would a language make its output non-deterministic on purpose? Two reasons. First, security. If an attacker can predict which bucket a key lands in, they can craft thousands of inputs that all collide into one bucket, degrading every lookup to O(n) and grinding a server to a halt — a hash-flooding denial-of-service attack. A secret, per-process seed makes those collisions impossible to predict. Second, discipline. By scrambling the order, Swift stops us from accidentally writing code that depends on an order the type never promised. The bug surfaces immediately on your machine instead of mysteriously in production.

This is the sharpest contrast with Dart, and it is worth calling out directly. Dart's default Set and Map literals are backed by LinkedHashSet and LinkedHashMap, which preserve insertion order. Iterate a Dart map and you get the keys back in the order you inserted them, every run, guaranteed. Swift makes the opposite choice: its Set and Dictionary give you no order at all, and the order you do observe is randomised between runs.

// Swift — order is unspecified and varies between runs
let d = ["a": 1, "b": 2, "c": 3]
for (k, v) in d { print(k, v) }    // any order, changes each launch

// Need a stable order? Sort explicitly:
for k in d.keys.sorted() { print(k, d[k]!) }   // a, b, c — every time

So the practical rule is simple. Never rely on the order of a Swift Set or Dictionary. If you need order, either keep the data in an Array, or sort the keys at the point where order actually matters. Arrays, of course, always preserve their order — that promise is the whole point of an Array.

The three collections cover almost everything, but Swift's standard library has a few specialised siblings worth knowing.

ArraySlice is what you get when you take a range of an array, like array[2..<5]. Crucially, a slice does not copy — it shares the parent's storage and just remembers a start and end. That makes slicing cheap, but it has a sharp edge: a slice keeps the whole parent buffer alive in memory, and its indices are inherited from the parent (a slice's first index may not be 0). When you want a standalone array, wrap it: Array(slice).

let full = [10, 20, 30, 40, 50]
let slice = full[2...]         // ArraySlice, shares storage
print(slice.startIndex)        // 2, not 0
let standalone = Array(slice)  // now a real, independent [Int]

ContiguousArray is a variant that guarantees a contiguous C-style buffer even for class element types, where a plain Array might use a bridged Objective-C storage on Apple platforms. For pure-Swift numeric work it can shave off a little overhead.

Lazy sequences let us chain map and filter without building an intermediate array at each step. Writing array.lazy.map(...).filter(...) defers the work until something actually consumes the result, which can save a lot of allocation on long pipelines.

let result = (1...1_000_000).lazy
    .map { $0 * 2 }
    .filter { $0 % 3 == 0 }
    .prefix(5)
// Only computes enough to produce 5 elements
print(Array(result))   // [6, 12, 18, 24, 30]

All of this rests on a protocol hierarchy. Sequence is the base — anything you can iterate once with a for loop. Collection refines it with indices and multi-pass traversal, and Array, Set, and Dictionary all conform. That shared protocol is exactly why map, filter, and reduce work uniformly across all three: they are defined once on Sequence, and every collection inherits them.

A closing piece of history. Swift was announced at WWDC in June 2014 and open-sourced in December 2015, and these collection types have been part of the standard library since version 1.0. The randomised hashing that scrambles Set and Dictionary order, though, arrived later in Swift 4.2 in 2018 — a reminder that even a value type as ordinary-looking as a dictionary carries a deliberate security decision inside it.