來自掘金 《實(shí)現(xiàn) Equality 和 Hashing》
翻譯自 Mike Ash 的 Implementing Equality and Hashing
Equality
對(duì)象判等是一個(gè)基本的概念，在代碼中經(jīng)常會(huì)被使用到柱徙。在 Cocoa 編程中淫茵，它通過 isEqual: 方法被實(shí)現(xiàn)纱注。一些比較簡單的例子像[array indexOfObject:]會(huì)在底層使用到它奢浑，所以說對(duì)象支持判等是非常重要的。
在 Cocoa 編程中氧卧，它已經(jīng)為我們?cè)?NSObject 中提供了一個(gè)默認(rèn)的判等實(shí)現(xiàn)亚亲。這個(gè)默認(rèn)的實(shí)現(xiàn)只是通過對(duì)象的指針地址來進(jìn)行判等。換句話說难审，一個(gè)對(duì)象只會(huì)與它自己相等瘫拣。這個(gè)默認(rèn)實(shí)現(xiàn)從功能上看如下面代碼所示：
- (BOOL)isEqual: (id)other {
return self == other;
}
雖然該默認(rèn)的判等實(shí)現(xiàn)看上去過于簡單，但實(shí)際上它對(duì)于許多對(duì)象來說告喊，是十分有用的麸拄。比如，我們永遠(yuǎn)不會(huì)把一個(gè) NSView 看做跟另外一個(gè) NSView 同等黔姜。同樣的拢切，對(duì)于很多具有該特性的類來說，這個(gè)默認(rèn)的判等實(shí)現(xiàn)已經(jīng)是足夠了秆吵。這或許是個(gè)好消息淮椰，因?yàn)檫@意味著如果你的類具有相同的判等特性，那么你不需要做任何事情就可以免費(fèi)得到想要的結(jié)果纳寂。
實(shí)現(xiàn)自定義判等
有時(shí)候你需要實(shí)現(xiàn)更深層次的判等主穗。這對(duì)于許多對(duì)象來說是很正常的，特別是那些被看作“值類型的對(duì)象”毙芜，他們是根據(jù)邏輯上的判等來區(qū)分忽媒。舉個(gè)例子：
// 使用可變類型保證生成的是不同的字符串對(duì)象
NSMutableString *s1 = [NSMutableString stringWithString: @"Hello, world"];
NSMutableString *s2 = [NSMutableString stringWithString: @"%@, %@", @"Hello", @"world"];
BOOL equal = [s1 isEqual: s2]; // 返回 YES ！
當(dāng)然啦爷肝，NSMutableString 在這種情況下已經(jīng)為你做了判等實(shí)現(xiàn)猾浦。但是如果你想要為自定義的對(duì)象做同樣的操作該怎么辦陆错？
MyClass *c1 = ...;
MyClass *c2 = ...;
BOOL equal = [c1 isEqual: c2];
在這種情況下你需要實(shí)現(xiàn)你自己版本的isEqual:方法。
測試相等性在大多數(shù)情況下是相當(dāng)簡單的金赦。把你的類中所有相關(guān)的屬性收集起來音瓷，再測試他們的相等性。如果他們當(dāng)中有不相等的夹抗，那么返回 NO 绳慎，否則返回 YES 。
有一個(gè)微妙的點(diǎn)就是漠烧，當(dāng)你的對(duì)象所對(duì)應(yīng)的類也是檢測相等性中的一個(gè)重要的屬性杏愤。去檢測 MyClass 和 NSString 的相等性是十分合理的，但是這種比較的結(jié)果永遠(yuǎn)不會(huì)返回 YES （除非 MyClass 是 NSString 的一個(gè)子類）已脓。
有一個(gè)稍微不那么微妙的點(diǎn)就是珊楼，確保你測試的屬性對(duì)于判等來說是非常重要的。一些像緩存 caches 這樣的屬性對(duì)于你的對(duì)象的外部視角而言是無關(guān)緊要的度液，那么它就不需要被用作判等的因素厕宗。
比如說你的類看起來像這樣：
@interface MyClass: NSObject {
int _length;
char *_data;
NSString *_name;
NSMutableDictionary *_cache;
}
你的判等實(shí)現(xiàn)看起來會(huì)像這樣：
- (BOOL)isEqual: (id)other {
return ([other isKindOfClass: [MyClass class]] && [other length] == _length && memcmp([other data], _data, _length) == 0 && [[other name] isEqual: _name])
// 注意：沒有 _cache 的比較
}
Hashing
哈希表是一個(gè)普通的數(shù)據(jù)結(jié)構(gòu)，被用于實(shí)現(xiàn) NSDictionary 和 NSSet 等堕担。無論你往容器類中添加多少對(duì)象已慢，都能夠支持快速查找到相應(yīng)的對(duì)象。
如果你已經(jīng)了解哈希表是如何工作的霹购，你可以直接跳過接下來的一到兩個(gè)段落內(nèi)容佑惠。
哈希表基本上可以被看做是一個(gè)帶特殊索引的龐大數(shù)組。所有被添加到數(shù)組的對(duì)象都會(huì)有一個(gè)索引關(guān)聯(lián)著他們的哈希值齐疙。這個(gè)哈希值本質(zhì)上是由對(duì)象的屬性而產(chǎn)生的偽隨機(jī)的數(shù)字膜楷。這種機(jī)制使得索引有足夠的隨機(jī)性，那么兩個(gè)對(duì)象就不太可能擁有相同的哈希值了贞奋，但這是完全可復(fù)寫的把将。當(dāng)一個(gè)對(duì)象被插入到數(shù)組中時(shí)，它的哈希值會(huì)被用來決定它該被放到哪個(gè)位置上忆矛。當(dāng)一個(gè)對(duì)象被查找時(shí)，它的哈希值會(huì)被用來決定到哪個(gè)位置中查找请垛。
用更加正式的術(shù)語來講催训，一個(gè)對(duì)象的哈希值被定義了，如果兩個(gè)對(duì)象是相等的宗收，那么他們會(huì)有相同的哈希值漫拭。要注意的是，反過來說是不正確的混稽，也不應(yīng)該這樣采驻，因?yàn)椋簝蓚€(gè)對(duì)象可以有相同的哈希值审胚，但是他們可以不相等。你想要盡可能的避免出現(xiàn)這種情況礼旅，因?yàn)楫?dāng)兩個(gè)不相等的對(duì)象擁有兩個(gè)相同的哈希值（稱為碰撞）膳叨，那么哈希表就必須采取特殊的措施去處理這種情況，這是一個(gè)非常耗時(shí)的操作痘系。然而菲嘴，這已經(jīng)被證明了要想完全避免哈希碰撞的發(fā)生是不可能的。
在 Cocoa 編程中汰翠，哈希的實(shí)現(xiàn)通過哈希方法龄坪，它的方法簽名為：
- (NSUInteger)hash;
跟對(duì)象判等一樣，NSObject 也為你提供了一個(gè)默認(rèn)的哈希實(shí)現(xiàn)复唤，但這是通過使用對(duì)象的標(biāo)識(shí)來實(shí)現(xiàn)的健田。粗略的講，它做了這些事情：
- (NSUInteger)hash {
return (NSUInteger)self;
}
實(shí)際返回的值可能不一樣佛纫，但本質(zhì)的關(guān)鍵點(diǎn)是妓局，這種方式是基于實(shí)際指向 self 的指針的值。跟判等方法一樣雳旅，如果基于對(duì)象標(biāo)識(shí)的判等已經(jīng)達(dá)到你想要的需求跟磨，那么默認(rèn)的實(shí)現(xiàn)對(duì)你來說已經(jīng)是有用的了。
實(shí)現(xiàn)自定義哈希值
因?yàn)楣５恼Z義攒盈，如果你重寫了isEqual:方法抵拘，你就必須重寫哈希方法。如果你不這樣做型豁，你會(huì)遇到兩個(gè)相同對(duì)象卻擁有不同的哈希值的情況僵蛛，這是十分不安全的。如果你在字典迎变、集合或者其他需要哈希表的地方使用到這些對(duì)象充尉，那么會(huì)出現(xiàn)問題。
因?yàn)閷?duì)象哈希值的定義和相等性的關(guān)系是十分密切的衣形，同樣的驼侠，哈希方法的實(shí)現(xiàn)和判等方法的實(shí)現(xiàn)也十分密切。
一個(gè)例外的情況是谆吴，不需要在哈希值的定義中包含你的對(duì)象所屬的類倒源。這主要是作為isEqual:方法的一個(gè)保護(hù)措施，是為了確保跟不同對(duì)象之間比較時(shí)剩余內(nèi)容的檢測有意義句狼。如果通過不同的數(shù)學(xué)方式去合并不同屬性的哈希值笋熬，那么你的哈希值很可能跟其他不同的類的哈希值相比就會(huì)非常不一樣。
生成屬性的哈希值
檢測屬性的相等性通常來說是很簡單的腻菇，但計(jì)算他們的哈希值卻不總是那么簡單胳螟。你如何計(jì)算一個(gè)屬性的哈希值取決于對(duì)象的類型是什么昔馋。
對(duì)于數(shù)值型屬性，哈希值可以被簡單的設(shè)定為數(shù)字的值糖耸。
對(duì)于對(duì)象型屬性秘遏，你可以通過調(diào)用對(duì)象的哈希方法，來使用其返回的哈希值蔬捷。
對(duì)于數(shù)據(jù)型屬性垄提，你會(huì)想要使用一些哈希算法來生成哈希值。你可以使用 CRC32 周拐，或者重量型的 MD5 铡俐。后者的執(zhí)行速度相對(duì)較慢，但便于使用妥粟，它通過把數(shù)據(jù)封裝在 NSData 中审丘，并且獲取它的哈希值。在上面的例子中勾给，你可以像這樣計(jì)算出 _data 的哈希值：
[[NSData dataWithBytes: _data length: _length] hash];
合并屬性的哈希值
所以你已經(jīng)知道了如何為每個(gè)屬性生成哈希值滩报，但是要如何將他們合并在一起呢？
最簡單的方式就是將他們相加在一起播急，或者使用按位或的特性脓钾。然而，這會(huì)破壞哈希值的獨(dú)特性桩警，因?yàn)檫@些操作都是對(duì)稱性的可训，意味著區(qū)分不同對(duì)象時(shí)會(huì)出錯(cuò)。舉個(gè)例子捶枢，假設(shè)一個(gè)對(duì)象有 first 和 last name 兩個(gè)屬性握截，它的哈希方法的實(shí)現(xiàn)如下：
- (NSUInteger)hash {
return [_firstName hash] ^ [_lastName hash];
}
現(xiàn)在假設(shè)你有兩個(gè)對(duì)象，一個(gè)是 “George Frederick” 烂叔，另一個(gè)是 “Frederick George”谨胞。即使他們很明顯是不同的，但他們還是會(huì)有相同的哈希值蒜鸡。雖然哈希碰撞的發(fā)生是完全不可避免的胯努，但我們也應(yīng)該盡量讓這種情況不輕易出現(xiàn)。
如何合并哈希值是一個(gè)復(fù)雜的主題逢防，是無法用一個(gè)回答就能解釋的康聂。然而，使用任何不對(duì)稱的方式去合并哈希值卻是一個(gè)很好的開始胞四。我打算使用位移運(yùn)算加上按位異或預(yù)算來合并他們。
#define NSUINT_BIT (CHAR_BIT * sizeof(NSUInteger))
#define NSUINTROTATE(val, howmuch) ((((NSUInteger)val) << howmuch) | (((NSUInteger)val) >> (NSUINT_BIT - howmuch)))
- (NSUInteger)hash {
return NSUINTROTATE([_firstName hash], NSUINT_BIT / 2) ^ [_firstName hash];
}
自定義哈希值用例
現(xiàn)在我們可以運(yùn)用上述內(nèi)容來為前面的例子生成一個(gè)哈希值伶椿。這跟判等方法的實(shí)現(xiàn)一樣會(huì)遵循一些基本的格式辜伟，并且會(huì)使用上述的技術(shù)去獲取和合并每個(gè)屬性的哈希值氓侧。
- (NSUInteger)hash {
NSUInteger dataHash = [[NSData dataWithBytes: _data length: _length] hash];
return NSUINTROTATE(dataHash, NSUINT_BIT / 2) ^ [_name hash];
}
如果你還有更多的屬性，你可以添加更多的位移運(yùn)算和按位或操作导狡，而且這個(gè)流程都是類似的约巷。你還可能會(huì)想要為每一個(gè)屬性調(diào)整位移運(yùn)算來使得他們每一個(gè)都是不同的。
子類化時(shí)注意點(diǎn)
你必須要注意當(dāng)你子類化的是一個(gè)實(shí)現(xiàn)了自定義的哈希方法和判等方法的父類旱捧。尤其是你的子類不應(yīng)該暴露那些在判等方法的實(shí)現(xiàn)中使用到的新的屬性独郎。如果你這樣做了，那么該子類的實(shí)例肯定與父類的實(shí)例不相等枚赡。
為了解釋這種情況氓癌，假設(shè)一個(gè)子類擁有 first/last name 屬性，且包含一個(gè) birthday 屬性贫橙，而且 birthday 作為判等計(jì)算的一部分贪婉。然而，這不可以用在父類的實(shí)例中比較相等性卢肃，所以它的判等方法看起來像這樣：
- (BOOL)isEqual: (id)other {
// 筆者注：如果調(diào)用父類的判等實(shí)現(xiàn)的結(jié)果返回了 NO 疲迂，那么不用比較新屬性（如果有）也可知道肯定也不相等。
if(![super isEqual: other])
return NO;
// 如果執(zhí)行到這一步莫湘，證明通過父類的判等實(shí)現(xiàn)的結(jié)果返回的是 YES 尤蒿，接下來觀察要判斷 other 是否是子類或者子類的子類類型，如果不是幅垮，則證明要判等的兩個(gè)對(duì)象實(shí)質(zhì)上是同一個(gè)父類對(duì)象腰池。
if(![other isKindOfClass: [MyClass class]])
return YES;
// 如果執(zhí)行到這一步，證明要判等的是兩個(gè)子類類型军洼，而且對(duì)于父類中的屬性已被證明是相等的巩螃，那么接下來繼續(xù)判斷新屬性是否相等即可。
return [[other birthday] isEqual： _birthday];
}
現(xiàn)在假設(shè)你有一個(gè)父類的實(shí)例對(duì)應(yīng) “John Smith” 匕争，我稱之為 A 避乏，和一個(gè)子類實(shí)例對(duì)應(yīng) “John Smith”，并且生日為 5/31/1982甘桑，我稱之為 B 拍皮。因?yàn)橛辛松鲜龅呐械榷x，那么結(jié)果為跑杭，A 等于 B 铆帽，B 也等于他自己，得到了期望的結(jié)果德谅。
現(xiàn)在假設(shè)你有一個(gè)子類的實(shí)例對(duì)應(yīng) “John Smith” 爹橱，生日為 6/7/1994，我稱之為 C 窄做。那么 C 不等于 B 愧驱，得到我們期望的結(jié)果慰技。 C 等于 A ，同樣得到期望的結(jié)果组砚。但是現(xiàn)在出現(xiàn)了一個(gè)問題吻商，A 等于 B 和 C ，但是 B 和 C 不相等糟红！這打破了相等操作的傳遞性艾帐，并且會(huì)造成非常意外的后果。
通常來講這不應(yīng)該是一個(gè)嚴(yán)重的問題盆偿。如果你的子類添加了會(huì)影響父類對(duì)象判等的新屬性柒爸，這是你的類層級(jí)結(jié)構(gòu)中的一個(gè)明顯的設(shè)計(jì)問題。你應(yīng)該去考慮如何重新設(shè)計(jì)你的類層級(jí)結(jié)構(gòu)陈肛，而不是在isEqual:方法中做一些復(fù)雜的實(shí)現(xiàn)揍鸟。
使用字典時(shí)注意點(diǎn)
如果你想要在 NSDictionary 中使用你的對(duì)象來作為 key 值，你需要實(shí)現(xiàn)對(duì)應(yīng)的哈希方法和判等方法句旱，而且你也需要實(shí)現(xiàn)-copyWithZone:方法阳藻。做這樣的技巧已經(jīng)超出了本文的內(nèi)容，但你應(yīng)該意識(shí)到在某些情況下你需要做更多事情谈撒。
總結(jié)
在 Cocoa 編程中已經(jīng)為你提供了哈希方法和判等方法的默認(rèn)實(shí)現(xiàn)腥泥，這對(duì)于許多對(duì)象而言是有用的，但是如果你想要為你自己的對(duì)象即使在內(nèi)存地址是不相同的情況下啃匿，也想要通過判等結(jié)果返回 YES 來指明他們是相等的蛔外，那么你就必須要做一點(diǎn)額外的工作。幸運(yùn)的是溯乒，這實(shí)現(xiàn)起來并不困難夹厌，并且一旦你實(shí)現(xiàn)了他們，你自定義的類將可以用在許多 Cocoa 的集合類中裆悄。
