來自掘金 《實(shí)現(xiàn) Equality 和 Hashing》

image

翻譯自 Mike Ash 的 Implementing Equality and Hashing

Equality

對象判等是一個基本的概念，在代碼中經(jīng)常會被使用到。在 Cocoa 編程中，它通過 isEqual: 方法被實(shí)現(xiàn)。一些比較簡單的例子像[array indexOfObject:]會在底層使用到它，所以說對象支持判等是非常重要的。

在 Cocoa 編程中，它已經(jīng)為我們在 NSObject 中提供了一個默認(rèn)的判等實(shí)現(xiàn)。這個默認(rèn)的實(shí)現(xiàn)只是通過對象的指針地址來進(jìn)行判等。換句話說，一個對象只會與它自己相等。這個默認(rèn)實(shí)現(xiàn)從功能上看如下面代碼所示：

- (BOOL)isEqual: (id)other {
    return self == other;
}

雖然該默認(rèn)的判等實(shí)現(xiàn)看上去過于簡單，但實(shí)際上它對于許多對象來說，是十分有用的。比如，我們永遠(yuǎn)不會把一個 NSView 看做跟另外一個 NSView 同等。同樣的，對于很多具有該特性的類來說，這個默認(rèn)的判等實(shí)現(xiàn)已經(jīng)是足夠了。這或許是個好消息，因?yàn)檫@意味著如果你的類具有相同的判等特性，那么你不需要做任何事情就可以免費(fèi)得到想要的結(jié)果。

實(shí)現(xiàn)自定義判等

有時候你需要實(shí)現(xiàn)更深層次的判等。這對于許多對象來說是很正常的，特別是那些被看作“值類型的對象”，他們是根據(jù)邏輯上的判等來區(qū)分。舉個例子：

// 使用可變類型保證生成的是不同的字符串對象
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)。但是如果你想要為自定義的對象做同樣的操作該怎么辦？

MyClass *c1 = ...;
MyClass *c2 = ...;
BOOL equal = [c1 isEqual: c2];

在這種情況下你需要實(shí)現(xiàn)你自己版本的isEqual:方法。

測試相等性在大多數(shù)情況下是相當(dāng)簡單的。把你的類中所有相關(guān)的屬性收集起來，再測試他們的相等性。如果他們當(dāng)中有不相等的，那么返回 NO ，否則返回 YES 。

有一個微妙的點(diǎn)就是，當(dāng)你的對象所對應(yīng)的類也是檢測相等性中的一個重要的屬性。去檢測 MyClass 和 NSString 的相等性是十分合理的，但是這種比較的結(jié)果永遠(yuǎn)不會返回 YES （除非 MyClass 是 NSString 的一個子類）。

有一個稍微不那么微妙的點(diǎn)就是，確保你測試的屬性對于判等來說是非常重要的。一些像緩存 caches 這樣的屬性對于你的對象的外部視角而言是無關(guān)緊要的，那么它就不需要被用作判等的因素。

比如說你的類看起來像這樣：

@interface MyClass: NSObject {
   int _length;
   char *_data;
   NSString *_name;
   NSMutableDictionary *_cache;
}

你的判等實(shí)現(xiàn)看起來會像這樣：

- (BOOL)isEqual: (id)other {
   return ([other isKindOfClass: [MyClass class]] && [other length]  == _length && memcmp([other data], _data, _length) == 0 && [[other name] isEqual: _name])
   // 注意：沒有 _cache 的比較
}

Hashing

哈希表是一個普通的數(shù)據(jù)結(jié)構(gòu)，被用于實(shí)現(xiàn) NSDictionary 和 NSSet 等。無論你往容器類中添加多少對象，都能夠支持快速查找到相應(yīng)的對象。

如果你已經(jīng)了解哈希表是如何工作的，你可以直接跳過接下來的一到兩個段落內(nèi)容。

哈希表基本上可以被看做是一個帶特殊索引的龐大數(shù)組。所有被添加到數(shù)組的對象都會有一個索引關(guān)聯(lián)著他們的哈希值。這個哈希值本質(zhì)上是由對象的屬性而產(chǎn)生的偽隨機(jī)的數(shù)字。這種機(jī)制使得索引有足夠的隨機(jī)性，那么兩個對象就不太可能擁有相同的哈希值了，但這是完全可復(fù)寫的。當(dāng)一個對象被插入到數(shù)組中時，它的哈希值會被用來決定它該被放到哪個位置上。當(dāng)一個對象被查找時，它的哈希值會被用來決定到哪個位置中查找。

