NSObject子類重寫isEqual:函數(shù)和hash函數(shù)實(shí)踐

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

相等性：當(dāng)兩個(gè)物體有一系列相同的可觀測的屬性時(shí)鹅髓，兩個(gè)物體可能是互相相等或者等價(jià)的跃捣。但這兩個(gè)物體仍然是不同的险掀，他們各自有自己的本體嗜价。
本體性：在編程中腋妙，一個(gè)對象的本體和它的內(nèi)存地址是相互關(guān)聯(lián)的默怨。關(guān)聯(lián)的內(nèi)存地址相同則具有本體性。

對象比較：

比較方式：
1骤素、==：對于基本數(shù)據(jù)類型比較的是值匙睹，對于對象則是本體比較愚屁，也就是直接比較對象的指針地址
2、isEqual：
有了==后痕檬，為什么還要有 isEqual:,這里要搞清楚兩個(gè)概念：
對象比較和對象地址比較：
這里也就回到了文章開始提到的相等性霎槐，有時(shí)我們比較對象，并不是為了比較對象的地址是否相同梦谜，而是只要是對象的屬性丘跌，內(nèi)容等相同我們就會(huì)認(rèn)為對象相同。（這也是為什么我們會(huì)自定義isEqual:函數(shù)）
OC對象比較一般來說是比較“本體”唁桩，而本體的比較比的是對象的內(nèi)存地址闭树，（即：只要是地址相同，則被認(rèn)為是相同的對象）但是當(dāng)我們重寫了isEqual:后荒澡，動(dòng)機(jī)就是為了做相等性比較报辱。

重寫hash函數(shù)

哈希表的查找原理：

說到hash我們先來簡單了解下Hash Table這種數(shù)據(jù)結(jié)構(gòu)：
1、數(shù)組中查找一個(gè)元素的過程：
1）遍歷整個(gè)數(shù)組单山、
2）取出數(shù)組中每一個(gè)值碍现，并將取出的值同目標(biāo)值進(jìn)行比較。若一致則返回該成員米奸。
如果數(shù)組未經(jīng)過排序昼接，查找的時(shí)間復(fù)雜度是O(length).
2、而當(dāng)將一個(gè)元素加入到Hash Table中時(shí)悴晰，會(huì)給這個(gè)元素分配一個(gè)hash值慢睡，用來表示這個(gè)元素在hash表中的位置。（hash值的生成就是通過hash函數(shù)）膨疏。
通過位置標(biāo)識一睁，hash表的查找時(shí)間復(fù)雜度為O(1)钻弄。但是**多個(gè)成員的hash值相同時(shí)即：出現(xiàn)hash沖突佃却。這是時(shí)間復(fù)雜度就會(huì)降低。過程總結(jié)如下：
1）通過hash值定位到元素所在的位置
2）如果該位置有多個(gè)hash值相同的成員窘俺，則對該位置上的hash值相同的元素以數(shù)組方式進(jìn)行查找饲帅。
通常為了避免情況2的出現(xiàn)，有一個(gè)規(guī)范：加入到hash表中的元素應(yīng)盡量保證其hash值唯一瘤泪。

iOS中關(guān)于hash方法的重寫：

3灶泵、iOS中NSSet、NSDictionary都是基于hash table實(shí)現(xiàn)的对途。所以當(dāng)我們自定義的類重寫了isEqual方法赦邻，且該對象有可能被加入到集合中時(shí)，要保證重寫hash方法实檀。
原因如下：
1惶洲、為了保證效率按声，基于散列表實(shí)現(xiàn)的NSSet、NSDictionary在對成員判斷是否相等時(shí)恬吕，會(huì)：
1）想判斷連個(gè)對象的hash值是否相同签则，如果相同則進(jìn)行第二步處理，反之铐料，判定為不相等渐裂。
2）在基于第一步的條件下，再調(diào)用isEqual:(isEqualXXX:)來進(jìn)行判斷钠惩。
也就是說：hash值相同柒凉，對象也有可能不相同。但是我們一般約定：如果對象相等篓跛，hash值一定要保證相等扛拨。

