iOS开发 之 不要告诉我你真的懂isEqual与hash!

liwzwy6005 8年前
   <h2><strong>目录</strong></h2>    <ul>     <li> <p>为什么要有isEqual方法?</p> </li>     <li> <p>如何重写自己的isEqual方法?</p> </li>     <li> <p>为什么要有hash方法?</p> </li>     <li> <p>hash方法什么时候被调用?</p> </li>     <li> <p>hash方法与判等的关系?</p> </li>     <li> <p>如何重写自己的hash方法?</p> </li>    </ul>    <h2><strong>为什么要有isEqual方法?</strong></h2>    <p>isEqual方法的作用大家肯定是知道的:</p>    <p>判断两个对象是否相等</p>    <p>但是判断相等不是已经有==运算符了么, 为什么还要isEqual方法?</p>    <p>这是因为:</p>    <p>对于基本类型, ==运算符比较的是值; 对于对象类型, ==运算符比较的是对象的地址(即是否为同一对象)</p>    <p>注意: 上述==运算符的说明适用于Objective-C和Java等不支持运算符重载的语言, 支持运算符重载的语言有C++</p>    <p>所以要理清==运算符和isEqual方法的区别, 问题就集中在</p>    <p>什么叫比较对象的地址, 什么叫比较对象</p>    <p>我们通过下面的例子来说明这个问题</p>    <pre>  <code class="language-objectivec">UIColor *color1 = [UIColor colorWithRed:0.5 green:0.5 blue:0.5 alpha:1.0];  UIColor *color2 = [UIColor colorWithRed:0.5 green:0.5 blue:0.5 alpha:1.0];  NSLog(@"color1 == color2 = %@", color1 == color2 ? @"YES" : @"NO");  NSLog(@"[color1 isEqual:color2] = %@", [color1 isEqual:color2] ? @"YES" : @"NO");</code></pre>    <p>打印结果如下</p>    <pre>  <code class="language-objectivec">color1 == color2 = NO  [color1 isEqual:color2] = YES</code></pre>    <p>从上面的例子可以看出, ==运算符只是简单地判断是否是同一个对象, 而isEqual方法可以判断对象是否相同, 例如UIColor对象表示的color是否相同</p>    <h2><strong>如何重写自己的isEqual方法?</strong></h2>    <p>对于Cocoa Framework中定义的类型, 例如上面例子中的UIColor, isEqual方法已经实现好了</p>    <p>常见类型的isEqual方法还有NSString isEqualToString / NSDate isEqualToDate / NSArray isEqualToArray / NSDictionary isEqualToDictionary / NSSet isEqualToSet, 更多参考 <a href="/misc/goto?guid=4959658789289742649" rel="nofollow,noindex">Equality</a></p>    <p>但对于自定义类型来说, 通常需要重写isEqual方法</p>    <p>通过下面的例子, 我们来看看重写isEqual方法的正确姿势</p>    <p><!--more--></p>    <p>首先定义Person类如下</p>    <pre>  <code class="language-objectivec">@interface Person : NSObject    @property (nonatomic, copy) NSString *name;  @property (nonatomic, strong) NSDate *birthday;    @end</code></pre>    <p>Person类中实现的isEqual方法如下</p>    <pre>  <code class="language-objectivec">- (BOOL)isEqual:(id)object {      if (self == object) {          return YES;      }        if (![object isKindOfClass:[Person class]]) {          return NO;      }        return [self isEqualToPerson:(Person *)object];  }    - (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;  }</code></pre>    <p>上述代码主要步骤如下</p>    <ul>     <li> <p>Step 1: ==运算符判断是否是同一对象, 因为同一对象必然完全相同</p> </li>     <li> <p>Step 2: 判断是否是同一类型, 这样不仅可以提高判等的效率, 还可以避免隐式类型转换带来的潜在风险</p> </li>     <li> <p>Step 3: 通过封装的isEqualToPerson方法, 提高代码复用性</p> </li>     <li> <p>Step 4: 判断person是否是nil, 做参数有效性检查</p> </li>     <li> <p>Step 5: 对各个属性分别使用默认判等方法进行判断</p> </li>     <li> <p>Step 6: 返回所有属性判等的与结果</p> </li>    </ul>    <p>isEqual的实现并不复杂, 但是从代码质量(效率, 安全, 复用)来说, 上述实现仍然值得仔细学习和借鉴</p>    <p>除了上面的最佳实践, 还有一种最不佳实践</p>    <pre>  <code class="language-objectivec">@implementation NSDate (Approximate)    - (BOOL)isEqual:(id)object {      return YES;  }    @end</code></pre>    <p>这里的isEqual方法一直返回YES</p>    <pre>  <code class="language-objectivec">NSLog(@"[self.date1 isEqual:@\"hello\"] = %@", [self.date1 isEqual:@"hello"] ? @"YES" : @"NO");</code></pre>    <p>打印结果如下</p>    <pre>  <code class="language-objectivec">[self.date1 isEqual:@"hello"] = YES</code></pre>    <p>这个有趣的实验说明: 对象的判等可以完全由您决定, 即使两个完全不同的对象</p>    <h2><strong>为什么要有hash方法?</strong></h2>    <p>这个问题要从Hash Table这种数据结构说起</p>    <p>首先我们看下如何在数组中查找某个成员</p>    <ul>     <li> <p>Step 1: 遍历数组中的成员</p> </li>     <li> <p>Step 2: 将取出的值与目标值比较, 如果相等, 则返回该成员</p> </li>    </ul>    <p>在数组未排序的情况下, 查找的时间复杂度是O(array_length)</p>    <p>为了提高查找的速度, Hash Table出现了</p>    <p>当成员被加入到Hash Table中时, 会给它分配一个hash值, 以标识该成员在集合中的位置</p>    <p>通过这个位置标识可以将查找的时间复杂度优化到O(1), 当然如果多个成员都是同一个位置标识, 那么查找就不能达到O(1)了</p>    <p>重点来了:</p>    <p>分配的这个hash值(即用于查找集合中成员的位置标识), 就是通过hash方法计算得来的, 且hash方法返回的hash值最好唯一</p>    <p>和数组相比, 基于hash值索引的Hash Table查找某个成员的过程就是</p>    <ul>     <li> <p>Step 1: 通过hash值直接找到查找目标的位置</p> </li>     <li> <p>Step 2: 如果目标位置上有多个相同hash值得成员, 此时再按照数组方式进行查找</p> </li>    </ul>    <h2><strong>hash方法什么时候被调用?</strong></h2>    <p>带着这个问题, 我们来看下面的例子</p>    <pre>  <code class="language-objectivec">Person *person1 = [Person personWithName:kName1 birthday:self.date1];  Person *person2 = [Person personWithName:kName2 birthday:self.date2];    NSMutableArray *array1 = [NSMutableArray array];  [array1 addObject:person1];  NSMutableArray *array2 = [NSMutableArray array];  [array2 addObject:person2];  NSLog(@"array end -------------------------------");    NSMutableSet *set1 = [NSMutableSet set];  [set1 addObject:person1];  NSMutableSet *set2 = [NSMutableSet set];  [set2 addObject:person2];  NSLog(@"set end -------------------------------");    NSMutableDictionary *dictionaryValue1 = [NSMutableDictionary dictionary];  [dictionaryValue1 setObject:person1 forKey:kKey1];  NSMutableDictionary *dictionaryValue2 = [NSMutableDictionary dictionary];  [dictionaryValue2 setObject:person2 forKey:kKey2];  NSLog(@"dictionary value end -------------------------------");    NSMutableDictionary *dictionaryKey1 = [NSMutableDictionary dictionary];  [dictionaryKey1 setObject:kValue1 forKey:person1];  NSMutableDictionary *dictionaryKey2 = [NSMutableDictionary dictionary];  [dictionaryKey2 setObject:kValue2 forKey:person2];  NSLog(@"dictionary key end -------------------------------");</code></pre>    <p>为了看清楚hash方法是否被调用, 我们重写hash方法如下</p>    <pre>  <code class="language-objectivec">- (NSUInteger)hash {      NSUInteger hash = [super hash];      NSLog(@"hash = %ld", hash);      return hash;  }</code></pre>    <p>打印结果如下</p>    <pre>  <code class="language-objectivec">person1 == person2 = NO  [person1 isEqual:person2] = NO  isEqual end -------------------------------  array end -------------------------------  hash = 7809196951631946839  hash = 7809196951631946839  hash = 7809191961023760480  hash = 7809191961023760480  set end -------------------------------  dictionary value end -------------------------------  hash = 7809196951631946839  hash = 7809196951631946839  hash = 7809191961023760480  hash = 7809191961023760480  dictionary key end -------------------------------</code></pre>    <p>从打印结果可以看到:</p>    <p>hash方法只在对象被添加至NSSet和设置为NSDictionary的key时会调用</p>    <p>NSSet添加新成员时, 需要根据hash值来快速查找成员, 以保证集合中是否已经存在该成员</p>    <p>NSDictionary在查找key时, 也利用了key的hash值来提高查找的效率</p>    <h2><strong>hash方法与判等的关系?</strong></h2>    <p>hash方法主要是用于在Hash Table查询成员用的, 那么和我们要讨论的isEqual()有什么关系呢?</p>    <p>为了优化判等的效率, 基于hash的NSSet和NSDictionary在判断成员是否相等时, 会这样做</p>    <ul>     <li> <p>Step 1: 集成成员的hash值是否和目标hash值相等, 如果相同进入Step 2, 如果不等, 直接判断不相等</p> </li>     <li> <p>Step 2: hash值相同(即Step 1)的情况下, 再进行对象判等, 作为判等的结果</p> </li>    </ul>    <p>简单地说就是</p>    <p>hash值是对象判等的必要非充分条件</p>    <h2><strong>如何重写自己的hash方法?</strong></h2>    <p>很多人在iOS开发中, 都是这么重写hash方法的</p>    <pre>  <code class="language-objectivec">- (NSUInteger)hash {      return [super hash];  }</code></pre>    <p>这样写有问题么? 带着这个问题, 我们先来看下[super hash]的值到底是什么</p>    <pre>  <code class="language-objectivec">Person *person = [[Person alloc] init];  NSLog(@"person = %ld", (NSUInteger)person);  NSLog(@"[person1 getSuperHash] = %ld", [person getSuperHash]);</code></pre>    <p>打印结果如下</p>    <pre>  <code class="language-objectivec">person = 140643147498880  [person1 getSuperHash] = 140643147498880</code></pre>    <p>由此可以看出, [super hash]返回的就是该对象的内存地址</p>    <p>联想到前面对hash值唯一性的要求, 使用对象的内存地址作为hash值不是很好么?</p>    <p>别急, 我们添加如下两个对象到NSSet中试试</p>    <pre>  <code class="language-objectivec">Person *person1 = [Person personWithName:kName1 birthday:self.date1];  Person *person2 = [Person personWithName:kName1 birthday:self.date1];  NSLog(@"[person1 isEqual:person2] = %@", [person1 isEqual:person2] ? @"YES" : @"NO");    NSMutableSet *set = [NSMutableSet set];  [set addObject:person1];  [set addObject:person2];  NSLog(@"set count = %ld", set.count);</code></pre>    <p>此时打印结果如下</p>    <pre>  <code class="language-objectivec">[person1 isEqual:person2] = YES  set count = 2</code></pre>    <p>isEqual相等的两个对象都加入到了NSSet中(set count = 2), 所以直接返回[super hash]是不正确的</p>    <p>那么hash方法的最佳实践到底是什么呢?</p>    <p>In reality, a simple XOR over the hash values of critical properties is sufficient 99% of the time(对关键属性的hash值进行位或运算作为hash值)</p>    <p>对于上面Person类的hash方法实现如下</p>    <pre>  <code class="language-objectivec">- (NSUInteger)hash {      return [self.name hash] ^ [self.birthday hash];  }</code></pre>    <h2><strong>参考</strong></h2>    <ul>     <li> <p><a href="/misc/goto?guid=4959658789289742649" rel="nofollow,noindex">Equality</a></p> </li>     <li> <p><a href="/misc/goto?guid=4959716204170928531" rel="nofollow,noindex">Implementing Equality and Hashing</a></p> </li>     <li> <p><a href="/misc/goto?guid=4959716204261980403" rel="nofollow,noindex">NSObject的hash方法</a></p> </li>     <li> <p><a href="/misc/goto?guid=4959716204342655550" rel="nofollow,noindex">浅拷贝深拷贝以及 Hash/Equal</a></p> </li>    </ul>    <p> </p>    <p> </p>    <p>来自:http://www.jianshu.com/p/915356e280fc</p>    <p> </p>