用更加正式的術(shù)語來講，一個對象的哈希值被定義了，如果兩個對象是相等的，那么他們會有相同的哈希值。要注意的是，反過來說是不正確的，也不應(yīng)該這樣，因?yàn)椋簝蓚€對象可以有相同的哈希值，但是他們可以不相等。你想要盡可能的避免出現(xiàn)這種情況，因?yàn)楫?dāng)兩個不相等的對象擁有兩個相同的哈希值（稱為碰撞），那么哈希表就必須采取特殊的措施去處理這種情況，這是一個非常耗時的操作。然而，這已經(jīng)被證明了要想完全避免哈希碰撞的發(fā)生是不可能的。

在 Cocoa 編程中，哈希的實(shí)現(xiàn)通過哈希方法，它的方法簽名為：

- (NSUInteger)hash;

跟對象判等一樣，NSObject 也為你提供了一個默認(rèn)的哈希實(shí)現(xiàn)，但這是通過使用對象的標(biāo)識來實(shí)現(xiàn)的。粗略的講，它做了這些事情：

- (NSUInteger)hash {
    return (NSUInteger)self;
}

實(shí)際返回的值可能不一樣，但本質(zhì)的關(guān)鍵點(diǎn)是，這種方式是基于實(shí)際指向 self 的指針的值。跟判等方法一樣，如果基于對象標(biāo)識的判等已經(jīng)達(dá)到你想要的需求，那么默認(rèn)的實(shí)現(xiàn)對你來說已經(jīng)是有用的了。

實(shí)現(xiàn)自定義哈希值

因?yàn)楣５恼Z義，如果你重寫了isEqual:方法，你就必須重寫哈希方法。如果你不這樣做，你會遇到兩個相同對象卻擁有不同的哈希值的情況，這是十分不安全的。如果你在字典、集合或者其他需要哈希表的地方使用到這些對象，那么會出現(xiàn)問題。

因?yàn)閷ο蠊Ｖ档亩x和相等性的關(guān)系是十分密切的，同樣的，哈希方法的實(shí)現(xiàn)和判等方法的實(shí)現(xiàn)也十分密切。

一個例外的情況是，不需要在哈希值的定義中包含你的對象所屬的類。這主要是作為isEqual:方法的一個保護(hù)措施，是為了確保跟不同對象之間比較時剩余內(nèi)容的檢測有意義。如果通過不同的數(shù)學(xué)方式去合并不同屬性的哈希值，那么你的哈希值很可能跟其他不同的類的哈希值相比就會非常不一樣。

生成屬性的哈希值

檢測屬性的相等性通常來說是很簡單的，但計(jì)算他們的哈希值卻不總是那么簡單。你如何計(jì)算一個屬性的哈希值取決于對象的類型是什么。

對于數(shù)值型屬性，哈希值可以被簡單的設(shè)定為數(shù)字的值。

對于對象型屬性，你可以通過調(diào)用對象的哈希方法，來使用其返回的哈希值。

對于數(shù)據(jù)型屬性，你會想要使用一些哈希算法來生成哈希值。你可以使用 CRC32 ，或者重量型的 MD5 。后者的執(zhí)行速度相對較慢，但便于使用，它通過把數(shù)據(jù)封裝在 NSData 中，并且獲取它的哈希值。在上面的例子中，你可以像這樣計(jì)算出 _data 的哈希值：

[[NSData dataWithBytes: _data length: _length] hash];

合并屬性的哈希值

所以你已經(jīng)知道了如何為每個屬性生成哈希值，但是要如何將他們合并在一起呢？

最簡單的方式就是將他們相加在一起，或者使用按位或的特性。然而，這會破壞哈希值的獨(dú)特性，因?yàn)檫@些操作都是對稱性的，意味著區(qū)分不同對象時會出錯。舉個例子，假設(shè)一個對象有 first 和 last name 兩個屬性，它的哈希方法的實(shí)現(xiàn)如下：

- (NSUInteger)hash {
    return [_firstName hash] ^ [_lastName hash];
}

