NSObject子类重写isEqual:函数和hash函数实践

本体性和相等性：（摘自Equality）

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

对象比较：

比较方式：
1、==：对于基本数据类型比较的是值，对于对象则是本体比较，也就是直接比较对象的指针地址
2、isEqual：
有了==后，为什么还要有 isEqual:,这里要搞清楚两个概念：
对象比较和对象地址比较：
这里也就回到了文章开始提到的相等性，有时我们比较对象，并不是为了比较对象的地址是否相同，而是只要是对象的属性，内容等相同我们就会认为对象相同。（这也是为什么我们会自定义isEqual:函数）
OC对象比较一般来说是比较“本体”，而本体的比较比的是对象的内存地址，（即：只要是地址相同，则被认为是相同的对象）但是当我们重写了isEqual:后，动机就是为了做相等性比较。

重写hash函数

哈希表的查找原理：

说到hash我们先来简单了解下Hash Table这种数据结构：
1、数组中查找一个元素的过程：
1）遍历整个数组、
2）取出数组中每一个值，并将取出的值同目标值进行比较。若一致则返回该成员。
如果数组未经过排序，查找的时间复杂度是O(length).
2、而当将一个元素加入到Hash Table中时，会给这个元素分配一个hash值，用来表示这个元素在hash表中的位置。（hash值的生成就是通过hash函数）。
通过位置标识，hash表的查找时间复杂度为O(1)。但是**多个成员的hash值相同时即：出现hash冲突。这是时间复杂度就会降低。过程总结如下：
1）通过hash值定位到元素所在的位置
2）如果该位置有多个hash值相同的成员，则对该位置上的hash值相同的元素以数组方式进行查找。
通常为了避免情况2的出现，有一个规范：加入到hash表中的元素应尽量保证其hash值唯一。

iOS中关于hash方法的重写：

3、iOS中NSSet、NSDictionary都是基于hash table实现的。所以当我们自定义的类重写了isEqual方法，且该对象有可能被加入到集合中时，要保证重写hash方法。
原因如下：
1、为了保证效率，基于散列表实现的NSSet、NSDictionary在对成员判断是否相等时，会：
1）想判断连个对象的hash值是否相同，如果相同则进行第二步处理，反之，判定为不相等。
2）在基于第一步的条件下，再调用isEqual:(isEqualXXX:)来进行判断。
也就是说：hash值相同，对象也有可能不相同。但是我们一般约定：如果对象相等，hash值一定要保证相等。

2、既然重写了isEqual：函数，说明我们想要做的是“相等性”比较，而不是“本体性”比较，而默认的hash函数返回值则是对象的内存地址。既然是做“相等性”比较，那就应该让hash返回值也符合“相等性”比较行为，而不是返回对象内存地址。

来看一段代码：

person.m文件

@implementation person

- (instancetype)initWithUserName:(NSString *)userName {
    self = [super init];
    if(self) {
        self.userName = userName;
    }
    return self;
}

- (BOOL)isEqual:(id)object {
    NSLog(@"===isEqual:self:%@,object:%@",self,object);
//    return [super isEqual:object];
    if(self == object) {
        return YES;
    }
    else {
        if([self.userName isEqualToString:((person *)object).userName]) {
            return YES;
        }
        return NO;
    }
}

- (NSUInteger)hash {
    NSLog(@"=====hash");
    return [super hash];
}

//重写后直接调super和不重写hash方法作用是一致的。

otherClass.m
person *pp = [[person alloc] initWithUserName:@"1111"];
person *pp11 = [[person alloc] initWithUserName:@"1111"];
NSMutableSet *set = [NSMutableSet set];
[set addObject:pp];
[set addObject:pp11];

NSLog(@"=====%@",set);

期望输出：set中置于一个元素，因为我们重定义了isEqual，只要是userName相同，我们就认为对象是相同的。所以pp和pp11在这里是相等的，不应该被他添加到集合中。
实际输出：2个元素都被加入了集合中。
原因分析：在添加第二个元素时，因为hash值返回的是每个对象的内存地址，所以被判断为不相等，没有执行isEqual：函数。幸而直接被添加进set中。

疑问：如果把上面的代码作如下改动：

//添加代码
person *pp22 = [[person alloc] initWithUserName:@"1111"];
[set addObject:pp22];
NSLog(@"=====%@",set);

会发现pp22没有被添加到集合中，打印pp22 的hash值发现同pp、pp11不相同,而且这里却执行了isEqual:函数。所以不明白为什么没有添加进去？如果有同学有好的理解，请在评论区跟我分享。

如何重写hash函数：

直接说结论：

将对象关键属性的hash值进行位或运算，将运算结果作为对象的hash值。

这里只是提供了一种还算不错的实现方式，诸多开源库其实都有很好的实践。大家可自行参阅。

代码示例：

- (NSUInteger)hash {
    return [self.userName hash] ^ [self.lastName hash];
}

hash的设计是为了快速查找,要尽可能的避免hash冲突,也就是不满足isEqueal的两个元素,尽量hash不相等,在设计hash的时候要考虑,是否会比较轻易的出现两个不等的对象hash值相等的情况。如果是，那就需要重新设计hash函数的实现。
以上面的实现为例。（例如有人曾给出这个例子）john smith 和 smith john结果是一样的。
所以这里比较好的实践为：

- (NSUInteger)hash {
  return [self.firstName hash << 8] ^ [self.secondName hash];
}

添加进集合后，保证对象的hash值不可变：

如果重写了对象的hash函数，而且把对象作为基于“哈希表”实现的集合（NSSet、NSDictionary、NSMapTable、NSHashTable）中的key时，需要保证在集合内的期间，对象的hash不变。
看下面代码具体解释下：

NSMutableDictionary *dic = [NSMutableDictionary dictionary];
[dic setObject:@"hhhhh" forKey:pp];
NSLog(@"====%@",[dic objectForKey:pp]);

结果：输出hhh
但是我们稍加改造，如下：

    NSMutableDictionary *dic = [NSMutableDictionary dictionary];
    [dic setObject:@"hhhhh" forKey:pp];
    NSLog(@"====%@",[dic objectForKey:pp]);
    pp.userName = @"test";
    NSLog(@"====%@",[dic objectForKey:pp]);
结果：
 TestIsE&Hash[7399:1002659] ====hhhhh
 TestIsE&Hash[7399:1002659] ====(null)

当对象在集合内期间，如果改变了对象的hash值，会导致hash表结构的结合无法正确查找的问题。

添加isEqualXXX:函数：

NSObject子类重写了isEqual:后，需要做一下三方面的工作：

1、实现一个新的 isEqualTo__ClassName__ 方法，进行实际意义上的值的比较。
2、重载 isEqual: 方法进行类和对象的本体性检查，如果失败则回退到上面提到的值(相等性)比较方法。
3、重载 hash 方法。

参考：
isEqual & hash
不懂isEqual
解析和重写NSObjetc的isEqual和Hash
Equality