Swift Set: When contains(...) => true Misleads You and Hides a Broken Collection
Rewrite the surname on a card without moving it to the right drawer, and the catalog sends the next search to the wrong place. This illustrates a stale index, not literal alphabetical hashing.
The problem:
Add two users to a Swift Set, with IDs 1 and 2. Then change the first user’s ID (user.id = 2), and iterating the collection now gives [2, 2]: both stored objects compare equal. A contains check can still return true, so a quick membership test makes the mistake look harmless.
The mutation compiles because the set holds references to class instances. Another reference can change the field that defines equality without giving the collection a chance to reconsider its index. The useful question is how to expose that failure even when lookup appears to work.
Following that one assignment leads to a second surprise. “Swift picks one random seed per process” is only part of the explanation for results that change between newly created sets. We’ll use the actual output and the native lookup implementation to separate those two problems. We’ll also explain what a random seed is and how it affects hashing.
TL;DR
- Keep the fields used by
==andhash(into:)stable while an object is in aSetor used as aDictionarykey. Aletcollection does not freeze its class instances. - A successful
containsafter a key mutation does not validate the collection. It can already hold two elements that compare equal. - The inspected native implementation combines a process seed with a table-specific seed. New tables can give different observations within one process; repeated lookup in one unchanged table is a different experiment.
- Do not persist
hashValueas a cache key or database ID: the same value can receive a different hash after the program restarts. Store a stable ID for an entity; for a content fingerprint, choose an appropriate stable algorithm and a defined byte representation. - How to avoid the problem: prefer a stable account ID when deduplicating accounts. Use
===andObjectIdentifierwhen tracking live instances. If the actual key must change, remove it from every affected collection before mutation, then insert it again.
The Set already violates uniqueness, although contains returns true
Note
The complete code for both versions, with the bug and with the fix, appears below, immediately after the output. User is a class whose == and hash(into:) both use id. The users set stores references to those objects; another part of the application can hold references to the same instances.
Start with IDs 1 and 2. They are unequal, so insertion keeps both. Change the first ID to 2 through that other reference. There is no reinsertion to check uniqueness. The local run prints:
Stored IDs: [2, 2]
Count: 2
Objects compare equal: true
Contains first: true
Contains second: true
Every stored ID is unique: falseThe collection is already broken: a Set must not contain two elements that compare equal through ==. We violated that requirement by changing the key after insertion. contains only looks for an equal element; it does not scan every stored element for duplicates. Its true therefore does not validate the mutation or the collection. Here, the duplicate IDs and Count: 2 expose the mistake.
The comparison below changes one thing. On the left, the key is changed in place. On the right, the element is removed using its old key, changed, and inserted again. Run both to compare the stored IDs and the uniqueness result.
With the bug
// ════════════════════════════════════════════════════════════════
// ▶ ARTICLE EXAMPLE: the code discussed in the article
// ════════════════════════════════════════════════════════════════
final class User: Hashable {
var id: Int
init(id: Int) { self.id = id }
static func == (lhs: User, rhs: User) -> Bool {
lhs.id == rhs.id
}
func hash(into hasher: inout Hasher) {
hasher.combine(id)
}
}
func changeID(
_ user: User, to id: Int,
in users: inout Set<User>
) {
user.id = id
}
// ────────────────────────────────────────────────────────────────
// ◇ DEMO HARNESS: not part of the example. It only runs the code
// above and prints the result. Change it freely in the editor.
// ────────────────────────────────────────────────────────────────
import Foundation
print("▶ Start at \(Date.now)\n")
let first = User(id: 1)
let second = User(id: 2)
var users: Set<User> = [first, second]
changeID(first, to: 2, in: &users)
let ids = users.map(\.id).sorted()
print("Stored IDs: \(ids)")
print("Count: \(users.count)")
print("Objects compare equal: \(first == second)")
print("Contains first: \(users.contains(first))")
print("Contains second: \(users.contains(second))")
let unique = users.count == Set(ids).count
print("Every stored ID is unique: \(unique)")
// ▷ Try: change the destination ID from 2 to 3 and compare membership as well as uniqueness.Fixed
// ════════════════════════════════════════════════════════════════
// ▶ ARTICLE EXAMPLE: the code discussed in the article
// ════════════════════════════════════════════════════════════════
final class User: Hashable {
var id: Int
init(id: Int) { self.id = id }
static func == (lhs: User, rhs: User) -> Bool {
lhs.id == rhs.id
}
func hash(into hasher: inout Hasher) {
hasher.combine(id)
}
}
func changeID(
_ user: User, to id: Int,
in users: inout Set<User>
) {
users.remove(user)
user.id = id
users.insert(user)
}
// ────────────────────────────────────────────────────────────────
// ◇ DEMO HARNESS: not part of the example. It only runs the code
// above and prints the result. Change it freely in the editor.
// ────────────────────────────────────────────────────────────────
import Foundation
print("▶ Start at \(Date.now)\n")
let first = User(id: 1)
let second = User(id: 2)
var users: Set<User> = [first, second]
changeID(first, to: 2, in: &users)
let ids = users.map(\.id).sorted()
print("Stored IDs: \(ids)")
print("Count: \(users.count)")
print("Objects compare equal: \(first == second)")
print("Contains first: \(users.contains(first))")
print("Contains second: \(users.contains(second))")
let unique = users.count == Set(ids).count
print("Every stored ID is unique: \(unique)")
// ▷ Try: change the destination ID from 2 to 3 and compare membership as well as uniqueness.What changed
final class User: Hashable {
var id: Int
init(id: Int) { self.id = id }
static func == (lhs: User, rhs: User) -> Bool {
lhs.id == rhs.id
}
func hash(into hasher: inout Hasher) {
hasher.combine(id)
}
}
func changeID(
_ user: User, to id: Int,
in users: inout Set<User>
) {
+ users.remove(user)
user.id = id
+ users.insert(user)
}
On the left, changing the key in place leaves two equal members. On the right, removal before mutation and reinsertion keep one equal member. Reinsertion does not merge the users’ fields.
Reinsertion checks equality again. Because the destination ID already exists, the corrected example keeps one member for it. This example intentionally accepts keeping one equal member; it does not merge the users’ fields. An application that forbids ID conflicts should reject the change instead. For an account model, an immutable account ID is usually the cleaner design.
The interesting detail: on the corrected side, contains(first) can still be true even if the set kept the already-present second instance. contains checks equality, not whether that exact reference is stored. Here the stored count and IDs confirm that only one equal member remains.
Removal must happen before mutation. Removal also performs a lookup, so changing the key first can make that operation miss as well. If several collections hold the same object, every affected collection needs to release the old key before it changes. The comparison owns only the one set shown.
The reference stayed put; the lookup key changed
The problem explained: for this example, think of a hash table as numbered storage slots, or buckets. Insertion uses a hash to choose a starting bucket, checks for an equal element, and finds somewhere to store the new element. Lookup follows the corresponding search procedure.
With a class, the stored element is a reference. Assigning user.id = 2 changes the object reached by that reference. It does not call an insertion or removal method on the set. The reference remains in the slot selected when the object’s key was 1.
Now contains(user) hashes the current key, 2. That search can start somewhere else and reach an empty bucket before it reaches the stored reference. The object hasn’t disappeared; the lookup no longer follows the route used to place it.
The label changed; the file stayed put. A search based on the new key can look in the empty slot instead.
🔎 What to watch: follow User u. Its id changes while the reference in Bucket [1] stays put. Then Lookup follows the new key to the empty Bucket [2].
This is a four-bucket teaching model with invented hashes (105 and 202). It isolates the reference and the two search routes; the native implementation comes next.
Two requirements matter here:
- Equality and hashing must agree. Values that compare equal must feed the same essential components to
Hasher, in the same order. That is the documented Hashable requirement. - Do not change the key while it is in the collection. The equality-defining components must stay stable while an element is stored in the set.
The User implementation agrees with itself at each instant: both methods read id. The mistake is changing that key while the collection still indexes the old state. Making the collection a let constant does not freeze the fields of a class instance inside it. Copying a Set also doesn’t make independent copies of those instances.
Why contains(…) can return true after a key change
With one element, the same mistake can be harder to recognize. The object is still visible during iteration, but hash-based lookup may return false. In another run it may return true.
Tip
Try it yourself: run the program below several times with Run, or choose Open in the online editor → Run. Compare Hash-based lookup with Same instance found by iteration: lookup can change between true and false across executions, while iteration finds the same instance. Seeing both results within a few attempts is not guaranteed; repeated true results do not make the mutation safe either.
// ════════════════════════════════════════════════════════════════
// ▶ ARTICLE EXAMPLE: the code discussed in the article
// ════════════════════════════════════════════════════════════════
final class User: Hashable {
var id: Int
init(id: Int) { self.id = id }
static func == (lhs: User, rhs: User) -> Bool {
lhs.id == rhs.id
}
func hash(into hasher: inout Hasher) {
hasher.combine(id)
}
}
// ────────────────────────────────────────────────────────────────
// ◇ DEMO HARNESS: not part of the example. It only runs the code
// above and prints the result. Change it freely in the editor.
// ────────────────────────────────────────────────────────────────
import Foundation
print("▶ Start at \(Date.now)\n")
let user = User(id: 1)
let users: Set<User> = [user]
user.id = 2
print("Count: \(users.count)")
print("Stored IDs: \(users.map(\.id).sorted())")
print("Hash-based lookup: \(users.contains(user))")
let found = users.contains { $0 === user }
print("Same instance found by iteration: \(found)")
// ▷ Try: change id to another number; a successful lookup does not validate the mutation.One recorded run printed Count: 1, Stored IDs: [2] and Hash-based lookup: false, while iteration still found the exact instance. Iteration follows the stored references; contains(_:) searches using the current key. The iteration check is a diagnostic here, not a repair for the invalid index.
Suppose our teaching table has four buckets. An insertion with an invented hash of 105 starts at bucket 105 % 4, which is 1. After mutation, consider two possible hashes:
| Hash of the new key | Starting bucket | What happens in this one-element model |
|---|---|---|
202 |
2 |
The bucket is empty, so the lookup misses. |
309 |
1 |
The lookup reaches the stored reference; == reads the current IDs, 2 == 2, and succeeds. |
A finite set of slots cannot give every possible hash a unique starting slot. Two different full hashes can select the same bucket.
105 and 309 are different hashes. What matches is their starting bucket, after mapping a much larger hash range into four slots. This distinction avoids making the explanation depend on finding a collision between two complete hash values.
Swift’s native implementation uses a power-of-two bucket count and computes the starting index with hashValue & bucketMask. It then probes occupied buckets, compares elements through ==, and continues until it finds a match or an empty slot. See idealBucket in HashTable.swift and find in NativeSet.swift.
The positive-number % 4 example illustrates the mapping; it is not a recipe for recovering a real bucket from user.hashValue. A set also supplies its own seed, and public Set.capacity is not the number of buckets.
With more occupied buckets, probing creates additional routes to a match. A successful contains call therefore tells us little about the correctness of this mutation. The test may have taken a route that happened to reach the reference.
Why can new sets disagree within one process?
Why does Swift need a random seed? To make it harder for an attacker to choose keys that overwhelm an application. With predictable hashing, an attacker can prepare many distinct keys with collisions and feed them to the program. A lookup or insertion that averages O(1) can require O(n) comparisons; a series of n insertions can take up to O(n²) work. The CPU spends its time processing those inputs, leaving the application unresponsive or the service unable to keep up with requests. This is hash flooding, a form of denial of service described in the motivation for SE-0206.
A seed is a random starting value for hashing, normally chosen when the Swift process starts. Another seed can distribute the same keys differently, making a collision set prepared for one execution harder to reuse in another. This protects against predictable collision patterns; collisions remain possible. A correct collection also checks keys with ==: collisions can slow lookup, but do not by themselves make it return another key’s data.
When did Swift introduce this? General randomized hashing in the standard library and the public Hasher arrived with Swift 4.2, as recorded in Apple’s release notes and SE-0206. “There was no seed anywhere before 4.2” would be too broad: for example, Swift 4.1 already used randomly seeded SipHash for String on non-Apple platforms. Karoy Lorentey, the implementation’s author, documented that exception.
Now test whether one process seed explains the whole experiment. Create new sets inside the same process. One optimized execution produced this sequence for ten short-lived tables:
F T T F F F F F F FT means contains returned true; F means false. The process did not restart between these attempts. In that same execution, 64 tables kept alive together produced 36 true results and 28 false results. Those are observed counts, not probabilities promised by Swift.
The distinction between the experiments matters:
| What stays alive? | What are we checking? |
|---|---|
| One set | Repeat lookup in the same table and hash context. |
| New short-lived sets | Storage may be released between attempts. |
| New sets kept alive | Separate tables without immediate storage reuse. |
| A fresh process | A new execution seed and new tables. |
The next program runs the first three cases and hashes the same string twice. It is sequential, so a data race is not part of this experiment. Your output can differ from the recorded sequence.
// ════════════════════════════════════════════════════════════════
// ▶ ARTICLE EXAMPLE: the code discussed in the article
// ════════════════════════════════════════════════════════════════
final class User: Hashable {
var id: Int
init(id: Int) { self.id = id }
static func == (lhs: User, rhs: User) -> Bool {
lhs.id == rhs.id
}
func hash(into hasher: inout Hasher) {
hasher.combine(id)
}
}
func shortLivedTables() -> String {
var results: [String] = []
for _ in 0..<10 {
let user = User(id: 1)
let users: Set<User> = [user]
user.id = 2
results.append(users.contains(user) ? "T" : "F")
}
return results.joined(separator: " ")
}
func retainedTables() -> String {
var tables: [Set<User>] = []
var users: [User] = []
for _ in 0..<64 {
let user = User(id: 1)
tables.append([user])
users.append(user)
}
for user in users { user.id = 2 }
return zip(tables, users).map { table, user in
table.contains(user) ? "T" : "F"
}.joined(separator: " ")
}
// ────────────────────────────────────────────────────────────────
// ◇ DEMO HARNESS: not part of the example. It only runs the code
// above and prints the result. Change it freely in the editor.
// ────────────────────────────────────────────────────────────────
import Foundation
print("▶ Start at \(Date.now)\n")
let user = User(id: 1)
let users: Set<User> = [user]
user.id = 2
let repeated = (0..<10).map { _ in
users.contains(user) ? "T" : "F"
}.joined(separator: " ")
print("One table: \(repeated)")
print("Short-lived tables: \(shortLivedTables())")
print("Retained tables: \(retainedTables())")
print("Same string, twice:")
print("Swift".hashValue)
print("Swift".hashValue)
// ▷ Try: run again; keep key-stability tests separate from these intentionally invalid lookups.
Starting configuration is the useful analogy here: the same input can be transformed differently under another configuration. Unlike advancing Enigma rotors, an unchanged Swift table does not switch its hash context on each lookup.
There really is a per-execution seed. Ordinary Hasher() uses it, and hashing the same components repeatedly in one execution produces the same result. Native collections add another input: NativeSet.hashValue(for:) passes _storage._seed when hashing an element.
In the source revision inspected here, normal table seeding uses the storage object’s address, which is combined with the execution seed. Copy-on-write copies can preserve an existing seed; new storage and resizing can establish a new one. That gives us a reason to distinguish repeated lookup from repeated table creation.
🔎 What to watch: Process seed is shared within this execution. Follow its combination with Table seed A and Table seed B. Repeated Lookup in one unchanged table reuses its context; creating another table can introduce a different one.
The important result is that new sets can give different answers within one process. It does not mean repeated lookups of the same unchanged table randomly alternate between true and false.
How this was tested: Swift 6.4.2, 20 runs, and limitations
The local experiment used Apple Swift 6.4.2 in Swift 6 language mode, both without optimization and with -O. Five fresh processes per configuration, with default and deterministic hashing, made 20 experimental processes. The browser runner may use another toolchain.
Repeated results in a short-lived loop are consistent with an allocator reusing released storage addresses. Addresses were not measured here, so this is an inference, not an allocator trace. Keeping 64 tables alive removes immediate reuse of their released storage as an explanation for that case.
The source links pin the inspected Swift revision. They do not claim that the installed Apple toolchain was built from that exact revision. These table-seeding details explain the observed behavior; stable equality and hash fields remain the rule the model must satisfy.
Randomization protects the table; it doesn’t repair a changed key
Do not persist hashValue as a cache key or database identity. For a business entity, store its stable identifier. For a content digest, choose a suitable stable algorithm, such as SHA-256, over a defined byte representation. Those solve different problems, and neither makes an in-place change to an indexed key safe.
The reason is the initial hashing configuration: the same value can receive another hashValue after a restart. The algorithm itself can also change between standard library versions; the inspected implementation uses SipHash-1-3. The Hasher documentation explicitly warns against reusing hash values across program executions.
For local diagnostics, launch the compiled program with:
SWIFT_DETERMINISTIC_HASHING=1 ./seed-experimentSet the variable before the process starts. In my deterministic runs, all the mutated-key membership checks returned false. That is another observation for this toolchain, not a new requirement to build into your tests. The variable changes seeding; the key mutation remains incorrect.
Decide what “the same user” means
Decide what your Set should treat as a duplicate. Two Account objects with the same stable ID usually represent one account, so the set should keep one of them. Two separate sessions for that user may be different elements even when their accountID values match. The choices below and the runnable example show how to preserve the uniqueness you need without tying lookup to a field you change.
| What must count as the same element? | Suitable representation |
|---|---|
| The same account, even when loaded as another instance | Equality and hashing based on a stable, immutable account ID. |
| A selected account’s ID, while its loaded data changes | A Set<User.ID> alongside separately stored models. |
| Exactly the same live object instance | === for equality and ObjectIdentifier(self) for hashing. |
| A value whose actual key must change | Remove it using the old key, change it, then insert it again in every affected collection. |
The next example contrasts the first and third choices. Change an account’s display name: its stable ID still makes a newly loaded equivalent account findable. Then change a session’s account ID: reference-based membership still recognizes that exact session, while a second session remains a different element.
// ════════════════════════════════════════════════════════════════
// ▶ ARTICLE EXAMPLE: the code discussed in the article
// ════════════════════════════════════════════════════════════════
final class Account: Hashable {
let id: Int
var displayName: String
init(id: Int, displayName: String) {
self.id = id
self.displayName = displayName
}
static func == (lhs: Account, rhs: Account) -> Bool {
lhs.id == rhs.id
}
func hash(into hasher: inout Hasher) {
hasher.combine(id)
}
}
final class Session: Hashable {
var accountID: Int
init(accountID: Int) { self.accountID = accountID }
static func == (lhs: Session, rhs: Session) -> Bool {
lhs === rhs
}
func hash(into hasher: inout Hasher) {
hasher.combine(ObjectIdentifier(self))
}
}
// ────────────────────────────────────────────────────────────────
// ◇ DEMO HARNESS: not part of the example. It only runs the code
// above and prints the result. Change it freely in the editor.
// ────────────────────────────────────────────────────────────────
import Foundation
print("▶ Start at \(Date.now)\n")
let account = Account(id: 1, displayName: "Jim")
let accounts: Set<Account> = [account]
account.displayName = "Jim Halpert"
let reloaded = Account(id: 1, displayName: "James")
print("Reloaded account found: \(accounts.contains(reloaded))")
let session = Session(accountID: 1)
let other = Session(accountID: 1)
let sessions: Set<Session> = [session, other]
session.accountID = 2
print("Separate sessions stored: \(sessions.count)")
print("Same session found: \(sessions.contains(session))")
print("New session found: \(sessions.contains(Session(accountID: 2)))")
// ▷ Try: give the reloaded account another ID, then compare it with the separate session behavior.Using ObjectIdentifier requires matching identity-based equality. Hashing by instance identity while comparing two different instances as equal by account ID would break the agreement between equality and hashing. Apple’s ObjectIdentifier documentation also limits meaningful identity comparisons to the instance’s lifetime; this is not a persistent account identifier.
A mutable class can be a perfectly useful set element when its equality-defining state is stable. Changing displayName is fine in the account example because that property participates in neither equality nor hashing. This says nothing about concurrent access: synchronization is a separate concern.
When testing a model like this, check that an equivalent freshly loaded account is found, that changing non-key fields preserves membership, and that separate identity-based objects remain separate. Test key changes through the collection operation that owns them. Avoid tests that require a particular numerical hash or a particular outcome after violating the key-stability requirement.
What to check in your own code:
- Open your type’s
==andhash(into:)implementations. List the properties they read, such asid. - For an account ID, make it immutable:
let id. Names and other fields may change if they do not participate in equality or hashing. - To track individual live instances, use
===together withObjectIdentifier(self), as in theSessionexample above. - If the actual key must change, first remove the object from every
SetorDictionarywhere it is an element or key. Only then change the field and insert it again. Decide beforehand what happens when the new ID is already taken: reject the change or keep one equal element. - In tests, check the element count and IDs as well as
contains. A non-key change should preserve membership; a controlled key change should not leave two equal stored elements.
Additional resources
- Cover photograph: Card catalogue drawers, Carolina Prysyazhnyuk, CC BY-SA 2.0. Resized and converted to WebP.
- Pigeon-loft photograph: Pigeons-in-holes, BenFrantzDale, CC BY-SA 3.0. Resized and converted to WebP.
- Enigma photograph: Enigma rotors with alphabet rings, TedColes, CC0 1.0. Resized and converted to WebP.
- Code examples in the online editor:
MutateInPlace.swift,RemoveThenInsert.swift,MutationLookup.swift,SeedExperiment.swift,IdentityModels.swift - Hashable: equal values hash the same essential components.
- ObjectIdentifier: identity during an instance’s lifetime.
- Swift NativeSet lookup implementation.
- Swift HashTable bucket mapping and table seeding.
- Hasher: execution seed and persistence restrictions.
- SipHash implementation and seed combination.
- Runtime initialization and deterministic hashing.
- SE-0206: Hashable Enhancements.
- Apple’s Swift 4.2 release notes: randomized hashing and Hasher.
- Karoy Lorentey on hashing in Swift 4.1 and 4.2.
- Hasher: do not persist hashes across executions.
- SHA256 in CryptoKit.
Discussion
Comment translation
No languages found.