Equality and Hashing
Master the full equality and hashing contract in Objective-C: the difference between identity and value equality, why isEqual: and hash must always be overridden together, how NSSet and NSDictionary depend on that contract internally, and the specific, easy-to-miss hazard of mutating an object's hash-relevant state after it has already been inserted into a hash-based collection.
The NSObject Fundamentals lesson introduced isEqual: and hash briefly, as two of NSObject's foundational methods, and promised the full depth would come in this dedicated lesson -- this is that lesson. Equality and hashing look, on the surface, like a small, self-contained topic: override two methods, get value-based comparisons instead of pointer comparisons, done. In practice, the contract between isEqual: and hash is one of the easiest things in Objective-C to get subtly wrong, and getting it wrong doesn't produce a compiler warning or an obvious crash -- it produces a collection that silently, intermittently fails to find objects it should find. This lesson works through the full contract precisely, with a complete worked example, so that pattern becomes recognizable and preventable rather than something discovered by debugging a mysterious lookup failure days later.
Identity Equality vs Value Equality
Objective-C, like the C it's built on, has a built-in notion of identity equality: == compares two pointers directly, and it answers YES only when both sides refer to the literal same object in memory -- the same allocation, the same address. Two entirely separate NSString instances that happen to hold the identical text "hello" are not == to each other, because they're two different objects, even though what they represent is indistinguishable.
Value equality is a different, higher-level question -- 'do these two objects represent the same content,' regardless of whether they're the same physical object -- and Objective-C has no built-in way to answer it generically, because 'same content' means something different for every class. isEqual: is NSObject's hook for exactly this: a method every class can override to define what value equality means for its own instances, and which, for built-in classes like NSString and NSArray, already does the content comparison you'd expect out of the box.
The two are not interchangeable and answering the wrong one for a given piece of logic is a common source of bugs: code that means 'do these represent the same value' but accidentally uses == gets pointer comparison instead, silently failing to match two logically-equal-but-distinct instances; code that means 'is this literally the same object I stored earlier' but uses isEqual: risks matching an unrelated object that merely happens to compare equal by content.
• == is identity equality: true only when both sides are the literal same object in memory (the same pointer/address). • isEqual: is value (content) equality: true when two objects represent the same content, even as separate instances. • Built-in classes like NSString and NSArray already implement content-based isEqual: -- custom model classes must opt in explicitly by overriding it. • Using == when value equality is meant (or isEqual: when identity is meant) is a real, common source of bugs.
isEqual: and hash: The Contract
isEqual: takes another object and returns a BOOL: YES if the receiver considers itself equal to that object, NO otherwise. A correct override typically checks that the other object is of a compatible class (commonly with isKindOfClass:, covered in the sibling NSObject Fundamentals lesson) and then compares whatever fields actually define that class's notion of equality.
hash returns an NSUInteger meant to summarize an object's content into a single number, used internally by hash-based collections to group objects into buckets for fast lookup -- covered concretely in the next section. The rule accompanying this lesson's diagram states the entire contract in one line: if A is equal to B (by isEqual:), then A.hash must equal B.hash. This direction only -- equal objects must have equal hashes; it does NOT require the reverse, and two UNEQUAL objects are allowed to share the same hash value (a 'hash collision'), which hash-based collections are already designed to handle correctly as long as the equal-implies-equal-hash direction holds.
This is exactly why isEqual: and hash must always be overridden as a pair, never just one: overriding isEqual: alone leaves the default NSObject hash in place, which is typically based on the object's memory address -- so two objects your new isEqual: correctly considers equal will, in general, still report different hash values, violating the contract. Overriding hash alone without a matching isEqual: is equally broken, just less obviously so, because the default isEqual: still only ever compares by identity.
• isEqual: defines what content-equality means for a class; hash summarizes that same content into an NSUInteger for fast bucketing. • The contract: if A isEqual: B is YES, then A.hash must equal B.hash -- this direction only. • Two unequal objects sharing the same hash (a collision) is allowed and expected; collections handle that correctly on their own. • Overriding only one of the pair leaves the other using its default (identity-based) behavior, breaking the contract silently.
How NSSet and NSDictionary Actually Use Hash and Equality
NSSet and NSDictionary are hash-based collections: internally, they organize their contents into buckets keyed by hash value, so that checking whether an object is already present -- or finding a dictionary value for a given key -- doesn't require comparing against every stored element one by one. When asked to look up an object, the collection first computes that object's hash to jump directly to the bucket where a matching element, if present, must live, and only then uses isEqual: to compare against the (typically small number of) candidates already in that bucket.
This two-step process is exactly why the contract matters so precisely: if an object's hash changes, or was wrong to begin with, relative to what it was when inserted, the collection will look in the wrong bucket entirely and never find a match via isEqual: at all -- not because isEqual: itself is broken, but because the lookup never gets as far as calling it on the right candidate. An object can be, by every definition of isEqual:, present in a set, and a naive membership check can still return NO, simply because the bucket the check computes doesn't match the bucket the object was actually filed under.
This mechanism is also exactly why the equal-implies-equal-hash direction (and not the reverse) is the only thing required: two equal objects MUST land in the same bucket (same hash) so isEqual: within that bucket can find the match, but two unequal objects landing in the same bucket by coincidence is harmless -- isEqual: within that bucket simply says NO for that pair, and the search continues normally to any other candidates sharing the bucket.
• NSSet/NSDictionary bucket their contents by hash value first, then use isEqual: only to compare within the small set of candidates in the matching bucket. • A lookup computes the SEARCHED object's hash to find the bucket to check -- it never compares against every stored element directly. • If an object's hash is wrong or has changed since insertion, lookup checks the wrong bucket and never reaches isEqual: on the actual match. • Equal objects must share a bucket (equal hash); unequal objects sharing a bucket by coincidence is harmless and handled correctly.
A Complete Custom Model Class, Correctly Overriding Both
The worked example accompanying this lesson defines a Coordinate class holding two integer fields and overrides both isEqual: and hash together, deriving both from exactly the same fields -- x and y. This pairing is the entire pattern to internalize: whatever fields isEqual: compares are precisely the fields hash must be derived from, so that any two Coordinate instances isEqual: considers equal are mathematically guaranteed to also produce the same hash value.
A correct isEqual: override also has to handle a few edge cases beyond the simple field comparison: it should check for exact pointer equality first as a fast path (an object is always equal to itself), it should return NO -- never crash -- if the other object is nil or isn't a compatible class, and if a class overrides isEqual:, it is also expected to override the NSObject protocol method isEqual: consistently with -hash on the same object across the object's lifetime for as long as it's stored in a hash-based collection, which leads directly into the mutation hazard covered next.
It's worth being explicit about why this discipline matters even for simple value classes that feel like they'd 'obviously' behave correctly: without any override at all, two logically identical Coordinate instances are NOT isEqual: to each other (NSObject's default is identity-based), so inserting one into an NSSet and then checking containment with a separate-but-equal-by-value instance would silently return NO -- exactly the kind of bug that's easy to miss in testing and painful to track down in production.
• Derive hash from exactly the same fields isEqual: compares -- never more, never fewer, never different ones. • A robust isEqual: checks pointer equality first, handles nil/incompatible-class gracefully (return NO, don't crash), then compares fields. • Without any override, NSObject's defaults are identity-based -- two value-identical custom objects are NOT considered equal, and a set/dictionary lookup between separate instances silently fails.
Mutable Keys and Collection Hazards
The most dangerous consequence of the hash contract shows up not from a bad override, but from a correct override used incorrectly: mutating an object's hash-relevant fields AFTER it has already been inserted into an NSSet or used as an NSDictionary key silently corrupts that collection's internal bucket structure. The object was filed into a bucket based on its hash at insertion time; changing the fields hash is derived from changes what hash would now be computed for that object, but the collection has no way to know that happened and does not re-bucket the object automatically.
The practical result is an object that's still physically present in the collection, but effectively unreachable through the collection's own normal lookup path: a subsequent containsObject: check (for a set) or a dictionary lookup with an equal key computes the object's NEW hash, looks in the bucket that new hash points to, and doesn't find it there, because it's still sitting in the OLD bucket its OLD hash put it in. Even enumerating the whole collection may not behave as expected in some internal-consistency-checking code paths, and removing the object correctly can become impossible through ordinary means, because removal, too, relies on the same hash-driven bucket lookup that insertion did.
The rule that follows is absolute, not a style preference: never mutate any field an object's hash (and therefore its isEqual:) depends on while that object is a member of an NSSet, a key in an NSDictionary, or inside any other hash-based collection. If a value genuinely needs to change, the safe pattern is to remove the object from the collection first, mutate it, and then re-insert it -- which lets the collection correctly re-bucket it under its new hash.
• Mutating a hash-relevant field after insertion into a set/dictionary corrupts the collection's internal bucket structure silently. • The object stays present physically, but lookup by its new hash checks the wrong bucket and doesn't find it -- and removal through ordinary means can fail the same way. • The rule: never mutate hash-affecting fields while an object is a live member/key of a hash-based collection. • Safe pattern: remove the object first, mutate it, then re-insert it, so it's correctly re-bucketed under its new hash.
Code Examples
a and b are deliberately built as two separate NSString instances that happen to hold identical text. == compares pointers and correctly reports they're not the same object; isEqual: compares content and correctly reports they're equal by value -- this is the exact distinction 'identity vs value equality' refers to.
BOOL equalValue = [a isEqual:b]; // YES -- same content, "hello" isEqual: checks pointer equality first as a fast path, then gracefully handles a non-Coordinate or nil other by returning NO instead of crashing, and finally compares exactly the two fields (x and y) that define Coordinate's notion of equality. hash is derived from those same two fields, guaranteeing that any two Coordinate instances isEqual: considers equal will always produce equal hash values, satisfying the contract.
return (NSUInteger)(self.x * 31 + self.y);
Without the correctly paired isEqual:/hash override, this containsObject: check would return NO, because lookup and the originally inserted Coordinate are different objects. With the pairing in place, lookup's hash correctly matches the bucket the original was filed under, and isEqual: confirms the match within that bucket -- exactly the two-step process the earlier section describes.
BOOL found = [visited containsObject:lookup]; // YES point was correctly bucketed when it was inserted, based on its hash at that moment. Mutating point.x afterward changes what hash it would now compute, but NSMutableSet has no way to detect that and does not re-bucket it -- point is still sitting in its old bucket, unreachable by any lookup that (correctly) computes its new hash first. This is exactly the mutable-keys-and-collection-hazards danger this lesson's rules section warns about.
point.x = 99; // hash-relevant field changed AFTER insertion
Common mistake: Mutating a field that hash and isEqual: depend on while the object is still a member of an NSSet or a key in an NSDictionary.
NSString *a = [NSString stringWithFormat:@"%@", @"hello"];
NSString *b = [NSString stringWithFormat:@"%@", @"hello"];
BOOL identical = (a == b); // NO -- two separate NSString instances
BOOL equalValue = [a isEqual:b]; // YES -- same content, "hello"@interface Coordinate : NSObject
@property (nonatomic, readonly) NSInteger x;
@property (nonatomic, readonly) NSInteger y;
- (instancetype)initWithX:(NSInteger)x y:(NSInteger)y;
@end
@implementation Coordinate
- (instancetype)initWithX:(NSInteger)x y:(NSInteger)y {
if (self = [super init]) {
_x = x;
_y = y;
}
return self;
}
- (BOOL)isEqual:(id)other {
if (self == other) return YES;
if (![other isKindOfClass:[Coordinate class]]) return NO;
Coordinate *o = (Coordinate *)other;
return self.x == o.x && self.y == o.y;
}
- (NSUInteger)hash {
// Derived from exactly the same fields isEqual: compares -- never
// more, never fewer, never different ones.
return (NSUInteger)(self.x * 31 + self.y);
}
@endNSMutableSet<Coordinate *> *visited = [NSMutableSet set];
[visited addObject:[[Coordinate alloc] initWithX:3 y:4]];
Coordinate *lookup = [[Coordinate alloc] initWithX:3 y:4];
BOOL found = [visited containsObject:lookup]; // YES
// 'lookup' is a SEPARATE instance from the one inserted, but because
// isEqual: and hash are both correctly overridden and consistent,
// NSSet finds it via the exact bucket its hash points to.@interface MutableCoordinate : NSObject
@property (nonatomic) NSInteger x; // NOT readonly -- can be changed later
@property (nonatomic) NSInteger y;
@end
@implementation MutableCoordinate
- (BOOL)isEqual:(id)other {
if (self == other) return YES;
if (![other isKindOfClass:[MutableCoordinate class]]) return NO;
MutableCoordinate *o = (MutableCoordinate *)other;
return self.x == o.x && self.y == o.y;
}
- (NSUInteger)hash { return (NSUInteger)(self.x * 31 + self.y); }
@end
MutableCoordinate *point = [[MutableCoordinate alloc] init];
point.x = 3; point.y = 4;
NSMutableSet<MutableCoordinate *> *visited = [NSMutableSet set];
[visited addObject:point]; // filed into a bucket based on hash for (3,4)
// LATER, while 'point' is still a member of 'visited':
point.x = 99; // hash-relevant field changed AFTER insertion
BOOL stillFound = [visited containsObject:point];
// UNDEFINED IN PRACTICE -- 'point' is still physically in the set, but
// its hash has changed, so a lookup now checks the WRONG bucket. The
// collection's internal structure is now silently corrupted.The Equality / Hash Contract
The entire contract in one line, and the only direction that's required: whenever isEqual: says two objects are equal, their hash values must also be equal -- because NSSet and NSDictionary use hash first to find the bucket a lookup should even check, before isEqual: ever gets a chance to confirm the match within that bucket.
If A is equal to B
↓
A.hash == B.hashImportant Rules
If A is equal to B (A isEqual:B returns YES), then A.hash must equal B.hash -- this direction only; unequal objects may share a hash value with no problem.
Always override isEqual: and hash together, deriving hash from exactly the same fields isEqual: compares -- never override just one.
Never mutate an object's hash-relevant fields while it is a member of an NSSet or a key in an NSDictionary -- remove it, mutate it, then re-insert it instead.
Where This Actually Bites in Practice
This exact hazard shows up whenever a model object doubles as a dictionary key or set member and something else in the codebase later mutates one of its properties -- a cache keyed by a mutable request object, a set of 'visited' model instances where a property gets updated in place after insertion, or a dictionary keyed by an NSMutableString or NSMutableArray whose contents change after being used as a key (both of which override isEqual:/hash based on their current, mutable contents, making them exactly this hazard by design if used as keys). The defensive pattern -- use immutable value types (or defensively copy) for anything that will serve as a hash-based key, and if mutation is unavoidable, always remove before mutating and re-insert after -- prevents an entire class of bugs that otherwise surface as maddeningly intermittent 'the object should be in there, but the lookup says it isn't' reports, exactly the failure mode the NSSet / NSMutableSet and NSDictionary / NSMutableDictionary lessons' own key-safety guidance is built around.
MutableCoordinate *point = [[MutableCoordinate alloc] init]; point.x = 3; point.y = 4; [visited addObject:point]; // Later: point.x = 99; // mutated while still a member of 'visited'
MutableCoordinate *point = [[MutableCoordinate alloc] init]; point.x = 3; point.y = 4; [visited addObject:point]; // To change x safely, remove first, mutate, then re-insert: [visited removeObject:point]; point.x = 99; [visited addObject:point]; // re-bucketed correctly under the new hash
Removing the object before mutating it, and re-inserting it afterward, gives NSMutableSet the chance to correctly re-bucket it based on its new hash. Mutating it in place while it remains a member silently leaves it filed under its stale, no-longer-accurate hash, corrupting the set's internal structure without any error or warning at the point the mutation happens.
What is the fundamental difference between == and isEqual: in Objective-C? A. They are exact synonyms with no functional difference B. == compares object pointers (identity -- the literal same object); isEqual: compares content (value equality), and its behavior is defined per class C. isEqual: is faster than == in all cases D. == only works on primitive types, never on objects
B. == compares object pointers (identity -- the literal same object); isEqual: compares content (value equality), and its behavior is defined per class — == is C-level pointer comparison, always identity-based. isEqual: is a method whose behavior a class defines (or inherits NSObject's default identity-based behavior from) -- it's the hook for value/content equality.
According to the equality/hash contract, what MUST be true if A isEqual:B returns YES? A. A and B must be the exact same object in memory B. A.hash must equal B.hash C. A and B must belong to different classes D. A.hash must be strictly less than B.hash
B. A.hash must equal B.hash — The contract requires equal-implies-equal-hash: if isEqual: says two objects are equal, their hash values must match, because hash-based collections use hash to locate the bucket a lookup should even check before isEqual: is consulted.
Why must isEqual: and hash always be overridden together rather than just one of them? A. Overriding just one is always fine as long as the class never touches NSSet or NSDictionary B. Overriding only one leaves the other using NSObject's default (identity-based) behavior, breaking the contract between them and silently corrupting hash-based collection lookups C. The compiler will refuse to compile a class that overrides only one of the pair D. hash is automatically derived from isEqual: by the compiler, so overriding hash separately is redundant but harmless
B. Overriding only one leaves the other using NSObject's default (identity-based) behavior, breaking the contract between them and silently corrupting hash-based collection lookups — If only isEqual: is overridden, hash still falls back to NSObject's default (typically address-based), so two objects your isEqual: considers equal can still report different hashes -- violating the contract and breaking NSSet/NSDictionary lookups in ways that don't produce any compiler warning.
Why does mutating an object's hash-relevant fields AFTER inserting it into an NSMutableSet corrupt the set's internal structure? A. It doesn't -- NSMutableSet automatically re-buckets any member whenever its fields change B. The object was filed into a bucket based on its hash at insertion time; mutating it changes what hash it would now compute, but the set has no way to detect the change and doesn't re-bucket it, leaving it unreachable by lookups using its new hash C. Mutating any property of any object in a set throws a runtime exception immediately D. NSMutableSet stores a deep copy at insertion, so mutating the original object afterward has no effect on the set at all
B. The object was filed into a bucket based on its hash at insertion time; mutating it changes what hash it would now compute, but the set has no way to detect the change and doesn't re-bucket it, leaving it unreachable by lookups using its new hash — NSSet/NSDictionary bucket by hash at insertion time and never watch for later mutations. A hash-relevant mutation after insertion leaves the object stuck in its old, now-inconsistent bucket -- lookups computing its new hash check a different bucket and silently fail to find it.
Is it a contract violation for two UNEQUAL objects (isEqual: returns NO) to share the same hash value? A. Yes -- unequal objects must always have different hash values, or the collection breaks B. No -- this is an allowed hash collision, and hash-based collections are already designed to handle it correctly using isEqual: within a shared bucket C. It depends entirely on which specific subclass of NSObject is involved D. It is only allowed for NSString instances, never for custom classes
B. No -- this is an allowed hash collision, and hash-based collections are already designed to handle it correctly using isEqual: within a shared bucket — The contract only requires equal-implies-equal-hash, not the reverse. Two unequal objects landing in the same hash bucket is an ordinary, expected collision that isEqual: resolves correctly within that bucket -- it causes no corruption or incorrect behavior.
A Tag class has a mutable NSString *name property and overrides isEqual: and hash based on name's value. Write a short scenario, using a NSMutableSet<Tag *>, where inserting a Tag, later renaming it via its name property, and then calling containsObject: with a freshly created Tag holding the NEW name value returns NO even though a Tag with that exact name is, in some sense, present in the set. Then show the fix.
Tag *tag = [[Tag alloc] init]; tag.name = @"draft";\nNSMutableSet<Tag *> *tags = [NSMutableSet set];\n[tags addObject:tag]; // bucketed under hash("draft")\n\ntag.name = @"published"; // mutated IN PLACE while still a member\n\nTag *lookup = [[Tag alloc] init]; lookup.name = @"published";\nBOOL found = [tags containsObject:lookup]; // NO -- wrong bucket checked\n\n// Fix: remove before mutating, re-insert after:\n[tags removeObject:tag]; // must be done BEFORE renaming, using the OLD name's hash\ntag.name = @"published";\n[tags addObject:tag]; // now correctly re-bucketed under hash("published")\nfound = [tags containsObject:lookup]; // YES
The set buckets by the OLD name's hash at insertion time; renaming the tag in place changes what its hash would now be, but the set doesn't know to re-bucket it -- so a lookup by the NEW name checks a bucket the tag was never filed under.