2、既然重寫了isEqual：函數(shù)举塔，說明我們想要做的是“相等性”比較绑警，而不是“本體性”比較，而默認(rèn)的hash函數(shù)返回值則是對象的內(nèi)存地址央渣。既然是做“相等性”比較计盒，那就應(yīng)該讓hash返回值也符合“相等性”比較行為，而不是返回對象內(nèi)存地址芽丹。

來看一段代碼：

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];
}

//重寫后直接調(diào)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中置于一個(gè)元素，因?yàn)槲覀冎囟x了isEqual拔第，只要是userName相同咕村，我們就認(rèn)為對象是相同的。所以pp和pp11在這里是相等的蚊俺，不應(yīng)該被他添加到集合中懈涛。
實(shí)際輸出：2個(gè)元素都被加入了集合中。
原因分析：在添加第二個(gè)元素時(shí)泳猬，因?yàn)閔ash值返回的是每個(gè)對象的內(nèi)存地址批钠，所以被判斷為不相等，沒有執(zhí)行isEqual：函數(shù)得封。幸而直接被添加進(jìn)set中埋心。

疑問：如果把上面的代碼作如下改動(dòng)：

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

會(huì)發(fā)現(xiàn)pp22沒有被添加到集合中，打印pp22 的hash值發(fā)現(xiàn)同pp忙上、pp11不相同,而且這里卻執(zhí)行了isEqual:函數(shù)拷呆。所以不明白為什么沒有添加進(jìn)去？如果有同學(xué)有好的理解，請?jiān)谠u論區(qū)跟我分享茬斧。

如何重寫hash函數(shù)：

直接說結(jié)論：

將對象關(guān)鍵屬性的hash值進(jìn)行位或運(yùn)算箫柳，將運(yùn)算結(jié)果作為對象的hash值。

這里只是提供了一種還算不錯(cuò)的實(shí)現(xiàn)方式啥供，諸多開源庫其實(shí)都有很好的實(shí)踐悯恍。大家可自行參閱。

代碼示例：

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

hash的設(shè)計(jì)是為了快速查找,要盡可能的避免hash沖突,也就是不滿足isEqueal的兩個(gè)元素,盡量hash不相等,在設(shè)計(jì)hash的時(shí)候要考慮,是否會(huì)比較輕易的出現(xiàn)兩個(gè)不等的對象hash值相等的情況伙狐。如果是涮毫，那就需要重新設(shè)計(jì)hash函數(shù)的實(shí)現(xiàn)。
以上面的實(shí)現(xiàn)為例贷屎。（例如有人曾給出這個(gè)例子）john smith 和 smith john結(jié)果是一樣的罢防。
所以這里比較好的實(shí)踐為：

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

添加進(jìn)集合后，保證對象的hash值不可變：

如果重寫了對象的hash函數(shù)唉侄，而且把對象作為基于“哈希表”實(shí)現(xiàn)的集合（NSSet咒吐、NSDictionary、NSMapTable属划、NSHashTable）中的key時(shí)恬叹，需要保證在集合內(nèi)的期間，對象的hash不變同眯。
看下面代碼具體解釋下：

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

結(jié)果：輸出hhh
但是我們稍加改造绽昼，如下：

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

當(dāng)對象在集合內(nèi)期間，如果改變了對象的hash值须蜗，會(huì)導(dǎo)致hash表結(jié)構(gòu)的結(jié)合無法正確查找的問題硅确。

添加isEqualXXX:函數(shù)：

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

1明肮、實(shí)現(xiàn)一個(gè)新的 isEqualTo__ClassName__ 方法菱农，進(jìn)行實(shí)際意義上的值的比較。
2柿估、重載 isEqual: 方法進(jìn)行類和對象的本體性檢查循未，如果失敗則回退到上面提到的值(相等性)比較方法。
3官份、重載 hash 方法只厘。

參考：
isEqual & hash
不懂isEqual
解析和重寫NSObjetc的isEqual和Hash
Equality