Dictionaries and sets

Dictionary and Set are both hash tables, and both depend entirely on Hashable being implemented correctly. Get it wrong and nothing crashes — performance quietly degrades from O(1) to O(n), or values go missing.

The contract

Hashable has one rule, and it runs in one direction only:

If two values are equal, they must have the same hash value.

The converse is not required. Two unequal values may share a hash — that is a collision, and the table handles it by comparing with == within the bucket.

Breaking the rule in the other direction is what causes lost values:

struct User: Hashable {
    let id: UUID
    var lastSeen: Date

    static func == (lhs: User, rhs: User) -> Bool {
        lhs.id == rhs.id                     // equality ignores lastSeen
    }

    func hash(into hasher: inout Hasher) {
        hasher.combine(id)
        hasher.combine(lastSeen)             // but the hash does not — broken
    }
}

Two users with the same id and different lastSeen are ==, but hash differently. Insert one into a Set and look up the other and it is not found, because the lookup goes to the wrong bucket and never reaches the comparison.

Hashing is seeded per launch

Hasher is seeded randomly each time the process starts, so hash values are not stable across launches. Two consequences:

Never persist a hashValue. Not in a file, not in a database, not in a cache key that outlives the process. It will be different tomorrow.

Iteration order is not stable. A Dictionary or Set iterates in an order determined by the hash seed, so the same code produces a different order on the next launch. Code that appears to work because a dictionary happened to iterate alphabetically will break, and it will break in production rather than in tests.

for (key, value) in settings.sorted(by: { $0.key < $1.key }) { … }

If order matters, sort explicitly. If order matters and is part of the data model, use an array of pairs or an ordered collection.

Dictionary operations worth knowing

The subscript with a default removes most of the awkward code around counting and grouping:

var counts: [String: Int] = [:]
for word in words {
    counts[word, default: 0] += 1
}

That reads and writes through the same subscript, and because it is _modify-based it does not copy the value out and back — it mutates in place.

Three initialisers cover most of the rest:

Dictionary(grouping: users, by: \.city)             // [String: [User]]
Dictionary(uniqueKeysWithValues: pairs)             // traps on a duplicate key
Dictionary(pairs, uniquingKeysWith: { old, _ in old })   // resolves duplicates

uniqueKeysWithValues is worth calling out: it does not return nil or throw on a duplicate key, it traps. Building a dictionary from server data with that initialiser is a crash waiting for the first duplicate id. Use uniquingKeysWith: for anything you did not generate yourself.

merge and merging combine two dictionaries with an explicit conflict rule, which is the shape to reach for instead of a loop:

defaults.merging(overrides) { _, override in override }

When a Set is the right answer

The three-line version: Set is right when you need membership, uniqueness, or set algebra, and wrong when you need order or duplicates.

The case people miss is membership testing inside a loop:

// O(n × m)
let filtered = items.filter { blockedIDs.contains($0.id) }      // blockedIDs is an Array

// O(n)
let blocked = Set(blockedIDs)
let filtered = items.filter { blocked.contains($0.id) }

Array.contains is a linear scan. Inside a filter over a thousand items, with a thousand blocked ids, that is a million comparisons instead of a thousand lookups. Converting to a Set costs one pass and pays for itself immediately.

The set algebra methods are worth knowing by name, because the hand-written loops are longer and slower:

current.subtracting(previous)      // added
previous.subtracting(current)      // removed
current.intersection(previous)     // unchanged
current.symmetricDifference(previous)

That first pair is the whole of a diffing algorithm for unordered data, and it is how you work out what to insert and delete without comparing arrays element by element.

Copy-on-write applies here too

Both types are value types wrapping a heap buffer, exactly as described in the values-and-references chapter. Passing a large dictionary to a function copies a pointer; mutating a copy duplicates the buffer.

The one dictionary-specific cost is rehashing on growth. A dictionary that grows past its capacity allocates a larger buffer and rehashes every key into it. Building a large dictionary in a loop therefore rehashes several times, and minimumCapacity avoids it:

var index = Dictionary<String, Item>(minimumCapacity: items.count)

Worth doing when the size is known in advance and large. Not worth doing otherwise — the reallocation strategy is amortised, and this is a micro-optimisation everywhere except the loop where it is not.