EqualityMattt Chester Liu 🚩🌱

在哲学和数学领域，相等的概念一直以来都是人们所争论和探寻的焦点，其所蕴含的深层含义更是延伸到道德，社会正义以及公共政策等诸多层面。

从经验主义的角度来看，当两个物体没办法通过观察来互相区分开的时候，这两个物体就是相等的。对于人类而已，信奉平等主义的人相信，所有人都应该被认为是平等的个体，在其所存在的社会，生态，政治和司法系统中得到平等的待遇。

对于程序员来说，在我们所建模的问题领域当中，协调好“相等”概念在逻辑上和实际意义上的理解，是一个很重要的任务。在处理相等的概念的时候，有些细微的问题经常会被忽略。在没有对于相等语义有着足够理解的情况下，就直接进行编码实现，往往会导致冗余的工作和错误的结果。对底层数学和逻辑系统的深层理解，和真正让模型工作起来同等重要，对于我们都是必不可少的。

尽管对于所有技术博文来说，我们最想做的就是扫一下标题然后去找示例代码，但是对这篇文章来说，请务必花几分钟时间来阅读和理解它。在不懂得原理的情况下照搬那些看起来有关的代码可能会导致程序产生错误的行为。不开玩笑，在 Objective-C 的领域，相等性是最容易产生误解的话题之一。

相等性 & 本体性

首先，我们要对于 相等性 和 本体性 进行一下区分。

当两个物体有一系列相同的可观测的属性时，两个物体可能是互相 相等 或者 等价 的。但这两个物体本身仍然是 不同的 ，它们各自有自己的 本体 。 在编程中，一个对象的本体和它的内存地址是相关联的。

NSObject 使用 isEqual: 这个方法来测试和其他对象的相等性。在它的基类实现中，相等性检查本质上就是对本体性的检查。两个 NSObject 如果指向了同一个内存地址，那它们就被认为是相同的。

@implementation NSObject (Approximate)
- (BOOL)isEqual:(id)object {
  return self == object;
}
@end

对于 NSArray，NSDictionary 和 NSString 这种容器类来说，大家所期望的，同时也是更加有用的行为，应该是进行深层的相等性检查，对于集合中的每个成员都进行判断。

NSObject 的子类在实现它们自己的 isEqual: 方法时，应该完成下面的工作：

• 实现一个新的 isEqualTo__ClassName__ 方法，进行实际意义上的值的比较。
• 重载 isEqual: 方法进行类和对象的本体性检查，如果失败则回退到上面提到的值比较方法。
• 重载 hash 方法，在下一个部分会详细介绍。

下面是 NSArray 可能使用的解决方案（对于这个例子来说，我们暂时忽略掉 NSArray 实际上是一个类簇，真正的实现会比这个复杂得多）。

