Equality

Written by Mattt (revised)
This article has been translated into:
中文

The concept of equality is a central topic in philosophy and mathematics, with far-reaching implications for matters of ethics, justice, and public policy.

From an empiricist perspective of the universe, two objects are equal if they’re indistinguishable by measurable observation. On a human scale, egalitarians hold that individuals should be considered equal members of the societal, economic, political, and judicial systems they inhabit.

Our task as programmers is to reconcile our logical and physical understanding of equality with the domains we model. And to do this correctly, we must start from a place of understanding.

So I invite you to take a moment to consider these broader questions; resist the urge to skim this article in search of relevant-looking code to copy-paste verbatim. Equality in Objective-C is a topic that remains a frequent source of confusion and deserves our full and undivided attention.

Equality & Identity

First and foremost, let’s make a distinction between equality and identity.

Two objects may be equal or equivalent to one another if they share a common set of observable properties. Yet those two objects may be thought to be distinct, each with their own identity.

In Objective-C, an object’s identity is tied to its memory address. When you use the == operator to compare two objects in Objective-C, you’re checking to see if they point to the same location in memory.

NSObject and its subclasses designate the isEqual: method to determine equality between two objects. In its base implementation, an equality check simply tests for equal identity:

NSObject *a = [NSObject new];
NSObject *b = [NSObject new];

BOOL objectsHaveSameIdentity = (a == b); // NO
BOOL objectsAreEqual = ([a isEqual:b]); // NO

However, some NSObject subclasses override isEqual: and thereby redefine the criteria for equality:

An NSValue object is a wrapper around an underlying value. If you construct two NSValue objects from the same value, they’ll return NO when compared with the == operator, but YES when compared using the isEqual: method:

NSPoint point = NSMakePoint(2.0, 3.0);
NSValue *a = [NSValue valueWithPoint:point];
NSValue *b = [NSValue valueWithPoint:point];

BOOL valuesHaveSameIdentity = (a == b); // NO
BOOL valuesAreEqual = ([a isEqual:b]); // YES

NSObject and NSValue have different semantics for equality, and understanding the difference between them is the key to understanding how equality works in most programming languages.

Value vs. Reference Semantics

If the most important thing about an object is its state, then it’s known as a value type, and its observable properties are used to determine equality.

If the most important thing about an object is its identity, then it’s known as a reference type, and its memory address is used to determine equality.

The naming of NSValue is therefore appropriate because objects of that type follow value semantics when determining equality in isEqual:.

You’ll find plenty of other value types throughout Foundation — just look for their telltale isEqualToClassName: method. For example:

  • NSArray -isEqualToArray:
  • NSAttributedString -isEqualToAttributedString:
  • NSData -isEqualToData:
  • NSDate -isEqualToDate:
  • NSDictionary -isEqualToDictionary:
  • NSHashTable -isEqualToHashTable:
  • NSIndexSet -isEqualToIndexSet:
  • NSNumber -isEqualToNumber:
  • NSOrderedSet -isEqualToOrderedSet:
  • NSSet -isEqualToSet:
  • NSString -isEqualToString:
  • NSTimeZone -isEqualToTimeZone:

When comparing two instances of any of these classes, use these high-level methods rather than isEqual:.

Types that encapsulate a single value, such as NSDate, perform an equality comparison of that value. In the case of NSDate, which represents a point in time relative to an absolute reference date (1 Jan 2001 00:00:00 GMT), objects are compared using their offset value.

For container classes like NSArray and NSDictionary, deep equality comparison is performed by checking that each member-wise pair in the collections are equal to each other. Here’s an idea of how NSArray might implement isEqualToArray:, and how that relates to its implementation of isEqual: (ignoring for a moment that, as a class cluster, the actual implementation would be significantly more complicated):

@implementation NSArray // Simplified
- (BOOL)isEqualToArray:(NSArray *)array {
  if (!array || [self count] != [array count]) {
    return NO;
  }

  for (NSUInteger idx = 0; idx < [array count]; idx++) {
      if (![self[idx] isEqual:array[idx]]) {
          return NO;
      }
  }

  return YES;
}