現(xiàn)在假設(shè)你有兩個對象，一個是 “George Frederick” ，另一個是 “Frederick George”。即使他們很明顯是不同的，但他們還是會有相同的哈希值。雖然哈希碰撞的發(fā)生是完全不可避免的，但我們也應(yīng)該盡量讓這種情況不輕易出現(xiàn)。

如何合并哈希值是一個復(fù)雜的主題，是無法用一個回答就能解釋的。然而，使用任何不對稱的方式去合并哈希值卻是一個很好的開始。我打算使用位移運(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)容來為前面的例子生成一個哈希值。這跟判等方法的實(shí)現(xiàn)一樣會遵循一些基本的格式，并且會使用上述的技術(shù)去獲取和合并每個屬性的哈希值。

- (NSUInteger)hash {
    NSUInteger dataHash = [[NSData dataWithBytes: _data length: _length] hash];
    return NSUINTROTATE(dataHash, NSUINT_BIT / 2) ^ [_name hash];
}

如果你還有更多的屬性，你可以添加更多的位移運(yùn)算和按位或操作，而且這個流程都是類似的。你還可能會想要為每一個屬性調(diào)整位移運(yùn)算來使得他們每一個都是不同的。

子類化時注意點(diǎn)

你必須要注意當(dāng)你子類化的是一個實(shí)現(xiàn)了自定義的哈希方法和判等方法的父類。尤其是你的子類不應(yīng)該暴露那些在判等方法的實(shí)現(xiàn)中使用到的新的屬性。如果你這樣做了，那么該子類的實(shí)例肯定與父類的實(shí)例不相等。

為了解釋這種情況，假設(shè)一個子類擁有 first/last name 屬性，且包含一個 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 是否是子類或者子類的子類類型，如果不是，則證明要判等的兩個對象實(shí)質(zhì)上是同一個父類對象。
    if(![other isKindOfClass: [MyClass class]])
        return YES;
        
    // 如果執(zhí)行到這一步，證明要判等的是兩個子類類型，而且對于父類中的屬性已被證明是相等的，那么接下來繼續(xù)判斷新屬性是否相等即可。
    return [[other birthday] isEqual： _birthday];
}

現(xiàn)在假設(shè)你有一個父類的實(shí)例對應(yīng) “John Smith” ，我稱之為 A ，和一個子類實(shí)例對應(yīng) “John Smith”，并且生日為 5/31/1982，我稱之為 B 。因?yàn)橛辛松鲜龅呐械榷x，那么結(jié)果為，A 等于 B ，B 也等于他自己，得到了期望的結(jié)果。

現(xiàn)在假設(shè)你有一個子類的實(shí)例對應(yīng) “John Smith” ，生日為 6/7/1994，我稱之為 C 。那么 C 不等于 B ，得到我們期望的結(jié)果。 C 等于 A ，同樣得到期望的結(jié)果。但是現(xiàn)在出現(xiàn)了一個問題，A 等于 B 和 C ，但是 B 和 C 不相等！這打破了相等操作的傳遞性，并且會造成非常意外的后果。

通常來講這不應(yīng)該是一個嚴(yán)重的問題。如果你的子類添加了會影響父類對象判等的新屬性，這是你的類層級結(jié)構(gòu)中的一個明顯的設(shè)計(jì)問題。你應(yīng)該去考慮如何重新設(shè)計(jì)你的類層級結(jié)構(gòu)，而不是在isEqual:方法中做一些復(fù)雜的實(shí)現(xiàn)。

使用字典時注意點(diǎn)

如果你想要在 NSDictionary 中使用你的對象來作為 key 值，你需要實(shí)現(xiàn)對應(yīng)的哈希方法和判等方法，而且你也需要實(shí)現(xiàn)-copyWithZone:方法。做這樣的技巧已經(jīng)超出了本文的內(nèi)容，但你應(yīng)該意識到在某些情況下你需要做更多事情。

總結(jié)

在 Cocoa 編程中已經(jīng)為你提供了哈希方法和判等方法的默認(rèn)實(shí)現(xiàn)，這對于許多對象而言是有用的，但是如果你想要為你自己的對象即使在內(nèi)存地址是不相同的情況下，也想要通過判等結(jié)果返回 YES 來指明他們是相等的，那么你就必須要做一點(diǎn)額外的工作。幸運(yùn)的是，這實(shí)現(xiàn)起來并不困難，并且一旦你實(shí)現(xiàn)了他們，你自定義的類將可以用在許多 Cocoa 的集合類中。