NSSet and NSMutableSet: Unordered Uniqueness
Understand how NSSet and NSMutableSet store unordered collections of unique objects, why uniqueness depends on isEqual: and hash rather than identity, and when a set is the right tool instead of an array.
So far every collection you've studied in Foundation — NSArray, NSDictionary's values — has cared about order or key-based lookup. NSSet introduces a different kind of collection entirely: one that guarantees every element is unique and makes no promises whatsoever about order. That single property, uniqueness without order, makes NSSet the right tool for an entire category of problems — deduplication, fast membership testing, and set algebra — that would be awkward and slow to solve with NSArray. This lesson covers NSSet and its mutable subclass NSMutableSet in depth, including the mechanics of uniqueness itself, which trip up more Objective-C programmers than almost anything else in Foundation.
What makes a set a set
An NSSet is an unordered collection of distinct objects. "Distinct" is the operative word: when you add an object to a set, the set first checks whether an object considered equal to it is already present, and if so, the add is silently ignored. This is fundamentally different from NSArray, which happily stores the same value ten times if you ask it to, in the exact order you inserted it.
Because a set has no concept of order, it has no indexed access — there is no objectAtIndex: method, and enumerating a set (with a for-in loop or an NSEnumerator) can visit elements in any order, including an order that changes between two enumerations of what looks like the same set. If you need index 0, index 1, and so on, a set is the wrong collection; reach for NSArray or, when you need both uniqueness and order, NSOrderedSet (covered in the next lesson).
NSSet is the immutable base class — once created, its contents cannot change. NSMutableSet is its mutable subclass, adding addObject: and removeObject: so you can grow and shrink the collection after creation. This immutable/mutable split is the same pattern Foundation uses throughout: NSArray/NSMutableArray, NSDictionary/NSMutableDictionary, and now NSSet/NSMutableSet all follow it.
Uniqueness is determined by isEqual: and hash, not identity
This is the single most important — and most frequently misunderstood — fact about NSSet: two objects are considered "the same" for membership purposes not because they are the same object in memory (pointer identity), but because [objectA isEqual:objectB] returns YES. Two entirely separate NSString instances holding the text @"hello" are different objects at different memory addresses, yet a set will treat them as duplicates, because NSString implements isEqual: to compare character content rather than pointer identity.
Internally, NSSet doesn't call isEqual: against every existing element every time you add something — that would make sets no faster than arrays. Instead, it uses a hash table: every object supplies a hash (via the hash method), and the set uses that hash value to jump almost directly to the small bucket of objects that might be equal, only then falling back to isEqual: to confirm a true match. This is exactly why NSSet's containsObject: is, on average, an O(1) operation rather than the O(n) linear scan NSArray must perform.
This hash-then-compare strategy is also why isEqual: and hash must always be implemented together and must always agree: Foundation's contract requires that if [a isEqual:b] returns YES, then a.hash must equal b.hash. If you override isEqual: on a custom class to compare, say, two Person objects by their employee ID, but forget to override hash to derive from that same employee ID, you break the contract. The set may compute different hash values for two "equal" Person objects, causing it to check different buckets, never call isEqual: to compare them, and silently allow both into the set as if they were distinct. The bug doesn't crash — it just quietly produces a set with duplicates that shouldn't exist, which is often far worse because it goes unnoticed.
For Foundation's built-in value classes — NSString, NSNumber, NSDate, NSArray, NSDictionary — isEqual: and hash are already implemented consistently and correctly, comparing by value. You only need to worry about this contract when you put your own custom Objective-C objects into a set (or use them as dictionary keys, which relies on the identical mechanism).
Creating sets and testing membership
NSSet offers convenience constructors mirroring NSArray's: setWithArray: builds a set from an existing array (automatically discarding any duplicates the array contained), and setWithObjects: takes a nil-terminated list of objects directly. Both return an autoreleased, immutable NSSet.
Membership testing is where sets earn their keep. containsObject: on an NSSet is, on average, a constant-time O(1) operation thanks to the hash table underneath. Compare that to NSArray's containsObject:, which must walk the array from the start, calling isEqual: against each element until it finds a match or reaches the end — an O(n) linear scan. For a collection of a few dozen items the difference is invisible; for a collection of tens of thousands of items checked repeatedly (say, checking "have I already processed this ID?" inside a loop), the difference between O(1) and O(n) membership checks is the difference between an app that feels instant and one that visibly stalls.
This performance gap is one of the strongest, most concrete reasons to reach for NSSet over NSArray: whenever your code's dominant operation is "is this object already in my collection?" rather than "give me the object at this position" or "preserve the order I added things in," a set is very likely the better data structure.
Set algebra: intersect, union, and minus
Because sets model mathematical sets, Foundation gives them mathematical set operations. NSSet itself provides a read-only query, intersectsSet:, which returns YES if the receiver and another set share at least one element in common — useful for a quick yes/no overlap check without building a new collection.
NSMutableSet adds three in-place operations that actually mutate the receiver to become the result of a set operation: intersectSet: reduces the receiver down to only the elements also present in the argument set (set intersection, A ∩ B); unionSet: adds every element of the argument set that isn't already present (set union, A ∪ B); and minusSet: removes from the receiver any element that is present in the argument set (set difference, A − B). Each of these mutates the receiving mutable set directly rather than returning a new set, so if you need to keep the original untouched, make a mutable copy first with [set mutableCopy].
When to choose a set over an array
Reach for NSSet or NSMutableSet when three conditions line up: you need to repeatedly ask "is this object already here?", you don't care about the order elements were added in, and you want automatic deduplication rather than having to write your own containsObject: check before every insert. A tag system, a set of already-visited URLs, a collection of unique user IDs that have RSVP'd to an event — these are all natural fits for a set, where an array would force you to either tolerate duplicates or pay for a linear scan on every single insertion just to check first.
• Choose NSSet/NSMutableSet: fast membership checks, no ordering requirement, automatic deduplication desired • Choose NSArray/NSMutableArray: insertion order matters, indexed access is needed, duplicates are meaningful or expected
Code Examples
rawTags has five elements but two duplicate pairs; setWithArray: collapses it down to three unique tags automatically, since NSString compares by character content via isEqual:. containsObject: then answers the membership question in O(1) average time rather than scanning. Expected result: Unique tag count: 3 Post is tagged objc manualSet has 3 colors
NSSet *uniqueTags = [NSSet setWithArray:rawTags]; — duplicates in the source array vanish automatically because equal strings collapse to one element.
This demonstrates all four set operations. intersectsSet: gives a cheap yes/no check without allocating anything new. The three NSMutableSet operations mutate the receiver in place, which is why the code makes a mutableCopy of loggedInToday before each destructive operation — otherwise the original set would be permanently altered by intersectSet:, unionSet:, or minusSet:. Expected result: At least one premium user logged in today Premium + logged in: {( bob )} Everyone (union): 5 people Logged in, not premium: {( alice, carol )}
[premiumWhoLoggedIn intersectSet:premiumUsers]; mutates premiumWhoLoggedIn in place to become the intersection — it does not return a new set.
addObject:@42 is called twice, but since @42 (an NSNumber) already isEqual: an existing element the second time, the set silently ignores the duplicate add rather than raising an error or growing the count — contrast this with NSCountedSet later in this module, where a repeated add is tracked rather than ignored. Expected result: Visited count: 2 After removal: {( 42 )}
[visitedIDs addObject:@42]; the second time is a silent no-op because an equal object is already present.
NSArray *rawTags = @[@"swift", @"objc", @"swift", @"ios", @"objc"];
NSSet *uniqueTags = [NSSet setWithArray:rawTags];
NSLog(@"Unique tag count: %lu", (unsigned long)uniqueTags.count);
if ([uniqueTags containsObject:@"objc"]) {
NSLog(@"Post is tagged objc");
}
NSSet *manualSet = [NSSet setWithObjects:@"red", @"green", @"blue", nil];
NSLog(@"manualSet has %lu colors", (unsigned long)manualSet.count);NSMutableSet *loggedInToday = [NSMutableSet setWithObjects:@"alice", @"bob", @"carol", nil];
NSSet *premiumUsers = [NSSet setWithObjects:@"bob", @"dave", @"erin", nil];
if ([loggedInToday intersectsSet:premiumUsers]) {
NSLog(@"At least one premium user logged in today");
}
NSMutableSet *premiumWhoLoggedIn = [loggedInToday mutableCopy];
[premiumWhoLoggedIn intersectSet:premiumUsers];
NSLog(@"Premium + logged in: %@", premiumWhoLoggedIn);
NSMutableSet *everyone = [loggedInToday mutableCopy];
[everyone unionSet:premiumUsers];
NSLog(@"Everyone (union): %lu people", (unsigned long)everyone.count);
NSMutableSet *nonPremiumLogins = [loggedInToday mutableCopy];
[nonPremiumLogins minusSet:premiumUsers];
NSLog(@"Logged in, not premium: %@", nonPremiumLogins);NSMutableSet *visitedIDs = [NSMutableSet set];
[visitedIDs addObject:@42];
[visitedIDs addObject:@17];
[visitedIDs addObject:@42]; // duplicate: silently ignored, count stays at 2
NSLog(@"Visited count: %lu", (unsigned long)visitedIDs.count);
[visitedIDs removeObject:@17];
NSLog(@"After removal: %@", visitedIDs);Array scan vs set hash lookup
An array must potentially inspect every element to answer "is x present?"; a set uses x's hash to jump almost directly to the right bucket, then confirms with isEqual:.
NSArray containsObject: (O(n))
[ a ][ b ][ c ][ d ][ e ] ... check each, left to right
NSSet containsObject: (O(1) average)
hash(x) ──▶ bucket 3 ──▶ [ x ] (isEqual: confirms match)Important Rules
NSSet stores unique, unordered elements; uniqueness is determined by isEqual:, not pointer identity.
Always implement hash alongside isEqual: on custom classes — equal objects (isEqual: returns YES) must produce equal hash values, or set/dictionary behavior silently breaks.
containsObject: on NSSet is O(1) average; on NSArray it is O(n) — this is the strongest reason to choose a set when membership testing dominates.
NSMutableSet's intersectSet:, unionSet:, and minusSet: mutate the receiver in place; copy first if you need to preserve the original.
addObject: on a duplicate is a silent no-op on NSSet — it does not raise an exception and does not change the count.
Deduplicating and cross-referencing data
Sets show up constantly in real apps wherever the phrase "unique" appears in a spec: a set of hashtags on a post, a set of already-downloaded asset IDs so a sync routine never fetches the same file twice, a set of feature flags currently enabled for a user, or a set of blocked user IDs checked on every incoming message. Set algebra is equally common in analytics and access-control code — computing which users are in both group A and group B (intersectSet:), which users are in either group (unionSet:), or which users are in A but were removed from B (minusSet:) are all one-line operations once the data lives in NSSet form, instead of nested loops over arrays.
Enumerating an NSSet and assuming the elements come back in insertion order (e.g. expecting the first object added to be the first one enumerated).
Treat NSSet's enumeration order as unspecified and potentially different between runs; if order matters, use NSArray or NSOrderedSet instead.
NSSet makes no ordering guarantee whatsoever — its internal hash-table layout, not insertion order, determines enumeration order, and that layout can even change as the set grows.
Overriding isEqual: on a custom class to compare by a business key (like an ID) but leaving hash as the default (identity-based) implementation.
Override hash to derive from the exact same fields used in isEqual:, so that two objects considered equal always produce the same hash value.
If hash and isEqual: disagree, a set can place two "equal" objects into different hash buckets, never compare them with isEqual:, and end up storing both — silently defeating the whole purpose of using a set.
Calling intersectSet:/unionSet:/minusSet: directly on a set you still need in its original form.
Make a mutableCopy of the set first, then perform the destructive operation on the copy.
These three NSMutableSet methods mutate the receiver in place rather than returning a new set; calling them on the only reference you have to the original data permanently alters it.
What determines whether two objects are considered duplicates when added to an NSSet? A. Whether they occupy the same memory address (pointer identity) B. Whether isEqual: returns YES between them, backed by a consistent hash C. Whether they were added in the same method call D. Whether their class names match exactly
B. Whether isEqual: returns YES between them, backed by a consistent hash — NSSet determines uniqueness via isEqual: (accelerated by hash for lookup), not pointer identity — two separate object instances that compare equal are treated as duplicates.
Why must isEqual: and hash be implemented together and stay consistent on a custom class? A. Because Objective-C requires every class to implement both methods or it won't compile B. Because if equal objects produce different hash values, a set may never call isEqual: to compare them and can end up storing duplicates C. Because hash is only used for printing objects with NSLog D. Because NSMutableSet ignores isEqual: entirely and relies solely on hash
B. Because if equal objects produce different hash values, a set may never call isEqual: to compare them and can end up storing duplicates — A set uses hash to find the bucket of candidate matches and only then calls isEqual: to confirm. If equal objects hash differently, they can land in different buckets and never get compared, breaking uniqueness silently.
What is the average time complexity of containsObject: on an NSSet, compared to NSArray? A. Both are O(n); sets offer no performance advantage for membership testing B. NSSet is O(1) average via its hash table; NSArray is O(n) because it must scan sequentially C. NSSet is O(n log n); NSArray is O(1) D. Both are O(1) because Foundation caches all lookups
B. NSSet is O(1) average via its hash table; NSArray is O(n) because it must scan sequentially — NSSet's hash-table implementation gives average O(1) membership testing, while NSArray must potentially inspect every element in order, giving O(n) — a major reason to prefer a set when membership checks dominate.
What happens when you call addObject: on an NSMutableSet with an object that isEqual: an element already present? A. The set raises an NSInvalidArgumentException B. The object is added again, so the set now contains two equal elements C. The call is silently ignored and the set's contents and count are unchanged D. The existing element is replaced with the new one, changing its identity
C. The call is silently ignored and the set's contents and count are unchanged — NSSet enforces uniqueness by silently ignoring an add that would create a duplicate — the count does not change and no exception is raised, unlike NSCountedSet, which would increment a count instead.
You need to keep an existing NSMutableSet unchanged while also computing its intersection with another set. What should you do? A. Call intersectSet: directly on the original set, since it returns a new set without modifying the receiver B. Make a mutableCopy of the original set first, then call intersectSet: on the copy C. Convert both sets to arrays and use isEqualToArray: D. Use intersectsSet: instead, since it returns the intersection as a new set
B. Make a mutableCopy of the original set first, then call intersectSet: on the copy — intersectSet: (like unionSet: and minusSet:) mutates the receiver in place. To preserve the original set, operate on a mutableCopy instead. intersectsSet: (note the different name) only returns a YES/NO overlap check, not a new set.
Given an NSArray of NSString order IDs that may contain duplicates (some orders were double-submitted), produce an NSSet of the unique order IDs, then write a check using containsObject: to see whether a specific order ID (say @"ORD-1042") was among them.
NSArray *rawOrders = @[@"ORD-1001", @"ORD-1042", @"ORD-1001", @"ORD-1099"]; NSSet *uniqueOrders = [NSSet setWithArray:rawOrders]; BOOL found = [uniqueOrders containsObject:@"ORD-1042"]; NSLog(@"Unique orders: %lu, found target: %@", (unsigned long)uniqueOrders.count, found ? @"YES" : @"NO");
setWithArray: is the one-line way to both deduplicate and convert; containsObject: is your O(1) average membership check.