- (BOOL)isEqual:(nullable id)object {
  if (object == nil) {
    return NO;
  }

  if (self == object) {
    return YES;
  }

  if (![object isKindOfClass:[NSArray class]]) {
    return NO;
  }

  return [self isEqualToArray:(NSArray *)object];
}
@end

String Interning

After learning about the differences between reference and value semantics, and how they change the behavior of == and isEqual:, you may be confused by the following behavior:

NSString *a = @"Hello";
NSString *b = @"Hello";

BOOL valuesHaveSameIdentity = (a == b); // YES (?)
BOOL valuesAreEqual = ([a isEqual:b]); // YES

What? NSString is a value type, so why does == return YES for what should be two different objects?

It all has to do with an optimization technique known as string interning, whereby one copy of immutable string value is copied for each distinct value. NSString *a and NSString *b point to the same copy of the interned string value @"Hello".

Objective-C selector names are also stored as interned strings in a shared pool. This is an important optimization for a language that operates by passing messages back and forth; being able to quickly check strings by pointer equality has a huge impact on runtime performance.

Note that this only works for statically-defined, immutable strings.

Tagged Pointers

“Fair enough,” you might say to yourself at this point. “Strings are important and complicated, so I understand why things may not work as I originally expected.”

Unfortunately, your understanding would be further confounded when NSDate doesn’t work as you expect, either:

NSTimeInterval timeInterval = 556035120;
NSDate *a = [NSDate dateWithTimeIntervalSinceReferenceDate:timeInterval];
NSDate *b = [NSDate dateWithTimeIntervalSinceReferenceDate:timeInterval];

BOOL valuesHaveSameIdentity = (a == b); // YES (?)
BOOL valuesAreEqual = ([a isEqual:b]); // YES

Seriously? We spent all that time explaining the difference between == and isEqual: only to learn that it’s all a lie?

Well… kinda. Not so much a lie as an omission.

What you’re seeing here is another optimization technique at work, known as pointer tagging.

The Objective-C runtime, when running in 64-bit mode, represents object pointers using 64-bit integers. Normally, this integer value points to an address in memory where the object is stored. But as an optimization, some small values can be stored directly in the pointer itself. If the least-significant bit is set to 1, a pointer is considered to be tagged; the runtime reads the next 3 bits to determine the tagged class and then initializes a value of that class using the next 60 bits.

If we run the NSDate comparison code again with the debugger turned on, we can confirm that a and b are both instances of __NSTaggedDate * with odd pointer values (i.e. their least-significant digit is 1).

As an interesting tie-in to our previous section, NSString gained support for tagged pointers in macOS 10.10 & iOS 8. Mike Ash has a fascinating write-up of how that works.

Only a handful of Foundation types implement tagged pointers, so don’t expect your own objects to magically get this behavior.

Hashing

One of the most important applications of object equality is to determine collection membership. In order to keep this fast for NSDictionary and NSSet collections, subclasses with custom equality implementations are expected to implement the hash method in a way that satisfies the following criteria:

  • Object equality is commutative ([a isEqual:b] ⇒ [b isEqual:a])
  • If objects are equal, then their hash values must also be equal ([a isEqual:b] ⇒ [a hash] == [b hash])
  • However, the converse does not hold: two objects can have the same hash values, but not be equal to one another ([a hash] == [b hash] ¬⇒ [a isEqual:b])

Now for a quick flashback to Computer Science 101:

A hash table is a fundamental data structure in programming.

We can best understand hash tables by contrasting them to lists:

Lists store elements sequentially. If you want to see whether a particular object is contained by a list, you must check each element in the list sequentially until you either find what you’re looking for or run out of items. Therefore, the amount of time it takes to perform a lookup has a linear relationship to the number of elements in the list (O(n)). NSArray is the primary list type in Foundation.