@implementation NSArray (Approximate)
- (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:(id)object {
  if (self == object) {
    return YES;
  }

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

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

在 Foundation 框架中，下面这些 NSObject 的子类都有自己的相等性检查实现，分别使用下面这些方法：

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

对上面这些类来说，当需要对它们的两个实例进行比较时，推荐使用这些高层方法而不是直接使用 isEqual:。

到这里，我们理论的实现还没有完善，让我们把目光投向 hash 方法（不过首先我们要先通过一个小插曲，解决一下 NSString 当中的一些问题）：

古怪的 NSString

作为一个有意思的小插曲，我们看下面这个例子：

NSString *a = @"Hello";
NSString *b = @"Hello";
BOOL wtf = (a == b); // YES

首先我们要明确一点，比较 NSString 对象正确的方法是 -isEqualToString:。任何情况下都不要直接使用 == 来对 NSString 进行比较。

现在来看，到底发生了什么？为什么这样做结果是正确的，同样的代码对于 NSArray 和 NSDictionary 就不好使？

所有这些行为，都来源于一种称为字符串驻留的优化技术，它把一个不可变字符串对象的值拷贝给各个不同的指针。NSString *a 和 *b都指向同样一个驻留字符串值 @"Hello"。 注意所有这些针对的都是静态定义的不可变字符串。

有意思的是，Objective-C 选择器的名字也是作为驻留字符串储存在一个共享的字符串池当中的。

themoreyouknow.gif.

散列

对于面向对象编程来说，对象相等性检查的主要用例，就是确定一个对象是不是一个集合的成员。为了加快这个过程，子类当中需要实现 hash 方法：

• 对象相等具有 交换性 （[a isEqual:b] ⇒ [b isEqual:a])
• 如果两个对象相等，它们的 hash 值也一定是相等的 ([a isEqual:b] ⇒ [a hash] == [b hash])
• 反过来则不然，两个对象的散列值相等不一定意味着它们就是相等的 ([a hash] == [b hash] ¬⇒ [a isEqual:b])

下面快速复习一下大学计算机基础：

散列表是程序设计中基础的数据结构之一，它使得 NSSet 和 NSDictionary 能够非常快速地(O(1)) 进行元素查找。

通过把散列表和数组进行对比，有助于我们更好地理解散列表的性质：

数组把元素存储在一系列连续的地址当中，例如一个容量为 n 的数组当中，包含了位置 0，1 一直到 n-1 这么多空白的槽位。要判断一个元素是不是在数组中存在，需要对数组中每个元素的位置都进行检查（除非数组当中的元素是已经排序过的，那是另一回事了）。

散列表使用了一个不太一样的办法。相对于数组把元素按顺序存储(0, 1, ..., n-1)，散列表在内存中分配 n 个位置，然后使用一个函数来计算出位置范围之内的某个具体位置。散列函数需要具有确定性。一个 好的 散列函数在不需要太多计算量的情况下，可以使得生成的位置分布接近于均匀分布。当两个不同的对象计算出相同的散列值时，我们称其为发生了 散列碰撞 。当出现碰撞时，散列表会从碰撞产生的位置开始向后寻找，把新的元素放在第一个可供放置的位置。随着散列表变得越来越致密，发生碰撞的可能性也会随之增加，导致查找可用位置花费的时间也会增加（这也是为什么我们希望散列函数的结果分布更接近于均匀分布）。

在实现一个 hash 函数的时候，一个很常见的误解来源于肯定后项，认为 hash 得到的值 必须 是唯一可区分的。这种误解往往会导致没必要的包含着从 Java 课本里抄袭过来的素数以及魔法咒语一样的操作的实现。实际上，对于关键属性的散列值进行一个简单的 XOR操作，就能够满足在 99% 的情况下的需求了。

其中需要技巧的一点是，找出哪个值对于对象来说是关键的。

对于一个 NSDate 对象来说，从一个参考日期到它本身的时间间隔就已经足够了：

@implementation NSDate (Approximate)
- (NSUInteger)hash {
  return (NSUInteger)abs([self timeIntervalSinceReferenceDate]);
}

对于一个 UIColor 对象，RGB 元素的移位和可以很方便地计算出来：

@implementation UIColor (Approximate)
- (NSUInteger)hash {
  CGFloat red, green, blue;
  [self getRed:&red green:&green blue:&blue alpha:nil];
  return ((NSUInteger)(red * 255) << 16) + ((NSUInteger)(green * 255) << 8) + (NSUInteger)(blue * 255);
}
@end

在子类中实现 -isEqual: 和 hash

综合上面所说的内容，下面是一个在子类中重载默认相等性检查时可能的实现：

@interface Person
@property NSString *name;
@property NSDate *birthday;

- (BOOL)isEqualToPerson:(Person *)person;
@end

@implementation Person

- (BOOL)isEqualToPerson:(Person *)person {
  if (!person) {
    return NO;
  }

  BOOL haveEqualNames = (!self.name && !person.name) || [self.name isEqualToString:person.name];
  BOOL haveEqualBirthdays = (!self.birthday && !person.birthday) || [self.birthday isEqualToDate:person.birthday];

  return haveEqualNames && haveEqualBirthdays;
}

#pragma mark - NSObject

- (BOOL)isEqual:(id)object {
  if (self == object) {
    return YES;
  }

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

  return [self isEqualToPerson:(Person *)object];
}

- (NSUInteger)hash {
  return [self.name hash] ^ [self.birthday hash];
}

对于好奇心旺盛和不畏钻研的同学来说，Mike Ash 的这篇博文解释了如何通过移位操作和旋转可能重复的部分值来进一步优化 hash 函数的实现。

不要过度考虑

上面我们探讨的这些内容，对于我们理解认识论和计算机科学来说是很有趣的训练材料，然而还有一个残留的非常实际的细节我们没有提到：

一般情况下你不需要去实现这些。

很多情况默认的本体性检查（两个变量指向内存当中的同一个地址）正是我们需要的行为，这是数据建模上的局限性产生的结果。

以前面例子中的 Person 类为例，两个不同的人有着共同的名字 以及 生日并不是完全不可想象的。现实生活中，这种类型的身份危机会通过额外的信息来解决，不管是依赖于行政系统类似社保号码的东西，还是他们父母的身份，或者是其它的身体上的特征。

然而额外的信息也并不能保证万无一失。毕竟，一个人还可以被克隆，传送，或者被带到另一个平行宇宙当中。听起来不太可能？确实，但是在对系统进行建模时，很多挑战正是去处理那些不完美的假设。你懂我的意思。

最终我们需要通过抽象来把那些重要的，可用于区分的，同时建模系统也关心的特性抽离出来，抛弃剩下的那些。然后开发者可以考虑一下，会不会在集合成员检查时，需要针对对象做特殊的计算。对于一个只记录 姓名 和 生日 的程序来说，把属性相同的对象实例看成是不同的实体，也许是十分正确的做法。

经过这么多的解释，希望我们在这个有些诡谲的话题上取得了”相同“的认识。

作为人类，我们很努力地去理解和实现平等，在我们的社会中，在自然生态环境中，在立法和执法中，在选举我们领导人的过程中，在人类作为一个物种互相沟通延续我们的存在这一共识中。愿我们能继续这个奋斗的过程，最终达到理想的彼岸，在那里，评价一个人的标准是他的人格，就像我们判断一个变量是通过它的内存地址一样。

除非另有声明，本文采用知识共享「署名-非商业性使用 3.0 中国大陆」许可协议授权。