Hash tables take a slightly different approach. Rather than storing elements sequentially, a hash table allocates a fixed number of positions in memory and uses a function to calculate the position within that range for each object when it’s inserted. A hash function is deterministic, and a good hash function generates values in a relatively uniform distribution without being too computationally expensive. Ideally, the amount of time it takes to find an element in a hash table is constant (O(1)), independent of how many elements are stored. NSSet and NSDictionary are the primary collections in Foundation that implement hash tables.

There is one important caveat to these performance characteristics, though: If two different objects produce the same hash value, the hash table seeks from the calculated index and places the new object in the first available spot. We call this a hash collision. As a hash table becomes more congested, the likelihood of collision increases, which leads to more time spent looking for a free space (hence why a hash function with a uniform distribution is so desirable).

Best Practices when Implementing Value Types

If you’re implementing a custom type and want it to follow value semantics, do the following:

  • Implement a new isEqualToClassName: method to test for value equality.
  • Override the isEqual: method, starting with early nil check and class and object identity checks and falling back on the aforementioned value equality test.
  • Override the hash method such that equal objects produce the same hash value.

As an example, consider the following Color type, which represents a color using floating-point values for red, green, and blue intensities between 0 and 1:

@interface Color: NSObject
@property NSNumber *red;
@property NSNumber *green;
@property NSNumber *blue;
@end

Implementing isEqualToClassName:

The isEqualToClassName: method should be publicly declared and provide a test for value equality with another object of the same type.

- (BOOL)isEqualToColor:(Color *)color {
    return [self.red isEqualToNumber:color.red] &&
        [self.green isEqualToNumber:color.green] &&
        [self.blue isEqualToNumber:color.blue];
}

Implementations of this method typically perform member-wise comparison between the receiver and the passed argument for each of the properties of that type. In the case of a Color, that means checking the red, green , and blue properties of each color for equality.

Be sure to use the corresponding value equality method for each of the properties.

Implementing isEqual:

The isEqual: method should delegate to the isEqualToClassName: method after testing for nil argument, pointer equality, and checking for type identity:

- (BOOL)isEqual:(nullable id)object {
    if (object == nil) {
        return NO;
    }

    if (self == object) {
        return YES;
    }

    if (![object isKindOfClass:[Color class]]) {
        return NO;
    }

    return [self isEqualToColor:(Color *)object];
}

Implementing hash

A common misconception about custom hash implementations comes from affirming the consequent: thinking that hash values must be distinct. Although an ideal hash function would produce all distinct values, this is significantly more difficult than what’s required — which is, if you’ll recall:

  • Override the hash method such that equal objects produce the same hash value.

A simple way to satisfy this requirement is to simply XOR over the hash values of the properties that determine equality.

- (NSUInteger)hash {
    return [self.red hash] ^ [self.green hash] ^ [self.blue hash];
}

Yes, this approach results in collisions for objects with the same values for different properties (for example, cyan and yellow produce the same hash value, because each has color channels with intensity equal to 1). However, it may be good enough for what you’re doing.

Unless you have reason to believe that a better hash implementation would improve performance in a meaningful way, you’re probably better off focusing your time elsewhere. (That’s not to say that all optimizations are premature, but rather that complicated hash functions frequently are).

For the curious and pedantic, Mike Ash has another blog post with suggestions for improving hash functions using techniques like bit-shifting and rotating composite values that may overlap.

Hopefully, after all of this explanation, we can all stand with an equal footing on this slippery subject.

As humans, we strive to understand and implement equality in our society and economy; in the laws and leaders that govern us, and in the understanding that we extend to one another as we journey through existence. May we continue towards that ideal, where individuals are judged by the contents of their character, just as we judge a variable by the contents of its memory address.

NSMutableHipster

Questions? Corrections? Issues and pull requests are always welcome.

Written by Mattt
Mattt

Mattt (@mattt) is a writer and developer in Portland, Oregon.

Next Article

iOS development all but requires the use of Xcode. And if we’re resigned to use an IDE in our development workflow, we might as well make the most of it, right? So this week on NSHipster, we’re going to talk about one of the more powerful yet underused features of Xcode: Code Snippets